Priorität Recherche Baum Verwirrung

Question

Die einzige vernünftige Dia Satz fand ich this ist, die 15 in Seite sagt, für den Bau:

• sortieren alle Punkte durch ihre x-Koordinatenwert und speichert sie in den Blattknoten eines ausgeglichenen Binärbaums (dh eines Bereichsbaums)
• Beginnend an der Wurzel enthält jeder Knoten den Punkt in seinem Teilbaum mit dem Maximalwert für seine y-Koordinate, die nicht
  in einer flacheren Tiefe im Baum gespeichert wurde ; wenn kein solcher Knoten vorhanden ist, dann Knoten
  leer

ich einen Range-Baum implementiert just before, so am Beispiel ich dort verwendet, ich habe jetzt (für eine Priorität Recherche Baum):

Hier

       7 
         ------ 0 --------------------- 
         |       | 
         6       6 
       ---- -3 ----     ---- 4 ------ 
       |   |     |   | 
       4   2     1   3 
      ---- -4 -  -2    --- 3 ---  5 
      |  |  /\    |  | /\ 
      0 (-3,4) (-2,2)(0,7)  NIL (4,-4) (5,3)(6,-1) 
     -5        2  
     /\       /\ 
    (-5,6) (-4,0)     (2,1) (3,6) 

ist jeder innere Knoten der Form:

mid_x 
max y 

und die Bereichsabfrage, die ich vorstelle, ist (-inf, 1) x (-0,5, 5), d. H. (X_low, x_high) x (y_low, y_high).

1. So lassen Sie sich von der Wurzel beginnen, ich überprüfen, ob x (= 0) in (-inf, 1) und wenn 7> (-0,5, 5). Es ist, so gehe ich bei beiden Kindern vor, aber für Einfachheit, lassen Sie mich dem linken folgen (in allen Fällen von jetzt an).
2. Ich überprüfe, ob -3 ist der x-Bereich und wenn 6 ist mehr oder gleich als obere Grenze des y-Bereichs der Abfrage (d. H. 5). Es ist so, dass ich weiter mache.
3. Das gleiche für die nächste Ebene, also gehen wir auf die nächste Ebene und jetzt bitte auf diesen inneren Knoten konzentrieren. Es hat als max y eine 0, was anzeigt, dass die maximale y des Unterbaums 0 ist, was falsch ist (linkes Kind ist (-5, 6)) ^*.

Was fehlt mir beim Bau/Suchvorgang?

---

Mit anderen Worten:

Überprüfen Sie den äußersten linken Zweig des Baumes; Es hat als max_y Werte (2. Aufzählungszeichen in der Quote), 7, 6, 4, 0.

Aber ist das nicht der Wert, der den maximalen y-Wert im Teilbaum unter dem inneren Knoten gespeichert angezeigt? Wenn ja, gilt dies nicht für 0 und Punkt (-5, 6) (6 wird nicht verwendet, da es in der 2. Ebene verwendet wird).

---

* _{Die besondere Abfrage könnte ich bin aufwirft nicht durch die beschädigt werden, aber eine andere Dose.}

Answer 1

Sie letzte Logik ist eigentlich noch richtig. Der Wert (-5,6) sollte bereits aufgenommen worden sein, wenn Sie auf den von Ihnen markierten Knoten treffen (6, -3). Nun, ich bin kein Mathe-Major. Aber die allgemeine Idee ist dies. In der Struktur der Prioritätssuche, die Sie implementiert haben, suchen Sie tatsächlich nach zwei separaten Kriterien. Für x ist es eine einfache binäre Suche nach dem Bereich. Für y, Sie suchen tatsächlich nach ihr als Priorität Baum (gut für die Suche von y: inf oder -inf: y, je nachdem, ob Sie Max oder Min verwenden.)

Beachten Sie, dass am unteren Rand Seite 15 besagt, dass der Baum für einen semi-unendlichen Bereich (einer ist unendlich) gut ist. Lesen Sie weiter, Sie werden sehen, wie der Baum für den semi-unendlichen Bereich für y optimiert ist.

Kurz gesagt, da Ihr Baum mit x als binäre Suche und y als Priorität (mit max Restwert) konstruiert wird, ist die optimale Suche [x1: x2], [y1: inf].

Jeder Knoten im Baum speichert im Wesentlichen 2 Dinge. 1. Der Mittelpunkt von x (oder das Max-x im linken Baum und die Entscheidung, nach links oder rechts zu gehen, basiert auf der Prüfung> x). 2. Der POINT mit dem höchsten y-Wert im Teilbaum, der nicht zum vorherigen hinzugefügt wurde.

