4.4 Range-Trees

Motivation (Folien 22–23)

Für großes $n$ und kleines $R$ ist die Anfragezeit $O(\sqrt n+R)$ des kd-Baums noch relativ groß. Range-Trees schaffen $O(\log^2 n + R)$, zahlen dafür aber mit mehr Speicher.

Prinzip	Vergleiche von $x$ und $y$ …
kd-Baum	… abwechselnd (pro Ebene eine andere Koordinate)
Range-Tree	… nacheinander (erst alle $x$, dann alle $y$)

Idee:

1. Erst $x$: Ein balancierter Suchbaum über den $x$-Koordinaten. Eine 1d-Bereichsanfrage auf $[x_l,x_r]$ liefert alle Kandidaten.
2. Dann $y$: Unter den Kandidaten per 1d-Bereichsanfrage die mit $y\in[y_l,y_r]$ heraussuchen.

Damit das schnell geht, dürfen die Kandidaten nicht einzeln aufgezählt werden (das wären evtl. $\Theta(n)$). Stattdessen kommen sie als wenige vorbereitete Teilmengen, für die es schon $y$-Suchbäume gibt.

4.4.1 1d-Bereichssuche (Folien 24–28)

Ausgangspunkt: ein balancierter, blattorientierter binärer Suchbaum. Die Punkte stehen in den Blättern, jeder innere Knoten $v$ speichert einen Schlüssel $x_v$ = größter Wert seines linken Teilbaums. Suche: bei $x\le x_v$ nach links, sonst nach rechts.

Idee: Nach $x_l$ und $x_r$ gleichzeitig suchen.

1. Den Knoten $v_\text{split}$ finden, an dem sich die Suchpfade zu $x_l$ und $x_r$ trennen.
2. Von $v_\text{split}$ dem Pfad zu $x_l$ folgen. Wo der Pfad nach links abbiegt, liegt der ganze rechte Teilbaum im Bereich → komplett ausgeben.
3. Von $v_\text{split}$ dem Pfad zu $x_r$ folgen. Wo der Pfad nach rechts abbiegt, liegt der ganze linke Teilbaum im Bereich → komplett ausgeben.
4. Die beiden Blätter am Ende der Pfade einzeln prüfen.

Algorithmus 3: FindSplitNode(T, xl, xr)
 1: v = Root(T);
 2: while (v ist kein Blatt && (xl > xv || xr ≤ xv)) {
 3:   if (xr ≤ xv) v = LeftChild(v);     // beide Pfade gehen nach links
 4:   else         v = RightChild(v);    // beide Pfade gehen nach rechts
 5: }
 6: return v;

Algorithmus 4: 1dRangeSearch(T, xl, xr)
 1: vsplit = FindSplitNode(T, xl, xr);
 2: if (vsplit ist Blatt) gib den Punkt aus, falls er in [xl, xr] liegt;
 3: else {
 4:   v = LeftChild(vsplit);             // Pfad zu xl
 5:   while (v ist kein Blatt) {
 6:     if (xl ≤ xv) {
 7:       ReportSubtree(RightChild(v));
 8:       v = LeftChild(v);
 9:     } else v = RightChild(v);
10:   }
11:   gib den Punkt in v aus, falls nötig;
12:   // analog mit RightChild(vsplit) und xr (gespiegelt)
13: }

Beispiel (eigenes, kleiner als auf Folie 24)

Blätter 3, 10, 19, 23, 30, 37, 49, 59. Innere Knoten tragen den größten Wert ihres linken Teilbaums:

                    23
           ┌────────┴────────┐
          10                 37
       ┌───┴───┐         ┌───┴───┐
       3       19        30      49
      / \     /  \      /  \    /  \
     3  10   19  23    30  37  49  59

Anfrage $[9, 37]$:

• Split-Knoten: Wurzel 23, denn $9\le23<37$.
• Pfad zu 9: Knoten 10: $9\le10$ → rechten Teilbaum $\{19,23\}$ ausgeben, nach links. Knoten 3: $9>3$ → nach rechts, Blatt 10 ∈ Bereich → ausgeben.
• Pfad zu 37: Knoten 37: $37\ge37$ → linken Teilbaum $\{30,37\}$ ausgeben, nach rechts. Knoten 49: $37<49$ → nach links, Blatt 49 ∉ Bereich.
• Ergebnis: 10, 19, 23, 30, 37 ✔

Satz 1 (Folie 28)

Satz 1

1d-Bereichssuche geht mit $O(n)$ Speicher, $O(n\log n)$ Vorverarbeitung und $O(R+\log n)$ pro Anfrage.

Beweis:

• Vorverarbeitung: Punkte in einem balancierten Suchbaum (z.B. AVL) speichern: Speicher $O(n)$, Aufbau $O(n\log n)$.
• Anfrage: $v_\text{split}$ finden und den zwei Pfaden folgen kostet $O(\log n)$, weil der Baum balanciert ist und pro Knoten $O(1)$ anfällt. ReportSubtree ist linear in der Zahl der ausgegebenen Punkte, zusammen $O(R)$ (ein Teilbaum mit $m$ Blättern hat $m-1$ innere Knoten). Gesamt $O(R+\log n)$. □

Wichtige Nebenbeobachtung: Die Antwort setzt sich aus $O(\log n)$ disjunkten Teilbäumen zusammen (höchstens einer pro Knoten auf den zwei Pfaden). Genau das nutzt der 2d-Range-Tree.

2d-Range-Tree (Folien 29–31)

Kanonische Teilmengen

