AVL-Bäume

AVL Tree ist ein ausgewogener binärer Suchbaum. Der Beitrag führte binäre Suchbäume ein. Die Such-, Einfüge- und Löschzeiten für einen Binärbaum hängen von der Höhe des Baums ab. Im schlimmsten Fall beträgt die Höhe O(n). Wenn ein Baum perfekt ausbalanciert ist – also ein vollständiger Binärbaum – beträgt seine Höhe log n. Können wir einen perfekt ausgeglichenen Baum erhalten? Ja, aber dies wird kostspielig sein. Der Kompromiss besteht darin, einen ausgewogenen Baum beizubehalten – das heißt, die Höhen der beiden Teilbäume jedes Knotens sind ungefähr gleich.

AVL-Bäumesind gut ausbalanciert. AVL-Bäume wurden 1962 von zwei russischen Informatikern, G. M. Adelson-Velsky und E. M. Landis, erfunden (daher der Name AVL). In einem AVL-Baum beträgt der Unterschied zwischen den Höhen der beiden Teilbäume jedes Knotens 0 oder 1. Es kann gezeigt werden, dass die maximale Höhe eines AVL-Baums O(log n) beträgt.

Der Vorgang zum Einfügen oder Löschen eines Elements in einen AVL-Baum ist derselbe wie in einem regulären binären Suchbaum, mit der Ausnahme, dass Sie den Baum nach einem Einfüge- oder Löschvorgang möglicherweise neu ausbalancieren müssen. Der Balance-Faktor eines Knotens ist die Höhe seines rechten Teilbaums minus der Höhe seines linken Teilbaums. Ein Knoten gilt als ausgeglichen, wenn sein Ausgleichsfaktor -1, 0 oder 1 ist. Ein Knoten gilt als linkslastig, wenn sein Balancefaktor -1 ist, und als rechtslastig, wenn sein Balancefaktor +1 ist .

Das obige ist der detaillierte Inhalt vonAVL-Bäume. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!