Binärer Suchbaum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Abb. 1: Binärer Suchbaum der Höhe 5 mit Wurzel H und 13 Knoten, die Schlüssel tragen
Abb. 2: Derselbe binäre Suchbaum derselben Höhe 5 in anderer Sichtweise:
Wurzel H, 14 äußere und 13 innere Knoten, letztere mit denselben Schlüsseln

In der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch Binary Search Tree), ist ein binärer Baum, bei dem die Knoten „Schlüssel“ tragen, und die Schlüssel des linken Teilbaums eines Knotens nur kleiner (oder gleich) und die des rechten Teilbaums nur größer (oder gleich) als der Schlüssel des Knotens selbst sind.

Was die Begriffe „kleiner gleich“ und „größer gleich“ bedeuten, ist völlig dem Anwender überlassen; sie müssen nur eine Totalordnung (genauer: eine totale Quasiordnung siehe unten) etablieren. Am flexibelsten wird die Ordnungsrelation durch eine vom Anwender zur Verfügung zu stellende 3-Wege-Vergleichsfunktion realisiert. Auch ob es sich um ein einziges Schlüsselfeld oder eine Kombination von Feldern handelt, ist Sache des Anwenders; ferner ob Duplikate (unterschiedliche Elemente, die beim Vergleich aber nicht als „ungleich“ herauskommen) zulässig sein sollen oder nicht. Über Suchfunktionen für diesen Fall siehe unten.

Ein in-order-Durchlauf durch einen binären Suchbaum ist äquivalent zum Wandern durch eine sortierte Liste (bei im Wesentlichen gleichem Laufzeitverhalten). Mit anderen Worten: ein binärer Suchbaum bietet unter Umständen wesentlich mehr Funktionalität (zum Beispiel Durchlauf in der Gegenrichtung und/oder einen „direkten Zugriff“ mit potenziell logarithmischem Laufzeitverhalten – erzielt durch das Prinzip „Teile und herrsche“, das durch die Fernwirkung des Transitivitätsgesetzes ermöglicht wird) bei einem gleichen oder nur unwesentlich höheren Speicherbedarf.

Terminologie[Bearbeiten]

Die Begriffe Knoten und Kante, letztere definitionsgemäß als gerichtete Kante (oder auch Bogen und Pfeil), werden von den allgemeinen Graphen übernommen. Wenn die Gerichtetheit aus dem Kontext klar genug hervorgeht, genügt Kante.

Bei gerichteten Graphen kann man einem Knoten sowohl Ausgangsgrad wie Eingangsgrad zuordnen. Üblicherweise werden Binärbäume als Out-Trees aufgefasst. In einem solchen gewurzelten Baum gibt es genau einen Knoten, der den Eingangsgrad 0 hat. Er wird als die Wurzel bezeichnet. Alle anderen Knoten haben den Eingangsgrad 1. Der Ausgangsgrad ist die Anzahl der Kindknoten und ist beim Binärbaum auf maximal 2 beschränkt. Damit ist seine Ordnung als Out-Tree ≤ 2.

Knoten mit Ausgangsgrad ≥ 1 bezeichnet man als interne (innere) Knoten, solche mit Ausgangsgrad 0 als Blätter oder externe (äußere) Knoten. Bei Binärbäumen – und nur dort – findet sich gelegentlich die Bezeichnung Halbblatt für einen Knoten mit Ausgangsgrad 1 (englisch manchmal: non-branching node). Dann ist ein Blatt ein doppeltes Halbblatt.

Unterschiedliche Sprechweisen[Bearbeiten]

Den Knoten des Binärbaums in der Abb. 1 sind Schlüssel zugewiesen. Da bei der in-order-Traversierung die (alphabetische) Sortierordnung befolgt wird, ist der Baum ein binärer Suchbaum.

In der Abb. 2 ist derselbe binäre Suchbaum – nun aber mit expliziten „NIL-Knoten“ – dargestellt. Hier tragen nur die internen Knoten Schlüssel, wogegen die externen Knoten NIL-Knoten sind und als Platzhalter für die Intervalle zwischen den Schlüsseln (so bspw. in der Abb. 4), also als Einfügepunkte des binären Suchbaums fungieren. Knoten mit Ausgangsgrad 1 gibt es nicht. Der schlüssellose Suchbaum besteht aus genau einem Knoten, der extern und Wurzel zugleich ist. Da bei dieser Sichtweise die Höhe des „wirklich leeren“ Baums (der kein Suchbaum ist) zu –1 definiert ist, somit dem schlüssellosen Baum die Höhe 0 zukommt, stimmen die Höhenbegriffe überein, wenn in der Sichtweise der Abb.1 dem leeren und zugleich schlüssellosen Baum die Höhe 0 zugeteilt wird.[1]

Knotenorientierte und blattorientierte Speicherung[Bearbeiten]

Man nennt die Art der Speicherung knotenorientiert, wenn die Inhalte der Menge in den Knoten abgespeichert und die externen Blätter leer sind. Gegensatz dazu ist die blattorientierte Speicherung, bei der die Inhalte der Menge in den Blättern abgespeichert sind und die Knoten nur Hinweisschilder für die Navigation darstellen, die möglicherweise mit den Schlüsseln der Menge nichts zu tun haben.[2]

Begriffsklärung[Bearbeiten]

