Binärbaum

Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt. Oft wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen. Ein anschauliches Beispiel für einen solchen Binärbaum ist die Ahnentafel. Hierbei sind allerdings die Elternteile die Kindknoten.

Ein Binärbaum ist entweder leer, oder er besteht aus einer Wurzel mit einem linken und rechten Teilbaum, die wiederum Binärbäume sind.

Weitere Begriffe

Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwa nur ein rechtes Kind), sowie der linke Knoten kleiner, der rechte Knoten größer als der Betrachtungsknoten ist. Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt), oder aber zwei (also sowohl ein linkes wie ein rechtes) Kinder besitzt. Für die Eigenschaft voll werden gelegentlich auch die Begriffe saturiert oder strikt verwendet. Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe haben, wobei die Tiefe hier als die Anzahl übergeordneter Knoten definiert sei^[1]. Beispiel: Ein Baum, der nur aus der Wurzel besteht, hat die Höhe 0.

Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe h, den man häufig auch als B_h bezeichnet, genau

2^h+1-1 Knoten,
2^h-1 innere Knoten (Knoten, die keine Blätter sind),
2ⁱ Knoten in Tiefe i ^[1], insbesondere also
2^h Blätter

besitzt, wobei mit Höhe h die Länge des Pfades zu einem tiefsten Knoten bezeichnet wird. Eine Darstellung eines Binärbaumes, in dem die Knoten mit rechtwinkligen Dreiecken und die Kanten mit Rechtecken dargestellt werden, nennt man pythagoreischen Binärbaum.

Der Binärbaum ist entartet, wenn jeder Knoten entweder Blatt ist (Anzahl Kinder ist 0) oder nur ein Kind besitzt („Halb-Blatt“). In diesem Fall stellt der Baum eine Liste dar. Besondere Formen sind die geordneten Listen, bei denen ein Baum jeweils nur aus linken oder nur aus rechten Kindern besteht.

Anwendungen

Viele Datenstrukturen wie beispielsweise binäre Suchbäume, AVL-Bäume, Fibonacci-Bäume und binäre Heaps basieren auf Binärbäumen.

Einige spezielle Binärbäume

Partiell geordneter Baum

Ein partiell geordneter Baum T ist ein spezieller Baum,

dessen Knoten markiert sind
dessen Markierungen aus einem geordneten Wertebereich stammen
in dem für jeden Teilbaum T' mit der Wurzel x gilt: Alle Knoten aus T' sind größer markiert als x oder gleich x.

Intuitiv bedeutet dies: Die Wurzel jedes Teilbaumes stellt ein Minimum für diesen Teilbaum dar. Die Werte des Teilbaumes nehmen in Richtung der Blätter zu oder bleiben gleich.

Derartige Bäume werden häufig in Heaps verwendet.

Vollständig balancierter Binärbaum

Ein vollständig balancierter Binärbaum ist ein voller Binärbaum, bei dem die Abstände zweier beliebiger Blätter von der Wurzel um höchstens 1 voneinander abweichen. (Siehe auch Balancierter Baum oder AVL-Baum.)

Suchen per Index

Wird in jedem Knoten die Anzahl der Elemente in dem ihm zugehörigen Unterbaum gehalten, kann das Aufsuchen eines Elements vermöge seines in-order-Index in ganz ähnlicher Weise wie das Aufsuchen mit einem Schlüssel im binären Suchbaum bewerkstelligt werden – mit der nachteiligen Implikation, dass Einfüge- und Entfernoperation immer Korrekturen bis hinauf zur Wurzel erfordern.

Der Aufwand ist O(h), wo h die Höhe des Baums ist.

Traversierung

Traversierung bezeichnet das Untersuchen der Knoten des Baumes in einer bestimmten Reihenfolge. Ein Spezialfall ist die Linearisierung, bei der die Elemente in der Reihenfolge der Traversierung in eine Liste eingefügt werden.

Es gibt verschiedene Möglichkeiten, die Knoten von Binärbäumen zu durchlaufen. Man unterscheidet:

pre-order oder Hauptreihenfolge (W–L–R): wobei zuerst die Wurzel (W) betrachtet wird und anschließend zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird,

in-order oder symmetrische Reihenfolge (L–W–R): wobei zuerst der linke (L) Teilbaum durchlaufen wird, dann die Wurzel (W) betrachtet wird und anschließend der rechte (R) Teilbaum durchlaufen wird,
reverse in-order (R–W–L): wobei zuerst der rechte (R) Teilbaum durchlaufen wird, dann die Wurzel (W) betrachtet wird und anschließend der linke (L) Teilbaum durchlaufen wird und
post-order oder Nebenreihenfolge (L–R–W): wobei zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird und anschließend die Wurzel (W) betrachtet wird.
level-order: Beginnend bei der Wurzel, werden die Ebenen von links nach rechts durchlaufen. (Breitensuche)

Rekursive Implementierungen

