Unterschiedliche Sprechweisen

Den Knoten des Binärbaums in der Abb. 1A sind Schlüssel in Gestalt von Großbuchstaben zugeordnet. Da bei der in-order-Traversierung deren (alphabetische) Sortierordnung befolgt wird, ist der Baum ein binärer Suchbaum.

In der Abb. 1B ist die identische Schlüsselmenge in einem anderen binären Suchbaum dargestellt, einem Suchbaum, der explizite „NIL-Knoten“ enthält. Hier tragen nur die internen Knoten Schlüssel, wogegen die externen, die NIL-Knoten (auch externe Blätter genannt), als Platzhalter für die Intervalle zwischen den Schlüsseln (so beispielsweise in der Abb. 3), also als Einfügepunkte des binären Suchbaums fungieren. (Der Knoten mit dem Schlüssel ${\displaystyle {\mathsf {A}}}$ ist hier ein internes Blatt.) 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 (total) 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. 1A dem leeren und zugleich schlüssellosen Baum die Höhe 0 und einem Baum, der nur aus einem Knoten besteht, die Höhe 1 zugeteilt wird.

Knotenorientierte und blattorientierte Speicherung

Wenn – wie oben und in der Abb. 1A – die Inhalte der Menge in den Knoten abgespeichert werden und die externen Knoten leer sind, nennt man die Art der Speicherung knotenorientiert. Um auszudrücken, dass sie nicht zur Menge gehören, bezeichnet man in diesem Fall die externen Knoten zur besseren Unterscheidung als externe Blätter. Ein externes Blatt stellt einen Einfügepunkt dar.

Bei der blattorientierten Speicherung sind die Inhalte der Menge in den Blättern abgespeichert, und die Knoten stellen nur Hinweisschilder für die Navigation dar, die möglicherweise mit den Schlüsseln der Menge wenig zu tun haben.

Suchen ohne Duplikate (rekursiv)

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  (Knoten,Vergleichsergebnis) oder  (Baum,Empty)
}

Bei dem in der Abb. 2 gewählten Beispiel würde Find beim Suchschlüssel s = ${\displaystyle {\mathsf {F}}}$ den ersten Treffer, das obere ${\displaystyle {\mathsf {F}}}$, als Ergebnis zurückgeben.

Suchen ohne Duplikate (iterativ und mit Sentinel)

Die folgende Funktion FindWithSentinel hat genau dieselbe Funktionalität wie das obenstehende Find. Der Trick mit dem Wächterknoten oder Sentinel erspart pro Iterationsschritt eine Abfrage, und zwar die auf Abwesenheit des Kindknotens, also ${\displaystyle \leq h}$ (=Höhe) Abfragen. Sie wird hier iterativ programmiert in der Programmiersprache C vorgestellt.

Bemerkung: Da beim Ergebnis »gefunden« der Knoten, beim Ergebnis »nicht gefunden« aber der letzte Elterknoten gebraucht wird, kommen in der heißen Schleife zwei Variable alternierend zum Einsatz.

typedef struct NODE {     // Knoten des binären Suchbaums
  Node* lChild;           // -> linker  Kindknoten
  Node* rChild;           // -> rechter Kindknoten
  int key;                // Schlüssel
} Node;

typedef struct RESULT {   // Ergebnisstruktur mit zwei Feldern
  Node* resNod;           // -> Ergebnisknoten
  int resDir;             // Vergleichsergebnis (Equal, LessThan, GreaterThan oder Empty)
} Result;

typedef struct BinarySearchTree { // Der binäre Suchbaum
  Node* root;             // -> Wurzel des Baums
} Bst;
Bst bst;

Node Sentinel, *sentinel = &Sentinel; // Der Wächterknoten und sein Zeiger
Sentinel.lChild = sentinel; Sentinel.rChild = sentinel;

// Initialisierung des leeren binären Suchbaums:
bst.root = sentinel;      // Indikator, dass die Wurzel .root fehlt.
// Dieser Zeiger ist auch von den Einfüge- oder Löschfunktionen
//   an den Stellen zu verwenden, wo es einen Kindknoten nicht gibt.