Zur Beachtung:

  1. Der Begriff „Nachbar“ (und „Nachbarschaft“ etc.) wird in diesem Artikel (und bei den Suchbäumen generell) anders als sonst in der Graphentheorie verwendet, nämlich ausschließlich im Sinn der eingeprägten Ordnungsrelation: „rechter“ Nachbar meint den nächsten Knoten in aufsteigender Richtung, „linker“ in absteigender.
  2. Muss in diesem Artikel auf die Hierarchiestruktur des Baumes eingegangen werden, so werden Begriffe wie „Vater“ oder „Vorfahr“ und „Vorgänger“ bzw. „Kind“ oder „Nachfahr“ und „Nachfolger“ verwendet.
  3. Die hierarchische Anordnung der Knoten in der Baumstruktur des binären Suchbaums wird als sekundär und mehr oder minder zufällig angesehen – ganz im Vordergrund steht die korrekte Darstellung der Reihenfolge.
  4. Ähnlich sekundär ist die Frage, welcher Knoten gerade die Rolle der Wurzel spielt, insbesondere wenn es sich um einen selbst-balancierenden Baum handelt. Insofern eignet die Adresse der Wurzel sich nicht zur Identifizierung des Baumes.
  5. Dagegen kann die feste Adresse eines Zeigers zur Wurzel als Identifikation genommen werden, der dann aber auch von den Operationen des Baums zu pflegen ist.

Ordnungsrelation[Bearbeiten]

Damit binäres Suchen, Sortieren etc. funktionieren kann, muss die Ordnungsrelation eine totale Quasiordnung, im Englischen „total preorder“, sein. Die Bezeichnungen für die induzierte Duplikatrelation \sim und die induzierte strenge Halbordnung <\ seien wie dort.

Die Trichotomie einer entsprechenden 3-Wege-Vergleichsfunktion \operatorname{compare}[3] – von ihrem Ergebnis ist nur das Vorzeichen \operatorname{sgn} relevant – ergibt sich folgendermaßen:

\operatorname{sgn}(\operatorname{compare}(x,y)):=
\begin{cases}
\\
\\
\end{cases}
-1, falls   x < y (x kleiner als y),
0, falls   x \sim y (x Duplikat von y),
+1, falls   y < x (x größer als y).

Nach Vertauschung von x und y und einer Umordnung erkennt man, dass

\forall x,y:\ \operatorname{sgn}(\operatorname{compare}(y,x)) = -\operatorname{sgn}(\operatorname{compare}(x,y)).

Die induzierte Ordnungsrelation  <\ ist eine strenge schwache Ordnung, im Englischen strict weak ordering. Sie induziert auf den Äquivalenzklassen dieser Relation, genauer: den Äquivalenzklassen der Duplikatrelation, eine strenge Totalordnung.

Offensichtlich lässt sich jede solche Ordnung spiegeln, d. h. +1 mit -1 vertauschen, das Ergebnis ist wieder eine strenge schwache Ordnung. Nachbarschaftsbeziehungen bleiben bestehen, es wird nur „größer“ mit „kleiner“ bzw. „rechts“ mit „links“ vertauscht.

Anmerkungen:

  • Zum reinen Aufsuchen genügt im Grunde eine 2-Wege-Vergleichsfunktion, die angibt, ob zwei „Schlüssel“ gleich sind oder nicht. Mit einer solchen Vergleichsfunktion sind aber effiziente, z. B. im Mittel logarithmische, Suchzeiten nicht erreichbar.
  • Für das Funktionieren des Sortierens und binären Suchens ist es unerheblich, ob das Aufspalten des Ungleich-Weges einer 2-Wege-Vergleichsfunktion in einen Kleiner- und einen Größer-Weg ein Artefakt ist, wie z. B. die Anordnung der Buchstaben in einem Alphabet, oder ob eine Näher-/Ferner- oder logische Beziehung (mit) im Spiel ist.
  • Spiegelt die Ordnungsrelation auch Nachbarschaft wider, kann diese für ein effizientes „unscharfes Suchen“ ausgenutzt werden.
  • Die Binarität der Binärbäume passt exakt zur Suche mit der 3-Wege-Vergleichsfunktion.
  • Wie im folgenden Abschnitt „Suchen“ näher ausgeführt, ist die Behandlung von Duplikaten unabhängig davon, ob die Ordnungsrelation Duplikate zulässt (totale Quasiordnung bzw. strenge schwache Ordnung) oder nicht (Totalordnung bzw. strenge Totalordnung). Einerseits kann es unerwünscht sein, auch wenn sie Duplikate zulässt, diese im Baum zu haben. Andererseits kann es durchaus angebracht sein, auch bei einer Totalordnung Duplikate in den Baum aufzunehmen, z. B. aus dem Eingabestrom. Es kommt in der praktischen Anwendung also nur darauf an, ob es im Baum Duplikate geben soll oder nicht. Konsequenterweise wird hier von vornherein von totalen Quasiordnungen ausgegangen.

Suchen[Bearbeiten]

Die Suche nach einem Eintrag verläuft derart, dass der Suchschlüssel zunächst mit dem Schlüssel der Wurzel verglichen wird. Sind beide gleich, so ist der Eintrag (oder ein Duplikat) gefunden.

Andernfalls (bei „ungleich“) wird überprüft, ob der Suchschlüssel kleiner (größer) ist als der Schlüssel im Knoten: dann wird die Suche rekursiv im linken (rechten) Teilbaum der Wurzel fortgeführt; gibt es keinen linken (rechten) Teilbaum, so existiert der gesuchte Eintrag im binären Suchbaum nicht.

Der auf diese Weise erhaltene finale „ungleich“-Knoten stellt zusammen mit der letzten Vergleichsrichtung den sog. Einfügepunkt für das gesuchte Element dar. (In der Sichtweise der Abb. 2 genügt der externe Knoten, der die Richtung mitenthält.) Wird es hier eingefügt, dann stimmt die in-order- mit der Sortier-Reihenfolge überein. Der finale „ungleich“-Knoten hat einen Schlüssel, der entweder der kleinste unter den größeren ist oder der größte unter den kleineren. Dasselbe gilt spiegelbildlich für seinen Nachbarknoten in der letzten Vergleichsrichtung, sofern es einen solchen gibt. (Allerdings ist dieser kein „Einfügepunkt“, sondern ein Vorfahr desselben.)

Suchen duplikatfrei[Bearbeiten]

Der folgende Pseudocode Find illustriert die Arbeitsweise des Algorithmus für eine Suche, bei der in keinem Fall Duplikate in den Baum aufgenommen werden sollen. (Das ist letztlich unabhängig davon, ob die Ordnungsrelation Duplikate zulässt oder nicht.)

Die Funktion gibt einen Knoten und ein Vergleichsergebnis zurück. Dieses Paar stellt – außer beim Vergleichsergebnis „Equal“ – einen Einfügepunkt dar.

Find(t, s) {
  t: binärerSuchbaum
  s: Suchschlüssel

  return Find0(t, s, t.root, Empty)
  // zurück kommt ein Knoten und ein Vergleichsergebnis

Find0(t, s, x, d)
  t: Teilbaum
  s: Suchschlüssel
  x: Knoten
  d: Vergleichsergebnis (Equal, LessThan, GreaterThan oder Empty)

  if x ≠ null then {
     if s = x.key then return (x, Equal)       // Suchschlüssel s gefunden
     if s < x.key
        then return Find0(x, s, x.left,  LessThan)
        else return Find0(x, s, x.right, GreaterThan)
  }
  return (t, d)                                // Suchschlüssel s nicht gefunden
  // zurück kommt  (Baum,Empty)  oder  (Knoten,Vergleichsergebnis)
}

Bei dem in der Abbildung gewählten Beispiel gibt Find beim Suchschlüssel s den ersten Treffer „F“ als Ergebnis zurück.

Suchen mit Duplikaten[Bearbeiten]

Sollen Einträge von Duplikaten in den Baum zugelassen sein, ist es vorteilhaft, die Suche nicht beim ersten besten gefundenen Knoten abzubrechen, sondern entweder auf der kleineren oder auf der größeren Seite bis zu den Blättern weiter zu suchen. Dies unterstützt eine gezielte Einfügung von Duplikaten und ist insbesondere dann interessant, wenn im Suchbaum nicht nur gesucht und gefunden werden soll, sondern u. U. auch traversiert wird. Der Einsatz der nachfolgenden Suchfunktionen beim Sortierverfahren Binarytreesort macht dieses Verfahren zu einem „stabilen“ (s. Stabilität (Sortierverfahren) mit erklärenden Beispielen).

Beim folgenden Pseudocode FindDupGE gibt der Benutzer die Richtung rechts vor, auf welcher Seite der Duplikate ein ggf. neues eingefügt werden soll.

FindDupGE(t, s, c) {
  t: binärerSuchbaum
  s: Suchschlüssel        // FindDupGE: falls s ein Duplikat ist,
                          // soll es rechts eingefügt werden.
  c: Cursor {             // Dieser Cursor enthält am Ende:
     c.d: Richtung        // (1) Left, Right oder Empty
     c.n: Knoten          // (2) Knoten oder Baum (nur bei Empty)
  }

  c.n = t                 // Für den leeren Baum
  return FindDupGE0(t.root, s, c, Empty)
  // zurück kommt ein Einfügepunkt im Cursor c
}

FindDupGE0(x, s, c, d) {
  x: Knoten
  s: Suchschlüssel
  c: Cursor
  d: Richtung

  if x ≠ null then {
     c.n = x
     if s ≥ x.key         // Suchschlüssel s ≥ Knoten.Schlüssel ?
        then return FindDupGE0(x.right, s, c, Right)  // ≥ (GE)
        else return FindDupGE0(x.left,  s, c, Left)   // <
  }
  c.d = d                 // Setzen Einfüge-Richtung
  return c
  // zurück kommt ein Einfügepunkt im Cursor c
}

Abb. 3: Einfügepunkt beim rechtesten Duplikat von s

Das Paar (Knoten, Richtung) des vorigen Beispiels Find ist hier zu dem einen Objekt, genannt Cursor, zusammengefasst. Es ist ein reiner Ausgabeparameter, der den Einfügepunkt spezifiziert.