preOrder( knoten ):

    print( knoten )

    if knoten.links ≠ null then
        preOrder( knoten.links )

    if knoten.rechts ≠ null then
        preOrder( knoten.rechts )

inOrder( knoten ):

    if knoten.links ≠ null then
        inOrder( knoten.links )

    print( knoten )

    if knoten.rechts ≠ null then
        inOrder( knoten.rechts )

postOrder( knoten ):

    if knoten.links ≠ null then
        postOrder( knoten.links )

    if knoten.rechts ≠ null then
        postOrder( knoten.rechts )

    print( knoten )

Eine Traverse über den ganzen Baum umfasst pro Kante einen Abstieg und einen Aufstieg. Der Aufwand bei n Knoten ist also $2\cdot n\in {\mathcal {O}}\left(n\right)$ .

Iterative Implementierung

Implementierungen, die nur einen einzelnen Querungs-Schritt vollziehen, sind in der Praxis fast noch wichtiger. Sie ermöglichen, Anfang und Ende der Traverse in einer Programmschleife direkt auszuprogrammieren.

Als Beispiel sei hier nur die in-order-Traverse gezeigt, die insbesondere bei binären Suchbäumen eine große Rolle spielt, da diese Reihenfolge der Sortier-Reihenfolge entspricht.

inOrderNext( knoten, richtung ):
    // richtung  =  Links („in-order“)  oder  Rechts („reverse in-order“)

    knotenY = knoten.kind[richtung]         // 1 Schritt in die gegebene Richtung
    if knotenY ≠ null then {
        richtung = 1 - richtung             // spiegele  Links <-> Rechts
        // Abstieg zu den Blättern über Kinder in der gespiegelten Richtung
        knotenZ = knotenY.kind[richtung]
        while knotenZ ≠ null {
            knotenY = knotenZ 
            knotenZ = knotenY.kind[richtung]
        } 
        return knotenY
    }
    // Aufstieg zur Wurzel über Vorfahren der gegebenen Richtung
    knotenY = knoten
    do {
        knotenZ = knotenY
        knotenY = knotenZ.vater
        if knotenY = null return knotenY   // (knotenZ ist die Wurzel:)
                               // ==> es gibt kein Element mehr in dieser Richtung
    } until knotenZ ≠ knotenY.kind[richtung]
    // knotenY ist der erste Vorfahr in der gespiegelten Richtung ==> Ergebnis
    return knotenY

Eine Traverse über den ganzen Baum kostet wie bei der rekursiven Implementierung O(n). Daher ist der Aufwand für eine Einzel-Traverse im Mittel O(1). Im schlechtesten Fall ist er O(h), wo h die Höhe des Baums ist.

Abstieg zum ersten oder letzten Element

Ganz ähnlich wie eine Einzel-Traverse funktioniert die Suche nach dem ersten oder letzten Element.

firstLast( binärBaum, richtung ):
    // richtung  =  Links (erstes)  oder  Rechts (letztes)

    knotenY = binärBaum.wurzel
    if knotenY = null then return binärBaum     // der leere Baum

    // Abstieg zu den Blättern
    do {
        knotenZ = knotenY
        knotenY = knotenZ.kind[richtung]
    } until knotenY = null
    return knotenZ

Der Aufwand ist O(h), wo h die Höhe des Baums ist.

Einfügen

Es sei angenommen, dass die Navigation zu einem Einfügepunkt bereits erledigt ist. Einfügepunkt bedeutet einen Knoten und eine Richtung (rechts bzw. links), in der kein Teilbaum vorhanden ist. Ein Einfügepunkt in einem binären Baum ist immer ein rechtes (bzw. linkes) Halb-Blatt.

Zum Einfügen lässt man das Kind auf der geforderten Richtung des Knotens auf das neue Element verweisen, damit ist dieses korrekt eingefügt. Die Komplexität der Einfügeoperation ist somit konstant.

Nach dem Einfügen ist das neue Element ein Blatt des Binärbaums.

Im folgenden Beispiel wird ein Knoten mit dem Schlüssel „J“ in einen binären Baum am Einfügepunkt („M“, links) eingefügt.

           S                            S
          / \                          / \
         /   \                        /   \
        G     W                      G     W
       / \                          / \
      /   \           =>           /   \
     D     M                      D     M
    / \     \                    / \   / \
   B   F     P                  B   F J   P

Durch wiederholtes Einfügen an immer derselben Stelle kann es dazu kommen, dass der Baum zu einer linearen Liste entartet.

Löschen

Beim Löschen muss man deutlich mehr Fälle unterscheiden. Wichtig ist z. B., wie viele Kinder der Knoten hat. Ist der Knoten ein Blatt (Knoten ohne Kinder), dann wird beim Löschen einfach der Knoten entfernt. Hat der zu löschende Knoten genau einen Kind, wird dieser an die Stelle des zu löschenden Knotens gesetzt.

