A
Blue-Tiger schrieb:
Ein AVL-Baum der Hoehe 0 hat keinen inneren Knoten,
Hm,
ist denk ich Definitionssache.
Wenn man hergeht, die Blätter als NULL-Zeiger auffasst und diese
in die Zeichnung nicht einfließen läßt, dann erhält man einen Baum der Höhe 0
mit genau einem inneren Knoten.
also statt
I
/ \
B B
einfach nur
I
(I == innerer Knoten, B == Blatt)
Blue-Tiger schrieb:
ein AVL-Baum der Hoehe 1 kann ebenfalls 0 innere Knoten haben: wenn ein Teilbaum 1 Element hat, der andere kein Element... wobei ich allerdings davon ausgehe, dass ein Knoten, der nur 1 Nachfolger hat, ein aeusserer Knoten ist (wenn ich mich da irre, ist auch meine folgende Ueberlegung hinfaellig):
Dieses Problem ergibt sich bei obiger Definition nicht,
da man hier nur innere Knoten zeichnet
Blue-Tiger schrieb:
Ich hab mal kurz rumgespielt, und ich denke ( ACHTUNG: reine Intiution!) folgendes:
wenn du einen AVL-Baum der Hoehe 12 hast, dann ist er bis mindestens Hoehe 10 vollstaendig (bzw. Allgemein: bei Hoehe i ist er bis i-2 vollstaendig... Ansonsten wuerde das bedeuten, dass in irgend einem Knoten in i-2 die Strukturbedingung nicht erfuellt ist (behaupt ich einfach mal (ACHTUNG: reine Intuition!)... mir ists nicht gelungen, einen Baum hinzuzeichnen, bei dem's nicht so ist ).
Genau auf den selben Fehler bin ich auch reingefallen.
Ein Baum der Höhe 5 ist nicht bis 3 vollständig (in der dritten Ebene fehlt ein Knoten (das X, hab ich auch ewig lang übersehen ):
0 I
/ \
1 I I
/ \ / \
2 I I I I
/ \ / \ / / \
3 I I I I I X I I // X ist nicht besetzt
/ \ \ \ \
4 I I I I I
/
5 I
Blue-Tiger schrieb:
Wenn man nun einen Baum weiterwachsen lassen will, reicht es von jedem 2ten Blatt aus einen Teilbaum der Laenge 2 runterwachsen zu lassen und von den anderen Blaettern jeweils einen der Laenge 1. Damit waeren alle Knoten der 10ten Ebene noch innere Knoten, alles was darauf folgt nicht mehr.
Damit:
Ein AVL-Baum der Hoehe 12 hat mindestens so viel innere Knoten wie ein vollstaendiger AVL-Baum der Hoehe 10 insgesamt Knoten hat.
Najo, wenn bis 10 vollständig...
PS:
hier mal ne andere Darstellung, wie ich auf meine Formel gekommen bin:
jede Zahl stellt die Wurzel eines (Teil-)baumes dar und gibt an, aus wievielen
Knoten dieser Baum besteht
0 20
/ \
1 12 7
/ \ / \
2 7 4 2 4
/ \ / \ / / \
3 4 2 1 2 1 X 1 2 // X ist nicht besetzt
/ \ \ \ \
4 2 1 1 1 1
/
5 1
Der Knoten ganz links unten ist ein Baum der Höhe 0.
der drüberliegende hat Höhe 1.
Knoten 4 darüber besteht nun aus einem linken Teilbaum der Höhe 1, der Rechte hat Höhe 0.
Somit besteht der Baum aus insgesammt 4 Knoten (einschließlich der Wurzel)
usw.
PPS:
Danke für die Antwort
