Binäre Suchbaum: Wie/wenn mit unglücklichen Inserierung Aufträge zu behandeln?

Question

Ich bereite grundlegende Algorithmen und Datenstrukturen auf.

Eine typischer binärer Suchbaum Einfügung Algorithmus sieht ungefähr so ​​aus:

insert(newValue) 
    if newValue is less than node.value: 
     if lesser subtree exists: 
      insert into lesser subtree 
     otherwise: 
      lesser subtree = new tree with newValue 
    if newValue is greater than node.value 
     if greater subtree exists: 
      insert into greater subtree 
     otherwise: 
      greater subtree = new tree with newValue 

Mit einem unglücklichen Auftrag, können Sie einen Baum erhalten, die auf eine Liste identisch ist:

insert(1) 
insert(2) 
insert(3) 

Produziert:

1 
\ 
    2 
    \ 
    3 

Mit einem Baum, der eigentlich eine Liste ist, wird die Suche natürlich lineare Zeit nehmen e.

Wird für eine binäre Suchbaumimplementierung erwartet? Oder würden Sie erwarten, dass die Einfügefunktion eine Art Neuausrichtung durchführt?

Answer 1

Sie haben zwei Arten von binären Suchbäumen. Die erste, die Sie haben, im schlimmsten Fall dauert es lineare Zeit zum Einfügen und Löschen und das passiert, wenn Sie Dinge in Increasing oder decreasing Reihenfolge einfügen.

Dies ist jedoch einfach binarysearch tree.

Es gibt auch RedBlack Binary search Bäume oder manchmal 2-3 binäre Suchbaum genannt, weil in jedem Knoten können Sie zwei Werte haben. Dies bedeutet, dass Sie von jedem Knoten eine rote Verbindung oder eine schwarze Verbindung zu einem anderen Knoten haben. Diese werden als ausgeglichene Suchbaumstruktur bezeichnet, da die Anzahl der schwarzen Kanten in jedem Pfad gleich ist (von Quelle zu Tiefe). Hier wächst der Binärsuchbaum von unten, aber der RedBlack-Suchbaum zeigt einen Wert an, wenn der Knoten voll ist (das ist interessant).

Suchen und einfügen: Dieser Algorithmus ist ein wenig komplex, aber es ist Komplexität für einfügen und Suche ist immer ~logN.

Max Höhe Max Höhe dieses Baumes ist zwischen log3N und logN:

Hier eine Spur ist, wie es funktioniert: