Definition eines ausgeglichenen Baumes

Ich frage mich nur, ob jemand in der Lage sein könnte, die Definition eines ausgeglichenen Baumes für mich zu klären. Ich habe das "ein Baum ist ausgeglichen, wenn jeder Teilbaum ausgeglichen ist und sich die Höhe der beiden Teilbäume um höchstens einen unterscheidet.

Ich entschuldige mich, wenn dies eine dumme Frage ist, aber gilt diese Definition für jeden Knoten bis hinunter zu den Blättern eines Baumes oder nur für die linken und rechten Teilbäume unmittelbar vor der Wurzel? Ich denke, eine andere Möglichkeit, dies zu erfassen, wäre: Ist es möglich, dass interne Knoten eines Baums nicht ausgeglichen sind und der gesamte Baum ausgeglichen bleibt?

Die Einschränkung wird im Allgemeinen rekursiv auf jeden Teilbaum angewendet. Das heißt, der Baum ist nur ausgeglichen, wenn:

1. Die Höhen der linken und rechten Teilbäume unterscheiden sich um höchstens eins UND
2. Der linke Teilbaum ist ausgeglichen UND
3. Der rechte Teilbaum ist ausgeglichen

Demnach ist der nächste Baum ausgeglichen:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

Der nächste ist nicht ausgeglichen, da sich die Teilbäume von C in ihrer Höhe um 2 unterscheiden:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

Die spezifische Einschränkung des ersten Punkts hängt jedoch von der Art des Baums ab. Die oben aufgeführte ist die typische für AVL-Bäume .

Rot-schwarze Bäume zum Beispiel erzwingen eine weichere Einschränkung.

Es gibt verschiedene Möglichkeiten, "Balanced" zu definieren. Das Hauptziel ist es, die Tiefe aller Knoten beizubehalten O(log(n)).

Es scheint mir, dass die Gleichgewichtsbedingung, über die Sie gesprochen haben, für den AVL-Baum gilt .
Hier ist die formale Definition der Gleichgewichtsbedingung des AVL-Baums :

Für jeden Knoten in AVL unterscheidet sich die Höhe seines linken Teilbaums um höchstens 1 von der Höhe seines rechten Teilbaums.

Nächste Frage, was ist " Höhe "?

Die " Höhe " eines Knotens in einem Binärbaum ist die Länge des längsten Pfades von diesem Knoten zu einem Blatt.

Es gibt einen seltsamen, aber häufigen Fall:

Menschen definieren die Höhe eines leeren Baumes (-1).

Das linke Kind von root ist beispielsweise null:

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Zwei weitere Beispiele zur Bestimmung:

Ja, ein ausgeglichener Baum Beispiel:

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

Nein, kein ausgeglichener Baum Beispiel:

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      

Es gibt keinen Unterschied zwischen diesen beiden Dingen. Denk darüber nach.

Nehmen wir eine einfachere Definition: "Eine positive Zahl ist gerade, wenn sie Null ist, oder diese Zahl minus zwei ist gerade." Sagt dies, dass 8 gerade ist, wenn 6 gerade ist? Oder heißt das, dass 8 gerade ist, wenn 6, 4, 2 und 0 gerade sind?

Es gibt keinen Unterschied. Wenn 8 gerade ist, wenn 6 gerade ist, heißt es auch, dass 6 gerade ist, wenn 4 gerade ist. Und so heißt es auch, dass 4 gerade ist, wenn 2 gerade ist. Und so heißt es, dass 2 gerade ist, wenn 0 gerade ist. Wenn also 8 gerade ist, wenn 6 gerade ist, heißt es (indirekt), dass 8 gerade ist, wenn 6, 4, 2 und 0 gerade sind.

Hier ist es dasselbe. Jeder indirekte Teilbaum kann durch eine Kette direkter Teilbäume gefunden werden. Selbst wenn es nur direkt für direkte Teilbäume gilt, gilt es dennoch indirekt für alle Teilbäume (und damit für alle Knoten).

Der ausgeglichene Baum ist ein Baum, dessen Höhe in der Größenordnung des Protokolls liegt (Anzahl der Elemente im Baum).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

Der Definition "ein Baum ist ausgeglichen von jedem Teilbaum ist ausgeglichen und die Höhe der beiden Teilbäume unterscheidet sich um höchstens einen" folgen AVL-Bäume.

Da AVL-Bäume ausgeglichen sind, aber nicht alle ausgeglichenen Bäume AVL-Bäume sind, halten ausgeglichene Bäume diese Definition nicht und interne Knoten können in ihnen unausgeglichen sein. Für AVL-Bäume müssen jedoch alle internen Knoten ausgeglichen sein.

Das Ziel eines ausgeglichenen Baumes ist es, das Blatt in einem Minimum an Durchquerung (minimale Höhe) zu erreichen. Der Grad des Baums ist die Anzahl der Zweige minus 1. Ein ausgeglichener Baum ist möglicherweise nicht binär.

1. Die Höhe eines Knotens in einem Baum ist die Länge des längsten Pfades von diesem Knoten nach unten zu einem Blatt, wobei sowohl der Anfangs- als auch der Endscheitelpunkt des Pfads gezählt werden.
2. Ein Knoten in einem Baum ist höhenausgeglichen, wenn sich die Höhen seiner Teilbäume um nicht mehr als 1 unterscheiden.
3. Ein Baum ist höhenausgeglichen, wenn alle seine Knoten höhenausgeglichen sind.