FindDupGE ist so gehalten, dass im Ergebnis-Cursor immer ein unmittelbarer Einfügepunkt geliefert wird. Aus dem Ergebnis ist aber nicht ohne Weiteres erkennbar, ob es sich um ein Duplikat handelt, da der Einfügepunkt nicht den gesuchten Schlüssel haben muss, selbst wenn dieser im Baum vorkommt. Dies hängt von der mehr oder minder zufälligen Anordnung der Knoten im Baum ab. Ist nämlich das rechteste Duplikat (im Beispiel der Abb. 3 „R“) ein rechtes Halbblatt, dann stellt es zusammen mit der Richtung „rechts“ den Einfügepunkt dar; ist es das nicht, dann ist es in der Hierarchie des Binärbaums ein Vorfahr des rechten Nachbarn von „R“, der nun ein linkes Halbblatt ist und zusammen mit der Richtung „links“ denselben Einfügepunkt spezifiziert und also in diesem Fall das Resultat von FindDupGE darstellt.

Während bei Find alle 3 Wege der Vergleichsfunktion abgefragt werden, begnügt sich FindDupGE mit der Abfrage von deren 2.

Der nachfolgende Pseudocode FindDup kombiniert die Fähigkeiten von Find und FindDupGE, indem er sowohl ein Ergebnis über das Vorhandensein eines Suchschlüssels als auch einen Einfügepunkt für Duplikate liefert. Hierzu gibt der Benutzer eine Richtung d (links oder rechts) vor, auf welcher Seite der Duplikate ein ggf. neues eingefügt werden soll. Als Ergebnis kommt ein Paar (Knoten, Cursor) zurück, wobei Knoten angibt, ob und wo der Suchschlüssel gefunden wurde.

Der Vorschlag baut beispielhaft ein Objekt auf, das (in Analogie z. B. zu den Datenbanken) Cursor genannt wird.[4] Der Cursor enthält den ganzen Pfad vom Ergebnisknoten bis zur Wurzel. Damit passt er zur nachfolgenden in-order-Traversierfunktion Next, eine Version, die ohne Zeiger zum Vaterknoten auskommt. Die passende Datenstruktur für den Pfad ist der Stapelspeicher, engl. Stack, mit den Operationen push und pop. Die Überlaufbedingung bei push wird im vorliegenden Vorschlag nicht explizit behandelt; aber es könnte ohnehin nur mit abnormalen Ende reagiert werden, was die push-Funktion alleine genauso gut kann. Bei höhen-balancierten Bäumen ist der Speicherbedarf für den Stack logarithmisch in der Zahl der Knoten und damit recht überschaubar (vorgerechnetes Beispiel AVL-Baum).

Der etwas einfacheren Version der Funktion, bei der ein Zeiger zum Vater in jedem Knoten vorausgesetzt wird und deshalb der Cursor ohne Stack auskommt, fehlen einfach die push- und clear-Aufrufe. Der Speicherbedarf für den Baum erhöht sich allerdings um einen festen Prozentsatz.

FindDup(t, s, c, d) {
  t: binärerSuchbaum
  s: Suchschlüssel
  c: Cursor {               // Dieser Cursor enthält am Ende:
     c.d: Richtung          // (1) Left, Right oder Empty
     c.n: Knoten            // (2) Knoten oder Baum (nur bei Empty)
     c.t: Baum              // (3) Baum (enthält den Zeiger zur Wurzel)
     c.p: Pfad              // (4) Pfad vom Vater des Knotens zur Wurzel
  }
  d: Richtung               // Falls s ein Duplikat ist, soll es ...

  c.d = d                   // ... auf dieser Seite eingefügt werden.
  c.t = t                   // initialisiere den Cursor
  clear(c.p)                // initialisiere den Stack
  c.n = t                   // für den leeren Baum
  return FindDup0(t.root, s, c, Empty)
  // zurück kommt ein Knoten und ein Einfügepunkt im Cursor c
}

FindDup0(x, s, c, d) {
  x: Knoten
  s: Suchschlüssel
  c: Cursor
  d: Richtung

  if x ≠ null then {
     push(c.p, c.n)                            // Vater von x in den Stack
     c.n = x                                   // setze neuen Knoten im Cursor
     if s = x.key then return FindDup1(x, s, c, c.d)
     if s < x.key
        then return FindDup0(x.left,  s, c, Left)
        else return FindDup0(x.right, s, c, Right)
  }
  c.d = d                                      // Setzen Einfüge-Richtung
  return (null, c)                             // Suchschlüssel s nicht gefunden
  // zurück kommt null und ein Einfügepunkt im Cursor c
}

FindDup1(q, s, c, d) {
  q: Knoten                                    // letzter Knoten mit Equal
  s: Suchschlüssel
  c: Cursor
  d: Richtung

  x: Knoten
  x = c.n.child[d]
  if x ≠ null then {
     push(c.p, c.n)                            // Vater von x in den Stack
     c.n = x                                   // setze neuen Knoten im Cursor
     if s = x.key
        then return FindDup1(x, s, c, c.d)     // x ist neuer Knoten mit Equal
        else return FindDup1(q, s, c, 1 - c.d) // bei ≠ weiter in der Gegen-Richtung
  }
  c.d = d                                      // Setzen Einfüge-Richtung
  return (q, c)
  // zurück kommt ein Duplikat und ein Einfügepunkt im Cursor c
}

