minimale Anzahl innerer Knoten eines AVL-Baumes der Höhe 12

anonymus

Hallo,

Hab mir zur Übung mal die Prüfung vom letzten Jahr organisiert.
Unter anderem ist dort nach minimaler und maximaler Anzahl innerer Knoten eines
AVL-Baumes der Höhe 12 gefragt.

Maximal dürfte vermutlich ned so tragisch sein:
Der Baum ist voll besetzt

=> Summe i=0 bis 12 über 2^i

Für die minimale Anzahl hab ich aber dann doch recht lang gebraucht.
Bin dann zum Schluss (nach ungefähr mindestens der Hälfte der zulässigen Zeit
)auf sowas hier gekommen:

Ein AVL-Baum der Höhe h besteht mindestens aus einem
linken Unterbaum der Höhe h - 1, einem rechten Unterbaum der Höhe
h - 2 und dem Wurzelknoten.

Somit würde sich dieser Ansatz ergeben:

A(0) = 1;
A(1) = 2;
A(h) = A(h-1) + A(h-2) + 1; (für h >= 2)

wobei A(h) die minimale Anzahl der inneren Knoten in Abhängigkeit von der Höhe h liefert.

h	A(h)
------------
0	1
1	2
2	4
3	7
4	12
5	20
6	33
7	54
8	88
9	143
10	232
11	376
12	699

Leider hab ich keine Lösung für die Aufgabe und somit keinen Schimmer, ob das
allgemein richtig ist, bzw. wie ich das beweisen könnte.
(bin wirklich ned motiviert, einen solchen Baum zum Beweis an die Wand zu Pinseln...)

Oder gibt's hier auch eine einfachere Möglichkeit?

thx
Martin

Blue-Tiger

anonymus schrieb:

=> Summe i=0 bis 12 über 2^i

Oder Vereinfacht:
2^(13) - 1

Ein AVL-Baum der Höhe h besteht mindestens aus einem
linken Unterbaum der Höhe h - 1, einem rechten Unterbaum der Höhe
h - 2 und dem Wurzelknoten.

Somit würde sich dieser Ansatz ergeben:

A(0) = 1;
A(1) = 2;
A(h) = A(h-1) + A(h-2) + 1; (für h >= 2)

wobei A(h) die minimale Anzahl der inneren Knoten in Abhängigkeit von der Höhe h liefert.

Ein AVL-Baum der Hoehe 0 hat keinen inneren Knoten, 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):

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 ).

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.

anonymus

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 == 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