int FindWithSentinel(
          Bst* t,         // -> binärer Suchbaum
          int sKey,       // der Suchschlüssel
          Result *r)      // -> Ergebnisstruktur
{ Node *x, *y;
  sentinel->key = sKey;   // präpariere den Wächterknoten Sentinel
  y = (Node*)t;           // »Elter« der Wurzel
  // Suchschleife:
  for (x = t->root; sKey != x->key; ) {
    if (sKey < x->key)
      y = x->lChild;      // ein echter oder der Wächter-Knoten
    else
      y = x->rChild;      // dito
    if (sKey == y->key) { // Schlüsselgleichheit
      r->resNod = y;      // Ergebnisknoten
      goto Epilog;
    }
    if (sKey < y->key)
      x = y->lChild;      // dito
    else
      x = y->rChild;      // dito
  }
  // Abbruch-Bedingung Schlüsselgleichheit: sKey == x->key
  r->resNod = x;
  x = y;                  // Elterknoten von r->resNod
Epilog:
  if (r->resNod != sentinel) { // Der Ergebnisknoten r->resNod ist echt
                          // und zeigt auf einen Schlüssel mit Wert sKey.
    r->resDir = Equal;
  }
  else {                  // Der Ergebnisknoten r->resNod ist unecht.
                          // x ist der »Elter« von r->resNod
    r->resNod = x;        // -> Ergebnisknoten (->Node oder ->Bst)
    if (x != (Node*)t) {  // x ist ein echter Knoten (->Node)
      if (sKey < x->key) {
        r->resDir = LessThan;
      else
        r->resDir = GreaterThan;
    }
    else                  // x ist der Baum (->Bst)
      r->resDir = Empty;
  }
  return r->resDir;
  // *r enthält  (->Node,Vergleichsergebnis)  oder  (->Bst,Empty)
}

Suchen, wenn Duplikate zulässig

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 Binary Tree Sort 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. Bei einer Funktion FindDupLE mit dem gespiegelten Vergleich if s ≤ x.key würde ein neues Duplikat links von allen vorhandenen Duplikaten eingefügt werden.

FindDupGE(t, s, c) {
  t: binärerSuchbaum
  s: Suchschlüssel        // FindDupGE: falls s ein Duplikat ist,
                          // soll es rechts (GE:≥) 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
}

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. 2 das untere rechte ${\displaystyle {\mathsf {F}}}$) kein Halbblatt nach rechts, dann ist es in der Hierarchie des Binärbaums ein Vorfahr seines rechten Nachbarn (im Beispiel ${\displaystyle {\mathsf {G}}}$), der nun ein Halbblatt nach links 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 zum Beispiel zu den Datenbanken) Cursor genannt wird. 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 Elterknoten auskommt. Die passende Datenstruktur für den Pfad ist der Stapelspeicher, engl. Stack, mit den Operationen push und pop.

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

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)
                            // Die folgenden 2 nur, wenn die Elterknoten fehlen:
     c.t: Baum              // (3) Baum (enthält den Zeiger zur Wurzel)
     c.p: Pfad              // (4) Pfad vom Elter 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)                            // Elter c.n 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)                            // Elter c.n 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. 2 das rechteste Duplikat ${\displaystyle {\mathsf {F}}}$, als gefundenen Knoten zurück. Der Einfügepunkt kann mit dem gefundenen Knoten zusammenfallen; er kann aber auch sein unmittelbarer (im Beispiel der Abb. rechter) Nachbar sein, in welchem Fall er einen anderen Schlüssel (im Beispiel ${\displaystyle {\mathsf {G}}}$) 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

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 ${\displaystyle h}$ des Suchbaums ab (Komplexität ${\displaystyle {\mathcal {O}}(h)}$); im asymptotisch vernachlässigbaren besten Fall ist die Laufzeit bei Find konstant, bei FindDupGE und FindDup jedoch immer ${\displaystyle {\mathcal {O}}(h).}$

