Höhere Datenstrukturen

Definition:
Ein ungerichteter Baum ist ein endlicher zusammenhängender azyklischer Graph.

Definition:
Ein gerichteter Baum ist ein gerichteter Graph mit folgenden Eigenschaften:
1. Es gibt genau einen Anfangsknoten, genannt Wurzel,
2. Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger,
3. Jeder Knoten (außer den Blättern) hat mindestens einen Nachfolger.

Definition:
Ein höhenbalancierter Baum (ausgeglichener Baum) ist ein gerichteter Baum dessen Blätter stets dieselbe Tiefe (bei abgeschwächten Bedingungen zumindest in derselben Ordnung) besitzen.

Definition:
Ein Schlüssel (Key) referenziert ein Datenelement. Schlüssel sind Elemente eines total geordneten Universums, also Zahlen oder lexikographisch geordnete Strings.