Der Suchalgorithmus läuft im Wesentlichen so. Ausgehend von der Wurzel mit einem Kriterium von [x1: x2], [y1: inf] 1. Überprüfen Sie den y-Wert des POINT, der dem Knoten zugewiesen ist. Wenn y> y1, gehe zu 2, ansonsten STOPP (da der dem Knoten zugewiesene POINT den höchsten y-Wert hat, wenn der Check fehlgeschlagen ist, gibt es keinen anderen Knoten darunter, der [y1: inf] erfüllen kann. 2. Überprüfen Sie, ob der x-Wert des Punktes im Bereich von [x1: x2] liegt. Wenn dies der Fall ist, fügen Sie diesen Punkt in den Ausgang ein. Fahren Sie mit Schritt 3 fort, unabhängig davon, ob Sie diesen Punkt eingefügt haben "Wert (lasst uns das mx nennen.) Wenn mx im Bereich von [x1: x2] ist, gehe beide Pfade durch. Wenn mx < [x1: x2] ist, traverse nach links. Ansonsten traverse nach rechts. Gehe zurück zu Schritt 1 für jeden

EDIT für sehr, SEHR langen Text: Lassen Sie uns durch Ihr Beispiel laufen .. Ich habe eine zusätzliche Anmerkung markiert jeden Punkt mit Buchstaben (der "Name" des Punktes. Jeder Knoten haben jetzt das Format des Namens des Punktes, mit seinem y-Wert in der Elternschaft, und dem "mid-range" x darunter. Für die Blattknoten bedeuten solche mit einem '*', dass sie bereits irgendwo im Baum stehen und als NIL behandelt werden, wenn Sie sie jemals erreichen.

       7(E) 
         ------ 0 --------------------- 
         |       | 
         A(6)       G(6) 
       ----- -3 -----     ---- 4 -------- 
       |   |     |    | 
       C(4)  D(2)    F(1)   I(3) 
      ---- -4 -   -2    --- 3 ---   5 
      |  |  /\    |  |  /\ 
      B(0) C*(-3,4)D*(-2,2)E*(0,7)  NIL H(4,-4) I*(5,3)J(6,-1) 
      -5         2 
     /\        /\ 
    A*(-5,6)B*(-4,0)     F*(2,1) G*(3,6) 

Nehmen wir ein Beispiel Abfrage des Laufes [-2: 4] [1: inf] (oder eine beliebige y> = 1)

• von der Wurzel ausgehend sehen wir Punkt E.
• Ist das y von Punkt E (7)> ​​= 1? Ja.
• Ist das x von Punkt E (0) in [-2: 4]? Ja
• Fügen Sie E zur Ausgabe hinzu.
• Ist der Mittelpunkt (auch 0) in Reichweite? Ja
• Vom Knoten mit E müssen beide Seiten durchlaufen werden.
• Zuerst gehen wir nach links, wir sehen Punkt A.
• Ist das y von Punkt A (6)> = 1? Ja.
• Ist das x von Punkt A (-5) in [-2: 4]?
• Überspringen Sie A, aber fahren Sie weiter (nur die y-Prüfung stoppt die Traversierung).
• Liegt der Mittelpunkt bei A im Bereich von [-2: 4]? Nein, es ist auf der linken Seite.
• Seit -3 < [-2: 4] müssen wir nur noch nach rechts gehen. Jetzt sehen wir Punkt D.
• Ist das y von Punkt D (2)> = 1? Nein! Überspringe den Punkt und höre auf, abwärts zu fahren, da es keinen anderen Punkt unter D gibt, den wir NICHT ausgegeben haben (beachte, dass E bereits ausgegeben wird, wenn wir root am Anfang besucht haben).
• Ich fahre bis zu A, da wir den linken Pfad nicht überqueren müssen, weiter nach oben.
• Jetzt bin ich wieder bei root, die beide durchlaufen haben müssen. Da wir gerade nach links gegangen sind, gehen wir nach rechts. Dort sehen wir Punkt G
• Ist das y von Punkt G (6)> = 1? Ja
• Ist das x von Punkt G (3) in [-2: 4]? Ja
• Fügen Sie G zur Ausgabe hinzu, jetzt haben wir (E, G).
• Ist der Mittelpunkt bei G in Reichweite? Ja, wir müssen beide Seiten durchqueren.
• Lassen Sie uns zuerst links gehen. Wir sehen F.
• Ist das y von Punkt F (1)> = 1? Ja
• Ist das x von Punkt F (2) in [-2: 4]? Ja
• Fügen Sie F zur Ausgabe hinzu, jetzt haben wir (E, F, G)
• Ist der Mittelpunkt bei F in [-2: 4]? Ja, wir müssen beide Seiten durchqueren.
• Lassen Sie uns zuerst wieder links gehen, wir sehen ... NIL. Es müssen keine weiteren Punkte hinzugefügt werden (da wir bereits F, G überprüft/hinzugefügt haben).
• Lassen Sie uns zurück nach F gehen und auf der rechten Seite fahren, wir sehen H.
• Ist das y von Punkt H (-4)> = 1? Nein. Fügen Sie den Punkt nicht hinzu und hören Sie auf zu verfahren.
• Wir gehen zurück nach F, wo bereits beide Wege abgefahren sind.
• Wir gehen zurück zu G, die immer noch ihren richtigen Weg braucht.
• Wir durchlaufen den rechten Pfad und siehe I.
• Ist das y von Punkt I (3)> = 1? Ja
• Ist das x von Punkt I (5) in [-2: 4]? Nr.
• Skip F.
• Liegt der Mittelpunkt bei I im Bereich von [-2,4]? Nein, es ist größer.
• Da es größer ist, müssen wir nur die linke Seite durchlaufen, also machen wir das.
• Traverse auf der linken Seite sehen wir ... Ich wieder. Da wir bereits I gesehen haben und es ein Blattknoten ist, hören wir auf zu verfahren und gehen wieder auf I.
• Ich bin fertig (muss nicht nach rechts verfahren). Geh zurück nach G.
• G ist fertig (beide Seiten durchquert). Geh zurück nach E.
• E ist fertig (beide Seiten durchquert). Da E der Wurzelknoten ist, sind wir jetzt fertig.

Das Ergebnis ist "E, F, G" sind in Reichweite.