FindDup ist so gehalten, dass im Ergebnis-Cursor immer ein unmittelbarer Einfügepunkt geliefert wird. Wenn der Suchschlüssel nicht gefunden wurde, wird im Feld Knoten der Nullzeiger zurückgegeben. Wenn der Suchschlüssel gefunden wurde, gibt FindDup das linkeste oder rechteste Duplikat, im Beispiel der Abb. 3 das rechteste Duplikat „R“, als gefundenen Knoten zurück. Der Einfügepunkt kann mit dem gefundenen Knoten zusammenfallen; er kann aber auch sein unmittelbarer (im Beispiel der Abbildung rechter) Nachbar sein, in welchem Fall er einen anderen Schlüssel hat.

Im ersten Teil, FindDup0, werden alle 3 Wege der Vergleichsfunktion abgefragt; im zweiten Teil, FindDup1, wenn das Vorhandensein des Suchschlüssels positiv geklärt ist, nur noch deren 2.

Komplexität[Bearbeiten]

Da die Suchoperation entlang eines Weges von der Wurzel zu einem Blatt verläuft, hängt die aufgewendete Zeit im Mittel und im schlechtesten Fall linear von der Höhe h des Suchbaums ab (Komplexität O(h)); im asymptotisch vernachlässigbaren besten Fall ist die Laufzeit bei Find konstant, bei FindDupGE und FindDup jedoch immer O(h).

Die Höhe h ist im entarteten Fall so groß wie die Anzahl der vorhanden Elemente n. Beim Aufbau eines Baumes, was einem Sortierlauf entspricht, muss im Extremfall jedes Element mit jedem verglichen werden – ergibt in summa \tbinom n 2 \in \mathcal O\left(n^2\right) Vergleiche.

Gewichtsbalancierte Suchbäume können im Mittel auf konstante Laufzeit kommen, verhalten sich jedoch linear im schlechtesten Fall. Höhen-balancierte Suchbäume haben eine Höhe von O(log n) und ermöglichen so die Suche in garantiert logarithmischer Laufzeit. Der Aufbau eines Baumes kommt dann auf O(n log n) Vergleiche – das entspricht den besten Sortieralgorithmen.

Logarithmische Höhe gilt sogar im Durchschnitt für zufällig erzeugte Suchbäume, wenn die folgenden Bedingungen erfüllt sind:

  • Alle Permutationen der einzufügenden und zu löschenden Elemente sind gleich wahrscheinlich.
  • Bei Modifikationen des Baumes wird auf „asymmetrische“ Löschoperation verzichtet, d. h. die Abstiege bei den Löschungen nach links und die nach rechts halten sich im Mittel die Waage.

Suchtiefen und Pfadlängensummen[Bearbeiten]

Abb. 4: (Optimaler) binärer Suchbaum mit Gewichten (rot).

Sei \scriptstyle X := \left\{ x_1 < x_2 < ... < x_n \right\} eine Schlüsselmenge aus einem total (quasi)geordneten Reservoir \scriptstyle R von Schlüsseln, seien ferner \scriptstyle p_i bzw. \scriptstyle q_j Häufigkeiten, mit denen auf das Element \scriptstyle x \in R (oder Äquivalenzklasse resp. Intervall) zugegriffen wird, wobei \scriptstyle x \in \overline{x_i} für \scriptstyle 1 \leqq i \leqq n resp. \scriptstyle x_j < x < x_{j+1} für \scriptstyle 0 \leqq j \leqq n. (Dabei seien \scriptstyle x_0 := -\infty und \scriptstyle x_{n+1} := +\infty zusätzliche nicht zu \scriptstyle R gehörende Elemente mit der üblichen Bedeutung.) Das \scriptstyle (2n+1)-Tupel

\mathfrak{z} := \left(\begin{smallmatrix}
 & p_1 && p_2 && \cdots && p_n & \\
q_0 && q_1 && q_2 && \cdots && q_n 
\end{smallmatrix}\right)

heißt Zugriffsverteilung[5] für die Menge \scriptstyle X, wenn alle \scriptstyle p_i, q_j \geqq 0 sind. \mathfrak{z} wird zur Zugriffswahrscheinlichkeitsverteilung, wenn \scriptstyle \sum p_i + \sum q_j = 1 ist.

