Anzahl der Knoten innerhalb des Bereichs im binären Suchbaum in O (LogN)

Question

Gegeben eine BST und zwei ganze Zahlen "a" und "b" (a < b), wie können wir die Anzahl der Knoten so finden, dass ein < Knotenwert < b, in O (log n)?

Ich weiß, man kann leicht die Position von a und b in LogN Zeit finden, aber wie man die Knoten dazwischen zählt, ohne eine Traversierung zu machen, die O (n) ist?

Answer 1

In jedem Knoten Ihres binären Suchbaumes, auch Zählung der Anzahl der Werte im Baum halten, die kleiner als ihr Wert (oder für einen anderen Baumentwurf erwähnte in die Fußnote unten, die Knoten in seinem linken Teilbaum).

Suchen Sie zuerst den Knoten mit dem Wert a. Holen Sie sich die Anzahl der Werte kleiner als a, die in diesem Knoten gespeichert wurde. Dieser Schritt ist Log (n).

Suchen Sie nun den Knoten mit dem Wert b. Erhalten Sie die Anzahl der Werte kleiner als b, die in diesem Knoten gespeichert sind. Dieser Schritt ist auch Log (n).

Subtrahieren Sie die zwei Zähler und Sie haben die Anzahl der Knoten zwischen a und b. Die gesamte Komplexität dieser Suche ist 2 * Log (n) = O (Log (n)).

---

_{Siehe this video. Der Professor erklärt Ihre Frage hier mit Splay Trees.}

Answer 2

Die Idee ist einfach.

1. Die BST ausgehend von der Wurzel durchlaufen.
2. Überprüfen Sie für jeden Knoten, ob er in Reichweite liegt. Wenn es im Bereich liegt, dann zähle ++. Und wiederkehren für beide seiner Kinder.
3. Wenn der aktuelle Knoten kleiner als der niedrige Wert des Bereichs ist, dann wiederholen Sie für das rechte Kind, andernfalls wiederholen Sie für das linke Kind.

Zeitkomplexität O(height + number of nodes in range) sein ..

Für Ihre Frage, warum es nicht O(n) ist.

Da wir nicht den gesamten Baum durchlaufen, ist dies die Anzahl der Knoten im Baum. Wir durchlaufen nur den erforderlichen Teilbaum gemäß den Daten des Elternteils.

Pseudocode

int findCountInRange(Node root, int a, int b){ 

    if(root==null) 
     return 0; 
    if(root->data <= a && root->data >= b) 
     return 1 + findCountInRange(root->left, a, b)+findCountInRange(root->right, a, b); 
    else if(root->data < low) 
     return findCountInRange(root->right, a, b); 
    else 
     return findCountInRange(root->left, a, b); 

} 

Answer 3

speichern die Inorder Traversierung von BST in Array (es wird sortiert werden). Die Suche nach 'a' und 'b' dauert log (n) mal und sie erhalten ihren Index und nehmen den Unterschied. Dies gibt die Anzahl der Knoten im Bereich 'a' bis 'b'.

Raum Komplexität O (n)