Zähle Anzahl kleinerer Werte beim Einfügen in den binären Suchbaum (BST)

Question

Ich implementiere gerade einen Algorithmus, bei dem ich wissen muss, wie viele Zahlen von denen, die bereits gelesen wurden, kleiner als die aktuelle sind verarbeitet werden.

Ein Weg, dies zu tun, ist durch merge sort, aber ich bin mehr interessiert an einem BST-Ansatz.

Dieses Verfahren soll in O(log n) die Anzahl der Knoten mit Wert kleiner als der Schlüssel Knotens Wert berechnen:

countLessThan(int x, node T) 
    if T = null 
     return 
    if T.value >= x 
     countLessThan(x, T.left) // T.left contains only numbers < T.value and T.right only numbers > T.value 
    else 
     globalResult += T.numLeft 
     countLessThan(x, T.right) 

Die numLeft Feld in diesem Fall in jedem Knoten gespeichert werden würde, und die Anzahl der Knoten repräsentieren in seinem linken Teilbaum (selbst enthalten).

Also meine Frage ist, wie dieses bestimmte Feld auf schnelle Weise zu aktualisieren?

Answer 1

Sie könnten die Anzahl der Blätter, die mit der linken (weniger als) Seite verbunden sind, in jedem Knoten speichern und diese Zahl für jeden Zweig, den Sie auf der linken Seite übergeben, beim Einfügen eines neuen Blattes erhöhen.

Die Anzahl der Werte, die kleiner als der neu eingefügte Wert sind, kann gleichzeitig berechnet werden, indem alle Zählwerte der Zweige, die Sie beim Einfügen passieren, hinzugefügt werden.

Unten ist ein JavaScript-Code-Schnipsel das Verfahren zu demonstrieren:

function CountTree() {       // tree constructor 
 
    this.root = null; 
 

 
    this.insert = function(value) { 
 
     var branch = null, node = this.root, count = 0, after; 
 
     while (node != null) {     // traverse tree to find position 
 
      branch = node; 
 
      after = value > node.value;   // compare to get direction 
 
      if (after) { 
 
       node = branch.right;    // pass on the right (greater) 
 
       count += branch.count;   // add all nodes to the left of branch 
 
      } else { 
 
       node = branch.left;    // pass on the left (smaller or equal) 
 
       ++branch.count;     // increment branch's count 
 
      } 
 
     }          // attach new leaf 
 
     if (branch == null) this.root = new Leaf(value); 
 
     else if (after) branch.right = new Leaf(value); 
 
     else branch.left = new Leaf(value); 
 
     return count; 
 
    } 
 

 
    function Leaf(value) {      // leaf constructor 
 
     this.value = value; 
 
     this.left = null; 
 
     this.right = null; 
 
     this.count = 1; 
 
    } 
 
} 
 

 
var t = new CountTree(), v = [5, 3, 8, 2, 4, 7, 9, 1, 4, 7, 8]; 
 
for (var i in v) { 
 
    document.write("Inserting " + v[i] + " (found " + t.insert(v[i]) + " smaller)<BR>"); 
 
}

Dies ist der Baum aus dem Beispiel in dem Code, wenn das letzte Element eingefügt (der zweite Wert 8) . Jeder Knoten hat die Anzahl der Knoten zu seiner Linken (einschließlich sich selbst) unter seinem rechten Eckpunkt gedruckt. Wenn Sie die zweite 8 einfügen, übergeben Sie die Knoten mit den Werten 5, 8 und 7; von diesen werden 5 und 7 rechts weitergegeben, und die Summe ihrer Zählungen ist 6 + 2 = 8, also gibt es 8 Werte kleiner als 8 im Baum: 1, 2, 3, 4, 4, 5, 7 und 7. der erste Knoten mit dem Wert 8 wird auf der linken Seite übergeben, so seine Zählung wird von 3 bis 4.