Sei nun \scriptstyle T ein Suchbaum für die Menge \scriptstyle X mit einer Zugriffsverteilung \mathfrak{z}, ferner sei \scriptstyle a_i^T die Tiefe des (inneren) Knotens \scriptstyle x_i und \scriptstyle b_j^T die Tiefe des Blattes \scriptstyle (x_j, x_{j+1}) (s. Abb. 4; jeweils #Terminologie der Abb. 2). Wir betrachten die Suche nach einem Element \scriptstyle x \in R. Wenn \scriptstyle x = x_i, dann vergleichen wir \scriptstyle x mit \scriptstyle a_i^T+1 Elementen im Baum. Wenn \scriptstyle x_j < x < x_{j+1}, dann vergleichen wir \scriptstyle x mit \scriptstyle b_j^TElementen im Baum. Also ist

S^T_{\mathfrak{z}} := \sum_{i=1}^n p_i (a_i^T+1) + \sum_{j=0}^n q_j b_j^T

die (mit der Zugriffsverteilung \mathfrak{z}) gewichtete Pfadlängensumme des Baumes \scriptstyle T; ist \mathfrak{z} eine Wahrscheinlichkeitsverteilung, dann ist \scriptstyle S^T_{\mathfrak{z}} die gewichtete Pfadlänge, die gewichtete Suchtiefe oder die mittlere Anzahl der benötigten Vergleiche. Die Abb. 4 zeigt einen Suchbaum \scriptstyle T, der mit einem Wert von \scriptstyle S^T_{\mathfrak{z}}=2 optimal für die Zugriffsverteilung \mathfrak{z} := \tfrac1{24} \left(\begin{smallmatrix}
 & 1 && 3 && 3 && 0 & \\
4 && 0 && 0 && 3 && 10 
\end{smallmatrix}\right) ist.

Sind alle \scriptstyle p_i=1 und alle \scriptstyle q_j=0, dann ist \scriptstyle S^T_{\mathfrak{e}} mit \mathfrak{e} := \left(\begin{smallmatrix}
 & 1 && 1 && \cdots && 1 & \\
0 && 0 && 0 && \cdots && 0 
\end{smallmatrix}\right) die Summe der erforderlichen Vergleiche, wenn ein jeder der \scriptstyle n Knoten gesucht wird (\scriptstyle \mathfrak{e} für erfolgreiche Suche). Sie steht zur so genannten internen Pfadlänge I[6] in der Beziehung

I:=\sum_{i=1}^n a_i^T = S^T_{\mathfrak{e}}-n.

Für alle binären Suchbäume \scriptstyle T ist:

\underline S_{\mathfrak{e}}(n) \leq S^T_{\mathfrak{e}} \leq n(n+1)/2,

wobei die obere Grenze von der linearen Kette kommt und die untere \scriptstyle \underline S_{\mathfrak{e}}(n) von den vollständig balancierten Binärbäumen. Die Funktion \scriptstyle \underline S_{\mathfrak{e}}(n) ist stückweise linear, streng monoton steigend und konvex nach unten; in Formeln: Ist \scriptstyle k\in \N mit \scriptstyle 2^{k-1}\leq n+1 \leq 2^k, dann ist \scriptstyle \underline S_{\mathfrak{e}}(n)=1+(n+1)k-2^k.

Übrigens ist \scriptstyle \underline S_{\mathfrak{e}}(n)=A001855(n+1) mit der Folge A001855 in OEIS.

Sind dagegen alle \scriptstyle p_i=0 und alle \scriptstyle q_j=1, dann ist \scriptstyle S^T_{\mathfrak{f}} mit \mathfrak{f} := \left(\begin{smallmatrix}
 & 0 && 0 && \cdots && 0 & \\
1 && 1 && 1 && \cdots && 1 
\end{smallmatrix}\right) die Summe der notwendigen Vergleiche, um alle \scriptstyle n+1 Blätter aufzusuchen (\scriptstyle \mathfrak{f} für fehlend). \scriptstyle S^T_{\mathfrak{f}} wird auch als externe Pfadlänge E[7] bezeichnet:

E:=\sum_{j=0}^n b_j^T = S^T_{\mathfrak{f}}.

Es gilt für alle Bäume \scriptstyle T:

S^T_{\mathfrak{f}}=S^T_{\mathfrak{e}}+n.[8]

Beweis:
Die Behauptung ist richtig für n=1.
Sei T ein Baum mit n Knoten. Bei einem Knoten auf der Höhe h fügen wir eine neue Kante und einen neuen Knoten hinzu. \scriptstyle S^T_{\mathfrak{e}} erhöht sich um h+1 und \scriptstyle S^T_{\mathfrak{f}} um 2(h+1)–h=h+2, also wächst die Differenz \scriptstyle S^T_{\mathfrak{f}}-S^T_{\mathfrak{e}} um (h+2)–(h+1)=1. ■

Die vollständig balancierten Binärbäume sind auch für die Zugriffsverteilung \scriptstyle \mathfrak{f} optimal, und es gilt für alle binären Suchbäume \scriptstyle T:

\underline S_{\mathfrak{f}}(n) \leq S^T_{\mathfrak{f}} \leq n(n+3)/2

mit \scriptstyle \underline S_{\mathfrak{f}}(n):=\underline S_{\mathfrak{e}}(n)+n.

Übrigens ist \scriptstyle \underline S_{\mathfrak{f}}(n)=A003314(n+1) mit der Folge A003314 in OEIS, und \scriptstyle n+1 ist die Anzahl der externen Knoten (Blätter).

Traversierung[Bearbeiten]

Traversierung (Querung) bezeichnet das systematische Erforschen der Knoten des Baumes in einer bestimmten Reihenfolge.

Es gibt verschiedene Möglichkeiten, die Knoten von Binärbäumen zu durchlaufen. Beim binären Suchbaum sind jedoch die sog. in-order- oder reverse in-order-Traversierungen die eindeutig bevorzugten, da sie mit der eingeprägten Totalordnung korrespondieren.

Traversierung (Einzelschritt)[Bearbeiten]

Der folgende Pseudocode Next gibt ausgehend von einem Knoten das nächste Element in ab- oder aufsteigender Reihenfolge zurück – eine iterative Implementierung. Der Vorschlag kommt ohne Zeiger zum Vaterknoten aus. Dafür muss das Eingabeobjekt, hier #Cursor genannt, den ganzen Pfad vom aktuellen Knoten bis zur Wurzel enthalten, und dieser muss von der Next-Funktion auch entsprechend gepflegt werden, wenn Next in einer Schleife verwendet wird. Die passende Datenstruktur für den Pfad ist der Stapelspeicher, engl. Stack, mit den Operationen push und pop. Die Überlaufbedingung bei push wird im vorliegenden Vorschlag nicht explizit behandelt; aber es könnte ohnehin nur mit abnormalen Ende reagiert werden, was die push-Funktion alleine genauso gut kann. Bei höhen-balancierten Bäumen ist der Speicherbedarf für den Stack logarithmisch in der Zahl der Knoten und damit recht überschaubar (vorgerechnetes Beispiel AVL-Baum).

Die etwas einfachere Version der Funktion, bei der ein Zeiger zum Vater in jedem Knoten vorausgesetzt wird und deshalb der Cursor ohne Stack auskommt, ist beim Binärbaum aufgeführt. Der Speicherbedarf für den Baum erhöht sich allerdings um einen festen Prozentsatz.

Bei einer längeren Traversierung (mehreren Aufrufen von Next) wechseln sich Halbblätter und höherrangige Vorfahren ab.

Next(c) {
  c: Cursor {               // Dieser Cursor enthält:
     c.d: Richtung          // (1) Left, Right oder EndOfTree
     c.n: Knoten            // (2) Knoten oder Baum (nur bei EndOfTree)
     c.t: Baum              // (3) Baum (enthält den Zeiger zur Wurzel)
     c.p: Pfad              // (4) Pfad vom Vater des Knotens zur Wurzel
  }
  x,y: Knoten

  x = c.n                   // Ausgangsknoten dieses Einzelschritts
  d = c.d                   // gewünschte Richtung der Traversierung
  y = x.child[d]
  if y ≠ null then {        // 1 Schritt in die gegebene Richtung
     push(c.p, x)           // Vater von y in den Stack
     d = 1 - d              // spiegele  Left <-> Right
     // Abstieg in Richtung Blätter über Kinder in der gespiegelten Richtung
     x = y.child[d]
     while x ≠ null do {
        push(c.p, y)        // Vater von x in den Stack
        y = x
        x = y.child[d]
     }
     c.n = y                // Ergebnis: das nächste Halbblatt in Richtung c.d
     return c               // (Es ist Halbblatt auf seiner (1-c.d)-Seite.)
  }
  // Am Anschlag, deshalb Aufstieg zur Wurzel über die Vorfahren in der ...
  do {                      // ... c.d-„Linie“ (nur linke oder nur rechte)
     y = x
     x = pop(c.p)           // Vater von y aus dem Stack
     if x = c.t then {      // y ist die Wurzel.
        // Somit gibt es kein Element mehr in dieser Richtung.
        c.n = c.t           // Ergebnis: der Baum als Vater der Wurzel
        c.d = EndOfTree     // signalisiere das Ende der Traversierung
        return c
     }
  } until y ≠ x.child[d]
  // Es gab beim Aufsteigen einen Richtungswechsel:
  c.n = x                   // Ergebnis: der erste Vorfahr in der gespiegelten Richtung
  return c
}

Die Traversierung über den ganzen Baum umfasst pro Bogen einen Abstieg und einen Aufstieg; der Aufwand bei n Knoten ist also n ∈ Θ(n) . Daher ist der Aufwand für eine Einzel-Traversierung im Mittel O(1). Im schlechtesten Fall ist er O(h) mit h als der Höhe des Baums.

Für rekursive Implementierungen siehe Binärbaum.

Proximitäts-Suche[Bearbeiten]

Zusammen mit der Suchfunktion lässt sich mit der oben gezeigten Einzelschritt-Traversierung eine „Proximitäts“-Suche realisieren. (Proximitäts-Suche ist ein Arbeitstitel. Der Sachverhalt ist nichts Besonderes und kommt in der Literatur sicherlich vor, ist aber jetzt nicht gefunden worden. „Unscharfe Suche“ als Fuzzy-Suche ist schon vergeben und bedeutet etwas wesentlich Anderes.) Gemeint ist eine Suche in der Nähe eines bestimmten Schlüssels, zum Beispiel auf „größer gleich“ (bzw. „kleiner gleich“). Die obigen Suchfunktionen Find, FindDupGE und FindDup liefern nämlich im „ungleich“-Fall einen Einfügepunkt. Dieser enthält, wenn der Baum nicht leer ist, ein Element, das entweder das kleinste unter den größeren ist oder das größte unter den kleineren. Im ersteren Fall können wir den Wunsch „größer gleich“ direkt befriedigen. Im letzteren Fall gehen wir zum nächsten Element in aufsteigender Reihenfolge, wenn es noch eines gibt, und geben dieses zurück, denn es muss ein größeres sein. Die Logik für die gespiegelte Version liegt auf der Hand.

Eine ähnliche Vorgehensweise findet sich bei der Index Sequential Access Method.

Einfügen[Bearbeiten]

Es sei angenommen, dass die Navigation zum Einfügepunkt bereits erledigt ist. Einfügepunkt bedeutet einen Knoten und eine Richtung (rechts bzw. links). Ein unmittelbarer Einfügepunkt in einem binären Baum ist immer ein rechtes (bzw. linkes) Halbblatt (d. i. ein Knoten ohne rechten (bzw. linken) Nachfolger). (In der Sichtweise der Abb. 2 sind dies genau die externen Knoten.) Ein mittelbarer ist der unmittelbare Nachbar in der angegebenen Richtung und spezifiziert zusammen mit der Gegenrichtung dieselbe Stelle im Binärbaum – zum echten Einfügen muss aber die Einfügefunktion noch bis zu dem Halbblatt hinabsteigen, welches den unmittelbaren Einfügepunkt darstellt. Die obigen Funktionen Find, FindDupGE und FindDup liefern als Ergebnis einen (unmittelbaren) Einfügepunkt (Find nicht bei „Equal“).

Zum Einfügen lässt man den unmittelbaren Einfügepunkt (das Kind in der entsprechenden Richtung) auf das neue Element zeigen, damit ist dieses korrekt entsprechend der totalen Quasiordnung eingefügt. Die Komplexität der Einfügeoperation ist somit konstant. Wird allerdings ein Suchvorgang mit hinzugerechnet, dominiert dieser die Komplexität.

Nach dem Einfügen ist das neue Element ein Blatt des Suchbaums.

Durch wiederholtes Einfügen von aufsteigend (oder absteigend) sortierten Schlüsseln kann es dazu kommen, dass der Baum zu einer linearen Liste entartet.

Löschen[Bearbeiten]

Das Löschen im binären Suchbaum unterscheidet sich nicht vom Löschen in einem binären Baum. Gegeben ist der zu löschende Knoten.

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

Wegen der unvermeidlichen Abstiege bis zu den Halbblättern ist die Komplexität der Löschoperation im schlechtesten Fall O(h), wobei h die Höhe des Baumes ist.

Auswahlkriterien[Bearbeiten]

Das binäre Suchen im Array kann als eine Art „Vorläufer“ der binären Suchbäume angesehen werden. Da es sich bei Einfügungen und Löschungen linear verhält und dann auch die Speicherverwaltung seines Arrays sorgfältig überlegt werden muss, wird es in der Praxis fast nur für statische, vorsortierte Tabellen eingesetzt. Sind also Einfügungen oder Löschungen für die Anwendung wichtig, sind die Binärbäume geeigneter. Bezüglich Suchzeit und Speicher verhalten sich binäres Suchen im Array und höhenbalancierte binäre Suchbäume asymptotisch gleich.

Obwohl rein zufällige binäre Suchbäume sich im Mittel logarithmisch verhalten, garantiert ein binärer Suchbaum ohne irgendeine Vorkehrung, die einer Entartung entgegenwirkt, keineswegs eine unterlineare Laufzeit. Entartungen können systematisch vorkommen, zum Beispiel wenn ein Programmierer massenhaft nahe benachbarte Sprungmarkennamen vergibt.

Es gibt jedoch sehr viele Konzepte, die dazu entwickelt wurden, eine ausreichende Ausgeglichenheit sicherzustellen. Hierbei stehen sich immer Aufwand und Ertrag gegenüber. Zum Beispiel ist der Aufwand, einen binären Suchbaum ständig vollständig balanciert zu halten, so hoch, dass sich das nur bei Anwendungen lohnen dürfte, deren Laufzeit in extremer Weise vom Suchen dominiert wird.

Ein wichtiges Kriterium für die Auswahl ist, ob der Binärbaum statisch ist, und so ein einmaliger optimaler Aufbau ausreicht, oder ob verändernde Operationen wie Einfügen und Löschen wichtig sind. Für erstere kommen gewichtete Suchbäume in Betracht, worunter auch der Bellman-Algorithmus. Bei letzteren sind höhen-balancierte Suchbäume wie der AVL-Baum und der Rot-Schwarz-Baum, aber auch Splay-Bäume von Interesse.

Eine Gegenüberstellung von Komplexitäten verschiedener Suchalgorithmen finden sich im Artikel Suchbaum; Laufzeitmessungen anhand realistischer Beispiele sind zu finden bei Pfaff 2004b.

Bei diesen Überlegungen wurde generell angenommen, dass der ganze Baum im Arbeitsspeicher (Hauptspeicher) untergebracht ist. Spielen Zugriffe zu externen Medien eine Rolle, kommen ganz andere Kriterien hinzu. Schon der B-Baum, der solche Gesichtspunkte zu berücksichtigen versucht, ist zwar ein Suchbaum, aber nicht mehr binär.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Diese Sichtweise der Abb. 2 findet sich bspw. bei #Knuth und im Artikel Rot-Schwarz-Baum. Eine explizite Gegenüberstellung der beiden Sichtweisen gibt #Pfaff 2004a, a. a. O. p. 30 „4.1.1 Aside: Differing Definitions“. Dort bezeichnet er die Sichtweise der Abb. 1 als die des Implementierers.
  2. #Mehlhorn a. a. O. S. 296
  3. deren Erfüllung der Relationsgesetze die Software nicht nachprüfen kann
  4. #Pfaff 2004b, a. a. O. p. 3, gibt einem Objekt mit ganz ähnlicher Funktion den Namen traverser und offeriert für Suchen, Einfügen und Löschen eine normale und eine traverser Variante.
  5. nach #Mehlhorn a. a. O. S. 147
  6. internal path length bei #Knuth a. a. O. pp. 399-400
  7. external path length bei #Knuth a. a. O. pp. 399-400
  8. E = I + 2n bei #Knuth.