Algorithmen und Datenstrukturen · Kapitel 7
Bäume und Heaps
Listen, Stacks und Queues ordnen Daten in einer Reihe an. Ein Baum verzweigt sich: Jeder Knoten kann mehrere Nachfolger haben. So lässt sich in einem gut gebauten Suchbaum ein Wert in wenigen Schritten finden, und ein Heap liefert das kleinste Element sofort. Fast jede Methode auf Bäumen ist rekursiv, denn jeder Teil eines Baums ist selbst wieder ein Baum.
Begriffe
In einem Binärbaum hat jeder Knoten höchstens zwei Kinder, ein linkes und ein rechtes. In den Aufgaben sieht ein Knoten so aus:
class TreeNode { int value; TreeNode left; TreeNode right;}- Die Wurzel ist der oberste Knoten, der einzige ohne Elternknoten. Über sie erreichst du den ganzen Baum.
- Ein Blatt hat keine Kinder:
leftundrightsindnull. Alle anderen Knoten heißen innere Knoten. - Ein Teilbaum ist ein Knoten mit allem, was darunter hängt. Der linke Teilbaum der Wurzel ist also selbst ein Baum.
- Die Höhe zählt hier die Ebenen: Ein einzelner Knoten hat die Höhe 1, ein leerer Baum die Höhe 0. Manche Bücher zählen stattdessen die Kanten, dann ist alles um 1 kleiner.
Rekursion und Traversierung
Eine Methode auf einem Baum folgt fast immer demselben Muster: Abbruchfall ist der leere Baum (node == null), sonst verarbeitest du den Knoten und rufst dich für node.left und node.right auf. Jeder Knoten wird genau einmal besucht, das kostet O(n).
Wer alle Knoten besucht, traversiert den Baum. Die drei üblichen Reihenfolgen unterscheiden sich nur darin, wann der Knoten selbst drankommt:
- Preorder: Knoten, links, rechts. Die Wurzel steht vorn.
- Inorder: links, Knoten, rechts. Die Wurzel steht in der Mitte.
- Postorder: links, rechts, Knoten. Die Wurzel steht hinten.
public class Main { static int countNodes(TreeNode node) { if (node == null) { return 0; } return 1 + countNodes(node.left) + countNodes(node.right); }
static int height(TreeNode node) { if (node == null) { return 0; } return 1 + Math.max(height(node.left), height(node.right)); }
static void preorder(TreeNode node) { if (node == null) { return; } System.out.print(node.value + " "); preorder(node.left); preorder(node.right); }
static void inorder(TreeNode node) { if (node == null) { return; } inorder(node.left); System.out.print(node.value + " "); inorder(node.right); }
static void postorder(TreeNode node) { if (node == null) { return; } postorder(node.left); postorder(node.right); System.out.print(node.value + " "); }
public static void main(String[] args) { // 1 // / \ // 2 3 // / \ // 4 5 TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3)); System.out.println("Nodes: " + countNodes(root)); System.out.println("Height: " + height(root)); System.out.print("Preorder: "); preorder(root); System.out.println(); System.out.print("Inorder: "); inorder(root); System.out.println(); System.out.print("Postorder: "); postorder(root); System.out.println(); }}
class TreeNode { int value; TreeNode left; TreeNode right;
TreeNode(int value) { this.value = value; }
TreeNode(int value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; }}Für den Baum im Beispiel ergibt das 1 2 4 5 3, 4 2 5 1 3 und 4 5 2 3 1. In der Klausur hilft es, den Baum aufzuzeichnen und jeden Knoten beim Besuch abzuhaken.
Binäre Suchbäume
Ein binärer Suchbaum ordnet die Werte: Für jeden Knoten sind alle Werte im linken Teilbaum kleiner, alle im rechten größer. Beim Suchen vergleichst du mit dem Knoten und gehst nach links oder rechts, ganz wie bei der binären Suche im Array. Eingefügt wird an der Stelle, an der die Suche auf null stößt.
- Der kleinste Wert steht ganz links unten, der größte ganz rechts unten.
- Inorder liefert die Werte sortiert.
- Suchen und Einfügen brauchen so viele Schritte, wie der Baum hoch ist. Ist er ausgeglichen, sind das etwa log₂ n, also O(log n): 1 000 000 Werte in rund 20 Ebenen.
- Fügst du schon sortierte Werte ein (1, 2, 3, …), hängt jeder neue Knoten rechts am vorigen. Der Baum entartet zur Liste, Suchen kostet dann O(n). Selbst ausgleichende Bäume (AVL, Rot-Schwarz, in Java
TreeMap) verhindern das.
public class Main { static TreeNode insert(TreeNode root, int value) { if (root == null) { return new TreeNode(value); } if (value < root.value) { root.left = insert(root.left, value); } else if (value > root.value) { root.right = insert(root.right, value); } return root; }
static boolean contains(TreeNode root, int value) { TreeNode node = root; while (node != null) { if (value == node.value) { return true; } node = value < node.value ? node.left : node.right; } return false; }
static int min(TreeNode root) { TreeNode node = root; while (node.left != null) { node = node.left; } return node.value; }
static void inorder(TreeNode node) { if (node == null) { return; } inorder(node.left); System.out.print(node.value + " "); inorder(node.right); }
public static void main(String[] args) { TreeNode root = null; for (int v : new int[] {50, 30, 70, 20, 40, 60, 80}) { root = insert(root, v); } System.out.println("contains 40? " + contains(root, 40)); System.out.println("contains 45? " + contains(root, 45)); System.out.println("min: " + min(root)); System.out.print("sorted: "); inorder(root); System.out.println(); }}
class TreeNode { int value; TreeNode left; TreeNode right;
TreeNode(int value) { this.value = value; }}Heaps im Array
Ein Min-Heap ist ein Binärbaum mit der Heap-Eigenschaft: Jeder Knoten ist kleiner oder gleich seinen Kindern. Das Minimum steht also immer in der Wurzel. Anders als im Suchbaum sind die Geschwister untereinander nicht geordnet.
Ein Heap ist immer vollständig, Ebene für Ebene von links aufgefüllt. Deshalb passt er ohne Lücken in ein Array:
- Wurzel an Index 0
- Kinder von
i:2 * i + 1und2 * i + 2 - Elternknoten von
i:(i - 1) / 2(Ganzzahldivision)
Einfügen: hinten anhängen und aufsteigen lassen, solange der Wert kleiner als sein Elternknoten ist. Minimum entnehmen: das letzte Element an Index 0 setzen und absinken lassen, immer mit dem kleineren Kind tauschen. Beides läuft höchstens einmal von oben nach unten durch den Baum: O(log n). Java bietet das fertig als PriorityQueue.
import java.util.Arrays;
public class Main { static int[] data = new int[10]; static int size = 0;
static void insert(int value) { data[size] = value; int i = size; size++; // sift up: swap with the parent while smaller while (i > 0 && data[i] < data[(i - 1) / 2]) { swap(i, (i - 1) / 2); i = (i - 1) / 2; } }
static int poll() { int min = data[0]; size--; data[0] = data[size]; int i = 0; // sift down: swap with the smaller child while larger while (2 * i + 1 < size) { int child = 2 * i + 1; if (child + 1 < size && data[child + 1] < data[child]) { child++; } if (data[i] <= data[child]) { break; } swap(i, child); i = child; } return min; }
static void swap(int i, int j) { int tmp = data[i]; data[i] = data[j]; data[j] = tmp; }
public static void main(String[] args) { for (int v : new int[] {5, 3, 8, 1, 4}) { insert(v); System.out.println("insert " + v + ": " + Arrays.toString(Arrays.copyOf(data, size))); } System.out.println("poll: " + poll()); System.out.println("heap: " + Arrays.toString(Arrays.copyOf(data, size))); }}Heapsort
Heapsort sortiert mit einem Max-Heap direkt im Array:
- Heap aufbauen: Von
a.length / 2 - 1bis 0 lässt du jeden inneren Knoten absinken. Danach steht das Maximum an Index 0. - Das Maximum mit dem letzten Element des Heaps tauschen. Es steht jetzt an seinem endgültigen Platz, der Heap ist ein Element kürzer. Die neue Wurzel absinken lassen und wiederholen.
Jedes Absinken kostet O(log n), und das passiert n-mal: O(n log n), auch im schlechtesten Fall. Anders als Quicksort braucht Heapsort keinen Zusatzspeicher und hat keinen schlechten Fall mit O(n²). Dafür ist er nicht stabil: Gleiche Werte können ihre Reihenfolge tauschen.
import java.util.Arrays;
public class Main { static void heapSort(int[] a) { // 1. build a max-heap: let every inner node sink, from back to front for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); } // 2. move the maximum to the end, shrink the heap, repair it for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, end); } }
static void siftDown(int[] a, int i, int size) { while (2 * i + 1 < size) { int child = 2 * i + 1; if (child + 1 < size && a[child + 1] > a[child]) { child++; } if (a[i] >= a[child]) { return; } swap(a, i, child); i = child; } }
static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
public static void main(String[] args) { int[] a = {4, 10, 3, 5, 1}; heapSort(a); System.out.println(Arrays.toString(a)); }}Typische Fehler
Rekursiven Aufruf nicht eingehängt
insert(root.left, value);allein erzeugt zwar einen neuen Knoten, aber niemand merkt ihn sich. Richtig istroot.left = insert(root.left, value);. Genauso beim ersten Einfügen in einen leeren Baum:root = insert(root, 5);, sonst bleibtrootnull.Suchbaum nur mit den Kindern geprüft
Dass jedes linke Kind kleiner und jedes rechte größer ist, reicht nicht. Im Baum mit Wurzel 8, linkem Kind 3 und dessen rechtem Kind 9 passt jedes Paar, trotzdem steht die 9 im linken Teilbaum der 8. Prüfe jeden Knoten gegen eine untere und obere Grenze, die du beim Abstieg mitgibst.
Falsche Indizes im Heap
Mit der Wurzel an Index 0 sind die Kinder
2 * i + 1und2 * i + 2. Die Formeln2 * iund2 * i + 1gelten nur, wenn die Wurzel an Index 1 steht. Und beim Absinken gibt es ein Kind nur, wenn sein Index kleiner alssizeist, nicht kleiner alsdata.length: Dahinter stehen alte Werte.