Baum (Datenstruktur)

Kurz: Ein Baum ist eine hierarchische Datenstruktur aus Knoten, die über Kanten verbunden sind: Ein Wurzelknoten hat Kinder, diese wieder Kinder – ohne Kreise.

Genauer: Bäume bilden Hierarchien ab: Dateisysteme, HTML-Dokumente (DOM), Organigramme und Entscheidungen. Der binäre Suchbaum speichert Werte so, dass links nur kleinere und rechts nur größere Werte hängen – dadurch lässt sich in O(log n) suchen, solange er ausgeglichen ist.

Im Detail

Begriffe

• Wurzel: oberster Knoten; Blatt: Knoten ohne Kinder; Höhe: längster Weg von der Wurzel zu einem Blatt.
• Binärbaum: jeder Knoten hat höchstens zwei Kinder.
• Binärer Suchbaum: links < Knoten < rechts.
• Ausgeglichen (AVL-, Rot-Schwarz-Baum): Die Höhe bleibt klein, damit Suche, Einfügen und Löschen O(log n) bleiben.
• Weitere Arten: Heap (für Prioritätswarteschlangen), Trie (Präfixbaum für Wörterbücher), B-Baum (Datenbanken und Dateisysteme).

class Knoten:
    def __init__(self, wert):
        self.wert = wert
        self.links = None
        self.rechts = None
 
def einfuegen(knoten, wert):
    if knoten is None:
        return Knoten(wert)
    if wert < knoten.wert:
        knoten.links = einfuegen(knoten.links, wert)
    elif wert > knoten.wert:
        knoten.rechts = einfuegen(knoten.rechts, wert)
    return knoten
 
def in_reihenfolge(knoten):             # sortierte Ausgabe
    if knoten is None:
        return []
    return in_reihenfolge(knoten.links) + [knoten.wert] + in_reihenfolge(knoten.rechts)
 
wurzel = None
for z in [5, 3, 8, 1, 4, 7, 9]:
    wurzel = einfuegen(wurzel, z)
print(in_reihenfolge(wurzel))           # [1, 3, 4, 5, 7, 8, 9]

Durchlaufen

Die Tiefensuche geht erst in die Tiefe (mit Rekursion oder einem Stack); die Breitensuche besucht Ebene für Ebene (mit einer Queue). Beim Binärbaum unterscheidet man Pre-, In- und Post-Order. Ein Baum ist ein Spezialfall des Graphen.

Siehe auch: Graph, Rekursion, Datenstrukturen, Big-O-Notation