Die Höhe ${\displaystyle h}$ ist im entarteten Fall so groß wie die Anzahl der vorhanden Elemente ${\displaystyle n}$. Beim Aufbau eines Baumes, was einem Sortierlauf entspricht, muss im Extremfall jedes Element mit jedem verglichen werden – ergibt in summa ${\displaystyle {\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 ${\displaystyle {\mathcal {O}}(\log n)}$ und ermöglichen so die Suche in garantiert logarithmischer Laufzeit. Der Aufbau eines Baumes kommt dann auf ${\displaystyle {\mathcal {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

Sei ${\displaystyle X:=\left\{x_{1}<x_{2}<...<x_{n}\right\}}$ eine Schlüsselmenge aus einem total geordneten Reservoir ${\displaystyle R}$ von Schlüsseln, seien ferner ${\displaystyle p_{i}}$ bzw. ${\displaystyle q_{j}}$ Häufigkeiten, mit denen auf das Element ${\displaystyle x\in R}$ zugegriffen wird, wobei ${\displaystyle x=x_{i}}$ für ${\displaystyle 1\leqq i\leqq n}$ resp. ${\displaystyle x_{j}<x<x_{j+1}}$ für ${\displaystyle 0\leqq j\leqq n}$. (Dabei seien ${\displaystyle x_{0}:=-\infty }$ und ${\displaystyle x_{n+1}:=+\infty }$ zusätzliche nicht zu ${\displaystyle R}$ gehörende Elemente mit der üblichen Bedeutung.) Das ${\displaystyle (2n+1)}$-Tupel

${\displaystyle {\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 für die Menge ${\displaystyle X}$, wenn alle ${\displaystyle p_{i},q_{j}\geqq 0}$ sind. ${\displaystyle {\mathfrak {z}}}$ wird zur Zugriffswahrscheinlichkeitsverteilung, wenn ${\displaystyle \textstyle \sum p_{i}+\sum q_{j}=1}$ ist.

Sei nun ${\displaystyle T}$ ein Suchbaum für die Menge ${\displaystyle X}$ mit einer Zugriffsverteilung ${\displaystyle {\mathfrak {z}}}$, ferner sei ${\displaystyle a_{i}^{T}}$ die Tiefe des (inneren) Knotens ${\displaystyle x_{i}}$ und ${\displaystyle b_{j}^{T}}$ die Tiefe des (externen) Blattes ${\displaystyle (x_{j},x_{j+1})}$ (s. Abb. 3; jeweils #Terminologie der Abb. 1B). Wir betrachten die Suche nach einem Element ${\displaystyle x\in R}$. Wenn ${\displaystyle x=x_{i}}$, dann vergleichen wir ${\displaystyle x}$ mit ${\displaystyle a_{i}^{T}+1}$ Elementen im Baum. Wenn ${\displaystyle x_{j}<x<x_{j+1}}$, dann vergleichen wir ${\displaystyle x}$ mit ${\displaystyle b_{j}^{T}}$Elementen im Baum. Also ist

${\displaystyle S_{\mathfrak {z}}^{T}:=\sum _{i=1}^{n}p_{i}(a_{i}^{T}+1)+\sum _{j=0}^{n}q_{j}b_{j}^{T}}$

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

Sind alle ${\displaystyle p_{i}=1}$ und alle ${\displaystyle q_{j}=0}$, dann ist ${\displaystyle S_{\mathfrak {e}}^{T}}$ mit ${\displaystyle {\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 ${\displaystyle n}$ Knoten gesucht wird (${\displaystyle {\mathfrak {e}}}$ für erfolgreiche Suche). Sie steht zur so genannten internen Pfadlänge ${\displaystyle I}$ in der Beziehung

${\displaystyle I:=\sum _{i=1}^{n}a_{i}^{T}=S_{\mathfrak {e}}^{T}-n}$.

Für alle binären Suchbäume ${\displaystyle T}$ ist:

${\displaystyle {\underline {S}}_{\mathfrak {e}}(n)\leq S_{\mathfrak {e}}^{T}\leq n(n+1)/2}$,

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

Übrigens ist ${\displaystyle {\underline {S}}_{\mathfrak {e}}(n)=A001855(n+1)}$ mit der Folge A001855 in OEIS.

Sind dagegen alle ${\displaystyle p_{i}=0}$ und alle ${\displaystyle q_{j}=1}$, dann ist ${\displaystyle S_{\mathfrak {f}}^{T}}$ mit ${\displaystyle {\mathfrak {f}}:=\left({\begin{smallmatrix}&0&&0&&\cdots &&0&\\1&&1&&1&&\cdots &&1\end{smallmatrix}}\right)}$ die Summe der notwendigen Vergleiche, um alle ${\displaystyle n+1}$ Blätter aufzusuchen (${\displaystyle {\mathfrak {f}}}$ für fehlend). ${\displaystyle S_{\mathfrak {f}}^{T}}$ wird auch als externe Pfadlänge ${\displaystyle E}$ bezeichnet:

${\displaystyle E:=\sum _{j=0}^{n}b_{j}^{T}=S_{\mathfrak {f}}^{T}}$.

Es gilt für alle Bäume ${\displaystyle T}$:

${\displaystyle S_{\mathfrak {f}}^{T}=S_{\mathfrak {e}}^{T}+n}$.

Beweis

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

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

${\displaystyle {\underline {S}}_{\mathfrak {f}}(n)\leq S_{\mathfrak {f}}^{T}\leq n(n+3)/2}$

mit ${\displaystyle {\underline {S}}_{\mathfrak {f}}(n):={\underline {S}}_{\mathfrak {e}}(n)+n}$.

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

Traversierung (Einzelschritt)

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 Elterknoten 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 etwas einfachere Version der Funktion, bei der ein Zeiger zum Elter 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) EndOfTree oder Left, Right
     c.n: Knoten            // (2) Baum (nur bei EndOfTree) oder Knoten
     c.t: Baum              // (3) Baum (enthält den Zeiger zur Wurzel)
     c.p: Pfad              // (4) Pfad vom Elter 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)           // Elter x 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)        // Elter y 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)           // Elter 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 Elter 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 Kante einen Abstieg und einen Aufstieg; der Aufwand bei ${\displaystyle n}$ Knoten ist also ${\displaystyle 2n\in \Theta (n)}$. Daher ist der Aufwand für eine Einzel-Traversierung im Mittel und amortisiert konstant und im schlechtesten Fall in O(h) mit h als der Höhe des Baums.

Ob die Abfrage auf Anwesenheit des Kindknotens als (x ≠ null) oder mit einem Wächterknoten (s. Abschnitt #Suchen ohne Duplikate (iterativ und mit Sentinel)) geschieht, macht keinen Unterschied – weder funktionell noch laufzeitmäßig. Da bei der Traversierung immer mit der Adresse x eines Knotens verglichen wird, ist durch die Präparation eines Wächterknotens mit einem Wert auch kein Vorteil zu erwarten.

Proximitäts-Suche

Jede Suchfunktion lässt sich mit der oben gezeigten Einzelschritt-Traversierung zu einer „Proximitäts“-Suche (engl. approximate match) kombinieren. Das 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 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 kann der Wunsch „größer gleich“ direkt befriedigt werden. Im letzteren Fall geht man zum nächsten Element in aufsteigender Reihenfolge, wenn es noch eines gibt, und gibt dieses zurück, denn es muss ein größeres sein. Die Logik für die gespiegelte Version liegt auf der Hand.

Ähnliche Funktionalität hat die Index Sequential Access Method.

Ein wichtiger Anwendungsfall ist die Abbildung mehrerer linear sortierter Schlüssel auf eine einzige lineare Ordnung mithilfe einer raumfüllenden Kurve, bspw. des Hilbert-Index. Hier ist möglicherweise die schlechtere Treffsicherheit des so gebildeten Schlüssels durch gute Nachbarschaftseigenschaften auszugleichen.

Kopf

Da die Wurzel einer Löschung oder einer Rotation anheimfallen, somit den Baum nicht repräsentieren kann, muss diese Rolle von einer anderen Datenstruktur übernommen werden, die in der Literatur Kopf genannt wird. Sie enthält den Zeiger zur Wurzel und fungiert als eine Art Elter der Wurzel.

Iterative Programmierung

In der Literatur werden die Operationen häufig in rekursiver Programmierung vorgestellt. Der Anwender hat aber mehrere Vorteile davon, wenn der Implementierer die vom Aufschreiben her eleganten Rekursionen durch simple Iterationen ersetzt hat, da dadurch ${\displaystyle h}$ (Höhe) Prozeduraufrufe und -rücksprünge eingespart werden und der Speicherbedarf für den Programm-Stapelspeicher konstant gehalten wird. Es geht aber nicht nur um Ressourcenschonung. Bei der Traversieroperation wird dadurch beispielsweise die Programmierung der Anwendung wesentlich vereinfacht. Für das Aufbewahren des Rückwegs zu Wurzel und Kopf, der beim Traversieren, aber auch häufig bei Modifikationen zur Aufrechterhaltung der Bauminvarianten (AVL- oder Rot-Schwarz-Kriterium), gebraucht wird und der bei der rekursiven Programmierung neben anderem im Programmstapelspeicher steckt, muss dann ein anderes, explizites Konstrukt gewählt werden, welches sich im Cursor (siehe unten) subsumieren lässt.

Dadurch wird eine Trennung der modifizierenden Operationen von der Navigation möglich.

Trennung der navigierenden von den modifizierenden Operationen

Einfüge- und Löschoperation sind sinnvollerweise von der Suchoperation zu trennen, wenn zum Einfügepunkt beziehungsweise Knoten auch auf andere Weise als mit der Standardsuchoperation navigiert werden soll, beispielsweise mittels eines Querschritts oder mithilfe einer zweiten Suchstruktur für dasselbe Element wie in der #Mehrere Zugriffspfade.

Diese Modularisierung der Navigations- von den modifizierenden Operationen setzt einen gegebenenfalls unterlogarithmischen (sprich: konstanten) Aufwand der letzteren frei, denn ein Aufstieg bis zur Wurzel ist beispielsweise bei AVL-Baum und Rot-Schwarz-Baum nur in Ausnahmefällen erforderlich. In Anwendungen mit starkem sequentiellem Anteil kann sich das positiv auf die Laufzeit auswirken.

Cursor

Beim Suchen wird ein Paar (Knoten, Richtung) erzeugt, welches geeignet ist, beim Einfügen den Einfügepunkt zu spezifizieren. Beim Löschen wird der zu löschende Knoten durch die Komponente Knoten bezeichnet, und die Komponente Richtung kann angeben, wohin der Cursor nach der Löschung fortschreiten soll. Beim Traversieren gibt Knoten den Ausgangspunkt und Richtung die gewünschte Richtung der Navigation an, um im Ergebnis wieder bei einem solchen Paar anzukommen. Damit erzeugen und/oder verbrauchen alle wichtigen Operationen ein Konstrukt, das (in Analogie zum Beispiel zu den Datenbanken) Cursor genannt wird.

Die Größe des Cursors hängt entscheidend davon ab, ob die Knoten einen Zeiger zum Elter enthalten oder nicht.

1. Elterzeiger vorhanden: Ein Paar (Knoten, Richtung) stellt einen vollwertigen Cursor dar.
   Ein Cursor wird nach einer Operation dann und nur dann ungültig, wenn es sich um eine Löschung handelt, und der Knoten des Cursors das Ziel der Löschung ist.
   Mit dem prozentualen Aufschlag auf den Speicherbedarf für die Datenstruktur erkauft man sich auf jeden Fall eine prozentuale Einsparung an Laufzeit, da der Rückweg zu Wurzel und Kopf immer schon gesichert ist.
2. Zeiger zum Elterknoten nicht vorhanden („Cursor mit Stapel“): Zusätzlich zum Paar (Knoten, Richtung) muss der Pfad vom Knoten zu Wurzel und Kopf im Cursor gehalten werden. Die Länge des Cursors entspricht damit der maximalen Höhe des Baums. Diese ist entweder von sich aus ausreichend beschränkt (vorgerechnetes Beispiel AVL-Baum), oder der Stapelüberlauf löst eine Reorganisation des Baums oder ein abnormales Ende aus.
   Bei allen Operationen ist der Zugriff zum Elterknoten über den Stapel im Cursor geringfügig teurer als über den Elterzeiger. Soll der Pfad im Cursor auch nach einer modifizierenden Operation gültig gehalten werden (beispielsweise für sequentielle Einfügungen oder Löschungen), kommt noch ein zusätzlicher prozentualer Aufschlag hinzu. Dies kann so aber nur für einen Cursor, den Eingabecursor, erbracht werden.

Benötigt eine Anwendung mehrere Cursor für ein und denselben Suchbaum und über Änderungen an ihm hinweg, dann kann das Aufrechterhalten der Konsistenz der Cursor mit Stapel (zum Beispiel durch erneutes Suchen) so aufwändig werden, dass es wirtschaftlicher ist, dem Baum Elterzeiger zu spendieren.

Mehrere Zugriffspfade

Als Beispiel für eine Anwendung mit 2 Zugriffspfaden sei ein klassisches Speichermanagement gebracht. Elemente der Datenstruktur sind die freien Speicherblöcke mit den Attributen (Feldern) Ort und Größe. Für jedes der beiden Felder gebe es eine Suchstruktur, bei Ort ohne Duplikate. Da bei Größe jedoch Duplikate unvermeidlich sind, empfiehlt sich ein lexikographisch zusammengesetzter Schlüssel (Größe,Ort). Beim Akquirieren wird ein Block von Mindestgröße gesucht, ausgetragen und ein Rest, falls vorhanden, wieder eingetragen. Bei der Speicherrückgabe wird nach Ort gesucht, auf Konfliktfreiheit mit den Nachbarblöcken geprüft (ebenfalls ein Beispiel für die Nützlichkeit der Querschritts) und der zurückzugebende Block gegebenenfalls mit diesen verschmolzen. Alle Veränderungen müssen auf beiden Suchstrukturen durchgezogen werden. Sind Elterzeiger vorhanden, dann erspart das Hangeln von der einen Suchstruktur zur anderen einen Suchvorgang.