Im $x$-Baum $T$ repräsentiert jeder Knoten $v$ die Punkte in den Blättern seines Teilbaums, die kanonische Teilmenge $P(v)$.

Eine 1d-Anfrage auf $[x_l,x_r]$ liefert das Ergebnis als Vereinigung von $O(\log n)$ kanonischen Teilmengen. Von diesen Punkten braucht man nur die mit $y\in[y_l,y_r]$. Also speichert man für jedes $P(v)$ schon einen $y$-Suchbaum.

Aufbau

• Hauptstruktur (first level): balancierter binärer Suchbaum $T$ über den $x$-Koordinaten.
• In jedem inneren Knoten $v$: ein balancierter binärer Suchbaum über den $y$-Koordinaten der Punkte in $P(v)$, die assoziierte Struktur $T_\text{assoc}(v)$ (second level). Ihre Blätter enthalten die Punkte.

Satz 2: Speicher und Aufbau

Satz 2

Ein Range-Tree für $n$ Punkte in 2d braucht $O(n\log n)$ Speicher und kann in $O(n\log n)$ aufgebaut werden.

Beweis:

• Speicher: Auf jeder Ebene von $T$ liegt jeder Punkt in genau einer assoziierten Struktur (die kanonischen Teilmengen einer Ebene sind disjunkt). Jede assoziierte Struktur braucht linearen Speicher, pro Ebene also $O(n)$. $T$ hat $O(\log n)$ Ebenen ⇒ $O(n\log n)$.
• Aufbau: Die Punkte einmal nach $x$ und einmal nach $y$ vorsortieren. Die Bäume dann von unten nach oben bauen: Die nach $y$ sortierte Liste eines Knotens entsteht durch Mischen (Merge) der Listen seiner Kinder in linearer Zeit. Aus einer sortierten Liste baut man einen balancierten Baum in $O(m)$. Pro Ebene $O(n)$, also insgesamt $O(n\log n)$. (Würde man jede assoziierte Struktur neu sortieren, käme man auf $O(n\log^2 n)$.) □

Anfrage

Algorithmus 5: 2dRangeSearch(T, [xl, xr] × [yl, yr])
 1: vsplit = FindSplitNode(T, xl, xr);
 2: if (vsplit ist Blatt) gib den Punkt aus, falls er im Bereich liegt;
 3: else {
 4:   v = LeftChild(vsplit);
 5:   while (v ist kein Blatt) {
 6:     if (xl ≤ xv) {
 7:       1dRangeSearch(Tassoc(RightChild(v)), yl, yr);   // statt ReportSubtree
 8:       v = LeftChild(v);
 9:     } else v = RightChild(v);
10:   }
11:   prüfe den Punkt in v;
12:   // analog mit RightChild(vsplit) und xr
13: }

Der einzige Unterschied zur 1d-Suche: Statt einen Teilbaum komplett auszugeben, fragt man dessen assoziierten $y$-Baum nach $[y_l,y_r]$ ab.

Satz 3: Anfragezeit (Folie 33)

Satz 3

Eine Anfrage in einem Range-Tree mit $n$ Punkten in 2d kostet $O(R+\log^2 n)$.

Beweis:

• Jeder Aufruf von 1dRangeSearch in einem Knoten $v$ kostet $O(R_v+\log n)$, mit $R_v$ = Anzahl der Punkte in $D\cap P(v)$. Weil die kanonischen Teilmengen disjunkt sind, gilt $\sum R_v = R$.
• Aufgerufen wird nur an Knoten auf den beiden Suchpfaden, das sind $O(\log n)$ Stück.
• Also $\sum_v O(R_v+\log n) = O(R + \log n\cdot\log n) = O(R+\log^2 n)$. □

Höhere Dimensionen (Folie 34)

Rekursiv: Die assoziierte Struktur eines $k$-dimensionalen Range-Trees ist ein $(k-1)$-dimensionaler Range-Tree über den restlichen Koordinaten.

	$k$d-Range-Tree
Aufbau	$O(n\log^{k-1} n)$
Anfrage	$O(R+\log^k n)$
Speicher	$O(n\log^{k-1} n)$

Jede zusätzliche Dimension kostet einen Faktor $\log n$ bei allen drei Größen.

Vergleich (Folie 35)

	kd-Baum 2d	kd-Baum $k$d	Range-Tree 2d	Range-Tree $k$d
Speicher	$O(n)$	$O(n)$	$O(n\log n)$	$O(n\log^{k-1}n)$
Aufbau	$O(n\log n)$	$O(k\,n\log n)$	$O(n\log n)$	$O(n\log^{k-1}n)$
Anfrage	$O(R+\sqrt n)$	$O(R+k\,n^{1-1/k})$	$O(R+\log^2 n)$	$O(R+\log^k n)$

Faustregel:

• Wenig Speicher, einfache Implementierung, auch für Nächste-Nachbarn → kd-Baum.
• Sehr viele Anfragen, kleines $R$, Speicher egal → Range-Tree.

Fractional Cascading (Ergänzung, nicht auf den Folien)

Die $O(\log n)$ assoziierten Suchen fragen alle dasselbe Intervall $[y_l,y_r]$ ab. Ersetzt man die assoziierten Bäume durch sortierte Arrays und speichert in jedem Eintrag einen Zeiger auf die passende Position im Array des Kindes, muss man nur einmal binär suchen und kann danach den Zeigern folgen. Das senkt die Anfragezeit auf $O(R+\log n)$ in 2d (allgemein $O(R+\log^{k-1}n)$).