Binärbaum
Ein Binärbaum (englisch binary tree) ist eine nichtlineare Datenstruktur, in der jeder Knoten (englisch node) höchstens zwei Nachfolger hat: einen linken und einen rechten Teilbaum.
Die deutschen Namen der Bestandteile:
| deutsch | englisch | was es ist |
|---|---|---|
| Wurzel | root | der oberste Knoten, über den man einsteigt |
| Knoten | node | ein Element des Baums |
| Blatt | leaf | ein Knoten ohne Nachfolger |
| Teilbaum | subtree | ein Knoten mit allem, was unter ihm hängt |
| Höhe | height | die Länge des längsten Weges von der Wurzel zu einem Blatt |
Der Baum steht in der Informatik auf dem Kopf: Die Wurzel ist oben, die Blätter sind unten.
Ein binärer Suchbaum (englisch binary search tree) ist ein Binärbaum mit einer zusätzlichen Ordnung: Links steht alles Kleinere, rechts alles Größere. Ein AVL-Baum hält sich zusätzlich selbst ausbalanciert.