Binärer Suchbaum
Kurz gesagt: Ein binärer Suchbaum hält in jedem Knoten die kleineren Werte links und die größeren rechts. Eine Suche kostet also so viel wie die Höhe des Baums, und ausbalancierte Bäume halten sie bei O(log n).
Problem
Der Preisindex kriecht
Der Filter „Preis von … bis …“ im Shop durchsucht einen Preisindex, nicht den ganzen Katalog. Der Index ist ein binärer Baum: Jeder Preis ist ein Knoten, die billigeren links, die teureren rechts. Bei 1000 gemischten Preisen hat der Baum 22 Ebenen, und das Schreiben und Nachschlagen aller Preise kostet zusammen 22.990 Vergleiche: etwa 23 pro Preis.
Heute Morgen hat der Lieferant das Format geändert: Der Feed kommt jetzt nach Preis sortiert. Dieselben 1000 Preise, derselbe Code, und die Vergleiche springen auf 1.000.000: 43-mal so viele. Der Baum hat jetzt 1000 Ebenen.
Warum spielt die Reihenfolge der Eingabe eine Rolle, wenn die Preise dieselben sind?
Die Idee
Kleineres nach links, Größeres nach rechts
Ein binärer Suchbaum (BST) besteht aus Knoten mit je zwei Verweisen, left und right. Es gibt eine einzige Regel: Alles im linken Teilbaum eines Knotens ist kleiner als er, alles im rechten Teilbaum ist größer.
Die Suche ist also eine binäre Suche ohne Array: An jedem Knoten vergleichst du und überspringst einen ganzen Teilbaum. Das Einfügen folgt demselben Weg, bis es eine leere Stelle erreicht, und hängt den neuen Knoten dort an. Nichts wird verschoben, anders als beim Einfügen in ein sortiertes Array.
boolean add(int price) { Node parent = null; Node cur = root; int level = 1; while (cur != null) { compares++; if (price == cur.price) return false; parent = cur; cur = price < cur.price ? cur.left : cur.right; level++; } Node node = new Node(price); if (parent == null) root = node; else if (price < parent.price) parent.left = node; else parent.right = node; size++; depth = Math.max(depth, level); return true;}boolean add(int price) { Node parent = null; Node cur = root; int level = 1; while (cur != null) { compares++; if (price == cur.price) return false; parent = cur; cur = price < cur.price ? cur.left : cur.right; level++; } Node node = new Node(price); if (parent == null) root = node; else if (price < parent.price) parent.left = node; else parent.right = node; size++; depth = Math.max(depth, level); return true;}List<Integer> sorted() { List<Integer> out = new ArrayList<>(); walk(root, out); return out;}
private void walk(Node node, List<Integer> out) { if (node == null) return; walk(node.left, out); out.add(node.price); walk(node.right, out);}Schritt für Schritt, in Worten
- Ein leerer Preisindex. Jeder Preis läuft von der Wurzel nach unten: Billigeres geht nach links, Teureres nach rechts.
- 49 kommt zuerst. Der Baum ist leer, also wird 49 zur Wurzel.
- 12 < 49: nach links. Dort ist es leer, also wird 12 das linke Kind von 49. 89 geht nach rechts.
- 24: billiger als 49 (links), teurer als 12 (rechts). Zwei Vergleiche, und es landet auf Ebene 3.
- 32: 49, 12, 24, dann nach rechts. Drei Vergleiche bei 7 Preisen: Jeder überspringt einen ganzen Teilbaum.
- walk: linker Teilbaum, der Knoten, rechter Teilbaum. Die Preise kommen sortiert heraus: 6 12 24 32 49 89 159.
Die Anzahl der Vergleiche ist die Anzahl der Ebenen auf dem Weg. Ist der Baum niedrig, mit etwa log₂ n Ebenen, dann ist jede Suche O(log n).
Sieh es dir an
Dein eigener Baum
Ein Knoten hält den Preis und die zwei Verweise:
class Node { int price; Node left; Node right;
Node(int price) { this.price = price; }}add geht von der Wurzel nach unten und merkt sich den letzten Knoten (parent). Sobald es eine leere Stelle erreicht, hängt es den neuen Knoten links oder rechts von parent an. Derselbe Preis kommt nicht zweimal hinein. level zählt die Ebenen auf dem Weg, damit der Baum weiß, wie tief er ist:
boolean add(int price) { Node parent = null; Node cur = root; int level = 1; while (cur != null) { compares++; if (price == cur.price) return false; parent = cur; cur = price < cur.price ? cur.left : cur.right; level++; } Node node = new Node(price); if (parent == null) root = node; else if (price < parent.price) parent.left = node; else parent.right = node; size++; depth = Math.max(depth, level); return true;}contains folgt demselben Weg, hängt aber nichts an:
boolean contains(int price) { Node cur = root; while (cur != null) { compares++; if (price == cur.price) return true; cur = price < cur.price ? cur.left : cur.right; } return false;}Der billigste Preis steht ganz links, der teuerste ganz rechts (der Baum ist nicht leer):
int min() { Node node = root; while (node.left != null) node = node.left; return node.price;}
int max() { Node node = root; while (node.right != null) node = node.right; return node.price;}Durchlauf in Reihenfolge: erst der linke Teilbaum, dann der Knoten, dann der rechte Teilbaum. So kommen die Preise sortiert heraus. Hier mit Rekursion, denn jeder Teilbaum ist wieder ein Baum:
List<Integer> sorted() { List<Integer> out = new ArrayList<>(); walk(root, out); return out;}
private void walk(Node node, List<Integer> out) { if (node == null) return; walk(node.left, out); out.add(node.price); walk(node.right, out);}PriceTree tree = new PriceTree();for (int price : new int[] { 49, 12, 89, 24, 6, 159, 32 }) { tree.add(price);}System.out.println("der Reihe nach: " + tree.sorted());System.out.println("am billigsten: " + tree.min() + ", am teuersten: " + tree.max());for (int price : new int[] { 32, 50 }) { tree.compares = 0; boolean found = tree.contains(price); System.out.println(price + ": " + (found ? "ja" : "nein") + ", Vergleiche: " + tree.compares);}der Reihe nach: [6, 12, 24, 32, 49, 89, 159]am billigsten: 6, am teuersten: 15932: ja, Vergleiche: 450: nein, Vergleiche: 232 wird mit 4 Vergleichen gefunden: 49, 12, 24, 32. Bei 50 reichen 2: 49, dann 89, und links von 89 ist nichts, also fehlt 50.
Probier es aus
Wie viele Vergleiche?
PriceTree tree = new PriceTree();for (int price : new int[] { 50, 30, 70, 20, 40, 60, 80 }) { tree.add(price);}tree.compares = 0;tree.contains(65);System.out.println(tree.compares);65 > 50: rechts, zur 70. 65 < 70: links, zur 60. 65 > 60: rechts, und diese Stelle ist leer. Drei Vergleiche, und 65 ist nicht da.
Probier es aus
Ergänze
Der billigste Preis:
int min() {
Node node = root;
while (node. != null) node = node.left;
return node.price;
}Kleinere Werte stehen links, also gehst du nach links, solange es geht. Der letzte Knoten ist der kleinste.
Die Idee
Sortierte Eingabe: Der Baum wird zur Kette
Zurück zum Feed. Kommen die Preise sortiert an, ist jeder neue teurer als alle bisherigen. Er geht an jedem Knoten nach rechts vorbei und hängt ganz rechts. Nie geht etwas nach links, und der Baum ist eine Kette: eine verkettete Liste mit nutzlosen leeren Verweisen.
boolean add(int price) { Node parent = null; Node cur = root; int level = 1; while (cur != null) { compares++; if (price == cur.price) return false; parent = cur; cur = price < cur.price ? cur.left : cur.right; level++; } Node node = new Node(price); if (parent == null) root = node; else if (price < parent.price) parent.left = node; else parent.right = node; size++; depth = Math.max(depth, level); return true;}Schritt für Schritt, in Worten
- Der Feed des Lieferanten schickt dieselben 7 Preise, aber sortiert: 6, 12, 24, 32, 49, 89, 159.
- Jeder neue Preis ist teurer als alle davor, also geht er immer nach rechts. Nach links geht nie etwas.
- Preis Nummer i läuft an allen i Preisen vor ihm vorbei: 0 + 1 + … + 6 = 21 Vergleiche. Der Baum ist eine Kette mit 7 Ebenen.
- contains(159) läuft durch alle 7 Knoten, wie bei einer verketteten Liste. Bei 1000 Preisen: 1000 Ebenen.
- Dieselben Preise, ausbalanciert: 3 Ebenen statt 7. AVL-Bäume und Rot-Schwarz-Bäume halten diese Form mit Rotationen.
Der Preis mit der Nummer i läuft an i Knoten vorbei. Bei n Preisen sind das 0 + 1 + … + (n − 1) beim Schreiben, und beim Suchen noch einmal so viel plus n: genau n² Vergleiche. Es ist dieselbe Falle wie beim schlechten Pivot von Quicksort: sortierte Eingabe und der schlechteste Fall.
Das Programm aus dem Problem: dieselben 1000 Preise, einmal sortiert, einmal gemischt:
static int[] shuffled(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = 100 + i; long x = 2026; for (int i = n - 1; i > 0; i--) { x = x * 48271 % 2147483647; int j = (int) (x % (i + 1)); int t = a[i]; a[i] = a[j]; a[j] = t; } return a;}
static String report(int[] prices) { PriceTree tree = new PriceTree(); for (int p : prices) tree.add(p); for (int p : prices) tree.contains(p); return "Tiefe " + tree.depth + ", Vergleiche " + tree.compares;}int[] feed = new int[1000];for (int i = 0; i < 1000; i++) feed[i] = 100 + i;System.out.println("aufsteigend: " + report(feed));System.out.println("gemischt: " + report(shuffled(1000)));aufsteigend: Tiefe 1000, Vergleiche 1000000gemischt: Tiefe 22, Vergleiche 22990Lass beide Eingaben im Browser laufen:
- Preise in gemischter Reihenfolge
O(n log n) - Preise in aufsteigender Reihenfolge
O(n²)
| Algorithmus | n = 10 | n = 1.000 | n = 5.000 | n = 100.000 |
|---|---|---|---|---|
| Preise in gemischter Reihenfolge | 56 | 22.990 | 157.880 | 4.029.826 |
| Preise in aufsteigender Reihenfolge | 100 | 1.000.000 | 25.000.000 | ≈ 10.000.000.000 |
Bei gemischter Eingabe läuft eine Suche im Durchschnitt durch etwa 2 · ln n − 3 Knoten (etwa 12 bei 1000 Preisen). Das wächst wie log n, und alles zusammen ist O(n log n). Bei sortierter Eingabe ist es O(n²): bei 1000 Preisen 1.000.000 Vergleiche gegen 22.990. Das ist der Unterschied zwischen dem durchschnittlichen und dem schlechtesten Fall, und echte Daten sind oft genau sortiert: nach Preis, nach Datum, nach Nummer.
Die Idee
Ein ausbalancierter Baum
Die Eingabe zu mischen hilft, aber das geht nicht immer: Die Preise kommen einzeln an, während der Shop läuft. Ein ausbalancierter Baum repariert sich selbst: Nach jedem Einfügen prüft er, ob ein Ast viel länger geworden ist als der andere, und ordnet ihn um. So bleibt die Höhe bei jeder Eingabe O(log n), und jede Suche, jedes Einfügen und jedes Entfernen ist O(log n).
Das Umordnen ist eine Rotation: Ein Knoten und sein Kind tauschen die Plätze. Bei einer Rechtsrotation wird das linke Kind zum Elternknoten, der alte Elternknoten wird sein rechtes Kind, und der rechte Teilbaum des Kindes wandert nach links vom alten Elternknoten. Die Regel „Kleineres nach links“ gilt weiter, und ein Ast wird um eine Ebene kürzer.
Genauer, für Neugierige
Eine Rechtsrotation um 32 in der Kette 32 → 24 → 12 (jeder ist das linke Kind des vorigen):
32 24 / / \ 24 → 12 32 / 1224 wird zur Wurzel, und 32 kommt rechts davon. Die sortierte Reihenfolge bleibt gleich: 12, 24, 32.
AVL (Adelson-Welski und Landis, 1962) speichert in jedem Knoten die Höhe des Teilbaums. Unterscheiden sich die Höhen der beiden Kinder um mehr als 1, macht er eine oder zwei Rotationen. Der Baum ist sehr niedrig (höchstens etwa 1,44 · log₂ n), die Suche ist also schnell, aber das Einfügen macht manchmal mehr Arbeit.
Ein Rot-Schwarz-Baum färbt seine Knoten und hält zwei Regeln ein: Ein roter Knoten hat kein rotes Kind, und jeder Weg von der Wurzel zu einer leeren Stelle geht durch gleich viele schwarze Knoten. Dadurch ist ein Ast höchstens doppelt so lang wie ein anderer, die Höhe also höchstens 2 · log₂ n. Beim Einfügen und Entfernen braucht es Umfärben und höchstens zwei oder drei Rotationen.
Was die Sprachen machen:
- Java:
TreeMapundTreeSetsind Rot-Schwarz-Bäume. Nebengetundputhaben sie die geordneten Operationen:firstKey,floorKey(der größte bis zu einem gegebenen Schlüssel),subMap(from, to). Sie ordnen nachComparableoder nach einemComparator, den du übergibst. - C#:
SortedSet<T>ist ein Rot-Schwarz-Baum, undSortedDictionary<TKey, TValue>ist darauf aufgebaut.SortedSethatMin,MaxundGetViewBetween(from, to). Vorsicht beiSortedList<TKey, TValue>: Das sind zwei sortierte Arrays, das Nachschlagen ist also O(log n), aber das Einfügen in der Mitte ist O(n). - Python: Es gibt keinen eingebauten ausbalancierten Baum. Das Modul
bisectdurchsucht eine sortierte Liste in O(log n), aberinsortfügt in O(n) ein, weil es die Elemente verschiebt. Das Paketsortedcontainers(SortedList,SortedDict) wird separat installiert und ist kein Baum: Es hält eine Liste sortierter Listen mit je etwa tausend Elementen. - JavaScript: Es gibt keinen eingebauten sortierten Baum.
MapundSetbehalten die Einfügereihenfolge, nicht die Reihenfolge nach Wert. Bleibt ein sortiertes Array mit binärer Suche oder eine Bibliothek.
Probier es aus
Finde den Fehler
Jemand hat add umgeschrieben. Fünf Preise gehen hinein, aber der Durchlauf zeigt nur einige davon, und die Suche findet 6 und 24 nicht:
boolean add(int price) { Node parent = null; Node cur = root; int level = 1; while (cur != null) { compares++; if (price == cur.price) return false; parent = cur; cur = price < cur.price ? cur.left : cur.right; level++; } Node node = new Node(price); if (parent == null) root = node; else if (price > parent.price) parent.left = node; else parent.right = node; size++; depth = Math.max(depth, level); return true;}PriceTree tree = new PriceTree();for (int price : new int[] { 49, 12, 89, 24, 6 }) { tree.add(price);}System.out.println("der Reihe nach: " + tree.sorted());System.out.println("6: " + (tree.contains(6) ? "ja" : "nein"));System.out.println("24: " + (tree.contains(24) ? "ja" : "nein"));der Reihe nach: [49, 6]6: nein24: neinIn welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Die Schleife geht richtig bis zur leeren Stelle nach unten, aber der Knoten wird auf der anderen Seite von parent angehängt: der größere links, der kleinere rechts. Dort kann schon ein Teilbaum hängen, der dann verloren geht, und selbst wenn die Stelle leer ist, sucht die nächste Suche auf der richtigen Seite und findet ihn nicht. Der Vergleich muss price < parent.price lauten, genau wie in der Schleife.
Übung
Ein Preis ist nicht mehr gültig
Löse diese Aufgabe in deinem eigenen Editor.
Aus dem Index entfernen. Füge remove(price) hinzu, das zurückgibt, ob es einen Preis entfernt hat. Es gibt drei Fälle:
- Der Knoten ist ein Blatt: einfach abhängen;
- er hat ein Kind: Das Kind nimmt seinen Platz ein;
- er hat zwei Kinder: Finde den nächstgrößeren Preis (den ganz linken im rechten Teilbaum), setze ihn an die Stelle des entfernten und entferne ihn aus dem rechten Teilbaum. Er hat kein linkes Kind, also ist das einer der ersten beiden Fälle.
Füge die Preise 49, 12, 89, 24, 6, 159, 32 ein und entferne 12 (zwei Kinder), 49 (die Wurzel, zwei Kinder) und 70 (fehlt):
-12: [6, 24, 32, 49, 89, 159]-49: [6, 24, 32, 89, 159]-70: keinerWurzel: 89Weitere Aufgaben
- Preise in einem Bereich. Schreibe
between(from, to), das die Preise vonfrombistoder Reihe nach zurückgibt, ohne den ganzen Baum zu durchlaufen: Geh von einem Knoten, der kleiner alsfromist, nicht nach links, und von einem Knoten, der größer alstoist, nicht nach rechts. - Das Beste im Budget. Schreibe
floor(budget): den teuersten Preis, der das Budget nicht überschreitet. Vergleiche mitfloorKeyin Java oderGetViewBetweenin C#. - Höhe mit Rekursion. Schreibe
height(node)als 1 plus die größere der beiden Höhen der Kinder. Lass es auf der Kette aus 1000 sortierten Preisen laufen. Was passiert in Python? Und mit 100.000 Preisen in Java?
Test