Hat der zu löschende Knoten zwei Kinder, so ist es eine Möglichkeit, den linken (rechten) Teilbaum an die Position zu setzen, an der der zu löschende Knoten war, und den rechten (linken) Teilbaum an den linken (rechten) an dessen rechtester (linkester) Stelle anzuhängen, wie es das Beispiel zeigt („G“ soll gelöscht werden):

           S                           S
          / \                         / \
         /   \                       /   \
        G     W                     D     W
       / \                         / \
      /   \            =>         /   \
     D     M                     B     F
    / \   / \                           \
   B   F J   P                           M
                                        / \
                                       J   P

Die Veränderungen in den Höhen fallen jedoch kleiner aus, wenn der zu löschende Knoten durch einen (unmittelbaren) Nachbarn (in der in-order-Reihenfolge) ersetzt wird. Im Beispiel ist „F“ der linke Nachbar von „G“, steht also im linken Teilbaum ganz rechts; „J“ ist der rechte Nachbar von „G“, steht also im rechten Teilbaum ganz links. Die in-order-Reihenfolge ist „F“ – „G“ – „J“. Der linke (rechte) Nachbar kann einen linken (rechten) Teilbaum haben, der an die Stelle gehängt werden muss, wo der Nachbar war.

Im folgenden Beispiel wird der zu löschende Knoten „G“ durch seinen rechten Nachbarn „J“ ersetzt:

            S                             S
           / \                           / \
          /   \                         /   \
         G     W                       J     W
        / \                           / \
       /   \                         /   \
      D     M          =>           D     M
     / \   / \                     / \   / \
    B   F J   P                   B   F K   P
           \
            K

Durch wiederholtes Löschen kann es dazu kommen, dass der Baum zu einer linearen Liste entartet.

Durch die unvermeidlichen Abstiege bis zu den Halb-Blättern ist die Komplexität der Löschoperation O(h), wobei h die Höhe des Baumes ist.

Pseudocode

Die Abbildungen und der Pseudocode Remove zeigen das Entfernen eines Elements, das zwei Kinder und einen nahen Enkel besitzt, aus einem binären Baum.

Ein Binärbaum bei dem der Knoten 5 gelöscht werden soll
Der neue Baum

Remove(t, x)
  t: Binärbaum
  x: Knoten

  y: Knoten
  z: Knoten
  // Es sei angenommen, dass x.left ≠ null, x.right ≠ null und x.right.left ≠ null
  y = x.right
  while y ≠ null {
     z = y
     y = z.left
  } 
  // z ist der rechte Nachbar von x
  if z.right ≠ null then z.right.parent = z.parent
  z.parent.left = z.right
  z.right = x.right
  x.right.parent = z
  z.left = x.left
  x.left.parent = z         // x.left ≠ null
  if x.parent.left = x
     then x.parent.left = z
     else x.parent.right = z
  z.parent = x.parent

Rotation in binären Bäumen

Rotationen dienen dazu, um Bedingungen von binären Bäumen, insbesondere Höhen von Teilbäumen (bspw. in Rot-Schwarz-Bäumen), anzupassen. Sie ändern nicht die in-order-Reihenfolge, also ist nach ihrer Anwendung der Baum hinsichtlich der Reihenfolge äquivalent.

              W                                  S
             / \        Right-Rotate(S,W)       / \
            /   \           -------->          /   \
           S     Y                            G     W
          / \               <--------              / \
         /   \          Left-Rotate(W,S)          /   \
        G     U                                  U     Y

Erklärung zu Right-Rotate(S,W)

„W“ mit rechtem Teilbaum wird zum rechten Teilbaum von „S“. Der ursprüngliche rechte Teilbaum „U“ von „S“ wird zum linken Teilbaum von „W“. Der rechte Teilbaum „Y“ von „W“ bleibt an seiner Position.

Erklärung zu Left-Rotate(W,S)

„S“ mit linkem Teilbaum wird zum linken Teilbaum von „W“. Der ursprüngliche linke Teilbaum „U“ von „W“ wird zum rechten Teilbaum von „S“. Der rechte Teilbaum „Y“ von „W“ bleibt an seiner Position.

Komplexität

Rotationen benötigen konstante Laufzeit O(1).

Siehe auch

Literatur

Donald Knuth. The art of computer programming vol 1. Fundamental Algorithms, Dritte Auflage. Addison-Wesley, 1997. ISBN 0-201-89683-4. Abschnitt 2.3, (S. 318ff).

Anmerkungen

↑ ^a ^b Anmerkung: Die Tiefe wird häufig auch als Anzahl der Knoten auf dem Pfad zur Wurzel inklusive dem Knoten selbst definiert; in dem Fall ist hier statt mit i mit dem Wert i-1 zu rechnen

[Tiefe-1] Anmerkung: Die Tiefe wird häufig auch als Anzahl der Knoten auf dem Pfad zur Wurzel inklusive dem Knoten selbst definiert; in dem Fall ist hier statt mit i mit dem Wert i-1 zu rechnen

[1]