Get Intervall von binären Suchbaum so schnell wie sortierte Array

Question

Derzeit implementiere ich BST in Java für mein Universitätsprojekt. Wie wir wissen, ist BST ziemlich gut in der Suche nach einer einzigen Einheit Einheit, die O (log n) in einem ausgeglichenen Baum ist.

Aber, wie man Suche zwischen Wert a und b durchführt? (A < b)

Lassen Sie uns sagen, dass ich diesen Baum haben

│    ┌── 125 
│   ┌── 122 
│   │ └── 120 
│  ┌── 117 
│  │ │ ┌── 113 
│  │ └── 112 
│  │  └── 108 
│ ┌── 86 
│ │ │ ┌── 85 
│ │ └── 72 
└── 59 
    │   ┌── 56 
    │  ┌── 52 
    │ ┌── 47 
    │ │ │ ┌── 43 
    │ │ └── 39 
    │ │  │ ┌── 38 
    │ │  └── 36 
    └── 28 
     │  ┌── 18 
     │ ┌── 15 
     └── 2 
      └── 1 

I range(a,b) ein Verfahren schaffen wollen zurückzukehren Wert zwischen a und b inklusive. (Anmerkung: a und b im Baum nicht notwendig sind!)

Zum Beispiel: range(53,112)56,59,72,85,86,108,112

zurück Hier ist mein Pseudo-Code

/* recursive method */ 
range(a,b) 
    range(a,b,root); 

/* helper method */ 
range(a,b,node) 
    if (a <= node.value <= b) 
     if (node.left != null) and (node.value != a) 
      range(a,b,node.left) 

     print node.value 

     if (node.right != null) and (node.value != b) 
      range(a,b,node.right) 

    else if node.value < a 
     if (node.right != null) 
      range(a,b,node.right) 

    else // node.value > b 
     if (node.left != null) 
      range(a,b,node.left) 

Aber ich denke, dass meine Methode langsamer ist.

Zum Beispiel müssen wir in einem sortierten Array die binäre Suche auf a und b durchführen und ihren jeweiligen Index erhalten. Danach iterieren wir vom Index a zum Index b.

Stimmt es, dass BST beim Suchen mehrerer Werte langsamer arbeitet? Ist es möglich, meinen Algorithmus so schnell wie ein sortiertes Array zu verbessern?

Answer 1

Je nachdem, wie Sie das Ergebnis zurückgeben können, hat ein sortiertes Array den großen Vorteil, dass Sie die Ergebnisse nirgends kopieren müssen. Das Zurückgeben einer Zeiger- und Längenansicht in das Array ist viel schneller und cachefreundlicher als das Erstellen einer weiteren Kopie des Bereichs in einen anderen Puffer. Ein Baum muss immer Elemente aus dem Baum kopieren. Selbst wenn Sie eine Kopie benötigen (zum Modifizieren oder was auch immer), ist memcpy viel schneller als ein Baum zu gehen.

Dies ist kein Problem, wenn Sie während des Gehens am Baum (wie Sie mit print tun) können.

Ich immer scheinen Antworten vor dem googeln zu schreiben. Es stellt sich heraus, dass trees to answer range queries are a thing. Offensichtlich wird es normalerweise für 2D- oder 3D-Bereiche gemacht (wobei jeder Punkt zum Beispiel x- und y-Koordinaten hat), was mit einem sortierten Array nicht möglich ist. Ich nehme an, dass dies so ist, weil es zwar so effizient wie möglich ist, aber nicht so effizient ist wie ein Zeiger + Länge-Fenster in ein sortiertes Array zurückzugeben!

ich nicht den ganzen Algorithmus aus Wikipedia kopieren/einfügen gehen, nur um die clevere Idee:

Um die Punkte zu berichten, die im Intervall [x1, x2] liegt, beginnen wir von Suche für x1 und x2. Irgendscheitelpunkt in dem Baum, die Suchpfade zu x1 und x2 wird

abweichen Dies ist, wie effizient Sie ganze Teilbäume erfassen, die Sie wissen, wird in Ihrem Bereich, siehe wikipedia und/oder google „Baum Reichweitenabfrage "für viele Details.

Meine Pre-Googling-Beobachtung war, dass Sie Vergleiche vermeiden und nur einige Teilbäume gehen könnten. In Ihrem Beispiel ist der linke Teilbaum von 86 garantiert, dass alle in dem Bereich liegen, weil wir wissen, dass sie alle> 59 und < 86 sind, was eine engere Grenze als ist. Ich hatte nicht daran gedacht, nach diesem speziellen Fall zu suchen, der vielleicht nicht mehr Kosten verursachen würde, als er gespart hat.