Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume ::

Bäume

• Übergang von linearen Listen auf Baumstrukturen; Skip-Listen als "Vermittler"

• Vor- und Nachteile

• Algorithmen

• Anwendungen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Motivation

Motivation

• Die bisher betrachteten Datenstrukturen waren im Wesentlichen eindimensional oder linear: sie weisen mit der Vorgänger-Nachfolger-Relation nur eine Form von Beziehungen zwischen den einzelnen Elementen auf.

  • Das hat Auswirkungen auf die Algorithmik und deren Komplexitätsklassen, vor allem die Suche mit O(N).

• In diesem Kapitel wollen wir mit den Bäumen eine Klasse von Datenstrukturen kennen lernen, die eine zweite Dimension einbeziehen und dadurch auch die Darstellung von hierarchischen Strukturen ermöglichen.

• Baumstrukturen sind nicht nur in der Informatik von fundamentaler Bedeutung, etwa zur Organisation von Daten, sondern sind auch im Alltag in vielfältiger Form wiederzufinden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

• Bäume sind hierarchische Strukturierungshilfsmittel oder rin Organisationsprinzip für Daten, Klassen, Fakten.
• Ein typisches Beispiel ist etwa der Stammbaum einer Familie, der die Vererbungsbeziehungen darstellt, oder die Systematik in der Biologie

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

Allgemein können wir unter einem Baum eine Menge von Knoten ℕ (Nodes) und Kanten 𝔼 (Edges) verstehen, die besondere Eigenschaften aufweisen:

• So besitzt jeder Baum genau einen ausgezeichneten Knoten, der als Wurzel bezeichnet wird.

• Weiterhin ist jeder Knoten außer der Wurzel durch genau eine Kante mit seinem Vorgängerknoten verbunden.

• Jeder Knoten n_a kann 0..k Nachfolgerknoten u besitzen die durch Kanten k_a,u verbunden sind.

• Die Kanten sind (zunächst noch) gerichtet ("von oben nach unten")

• Ein Knoten oder der Baum haben eine Ordnung d: Die maximale Anzahl von Kanten pro Knoten.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

https://ac.informatik.uni-freiburg.de/lak_teaching/ss_06/info2/Slides/18_Baeume_Grundlagen_Natuerliche_Suchbaeume.pdf Nicht jede Struktur ist ein Baum (aber ein Graph)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

• Ein Knoten ohne Nachfolger kann als Blatt(knoten) bezeichnet werden.

• Ein Pfad in einem Baum ist eine Folge von unterschiedlichen Knoten, in der die aufeinander folgenden Knoten durch Kanten miteinander verbunden sind.

• Mithilfe des Pfades lässt sich auch die grundlegende Eigenschaft eines Baumes definieren: Zwischen jedem Knoten und der Wurzel gibt es genau einen Pfad. Dies bedeutet, dass:

1. ein Baum zusammenhängend ist und
2. es keine Zyklen gibt.

Weitere Eigenschaften (Parameter) von Bäumen: Höhe und Niveau.

• Unter dem Niveau eines Knotens versteht man die Länge des Pfades von der Wurzel zu diesem Knoten. Die Höhe eines Baumes entspricht dem größtem Niveau eines Blattes plus 1.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

• Es muss im Gegensatz zu lineare Listen Entscheidungsfunktionen f geben, die einen Übergang von Knoten n_a auf einen Nachfolgerknoten n_b berechenn.

  • Anders ausgedrückt: Jeder Knoten muss mit Daten verknüpft sein die entscheiden welche Kante als nächstes ausgewählt wird.
  • Ein Knoten kann mit einer Variable x_i verknüpft sein, eine Kante (a,b) die zwei Knoten n_a mit n_b verbindet mit eine Aktivierungsfunktion f(x_i)_a,b: n_a → n_b
  • Beispiel: Jeder Knoten ist mit dem Alter eines Menschen verknüpft, und die Kanten bestimmen Altersanschnitte.
  • Ein Stammbaum hat keine Kantenfunktionen!!!

• Ein Baum ist neben einer Beziehungsrelation (Stammbaum) eine Suchmaschine.

  • Die Knoten können mit den Ergebnisdaten verknüpft sein, müssen aber nicht.
  • Es kann Blätter mit den Ergebnisdaten geben (Blattsuchbaum), oder auch nicht.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

• Die Richtung von Bäumen muss nicht immer top-down sein. Ein Berechungsbaum für arithmetische Ausdrücke fängt bei den Blättern an und liefert ein Ergebnis im Wurzelknoten (Bottom-up).

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

• Ist mit jedem Knoten ein Datensatz verbunden D und ein Schlüssel k verbunden, so spricht man von einem Suchbaum.
• Die Kanten bestimmen Bereiche (Intervalle) von Schlüsseln [k₁,k₂]

• Hat man einen Bereichsbaum so sind die Datensätze nach ihrem Schlüssel sortiert, aber nicht mehr linear, sondern in Teilbäumen. Jeder Knoten ist mit einem Intervall [k₁,k₂] verknüpft.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

• In Such- und Bereichsbäumen werden die Kanten mit einer Relation zum aktuellen Knotenschlüssel k_i ausgewählt. Z.B.
  • Linke Kante wenn k<l, Rechte Kante wenn k>l ⇒ Binärbaum

Suche nach Schlüssel s endet beim Suchbaum in Knoten k mit k.key == s oder in Blatt, dessen Intervall s enthält.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Taxonomie

Taxonomie

Zusammenfassung:

Baumstrukturen dienen im Wesentlichen zur hierarchischen Repräsentation und Organisation von Daten. Eine der wichtigsten Einsatzgebiete von Bäumen ist jedoch die Unterstützung einer effizienten Suche. Hierfür werden in den einzelnen Knoten eines Baumes neben den eigentlichen Nutzdaten (bzw. einen Verweis darauf) zusätzlich noch Schlüsselwerte gespeichert, über die die Suche erfolgt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Abstrakter Datentyp Binärer Baum

Abstrakter Datentyp Binärer Baum

• Da der ADT Tree parametrisierbar bezüglich des Typs der Elemente sein soll, wird in der folgenden Spezifikation wieder ein Sortenparameter T verwendet.
  • Die entscheidende Funktion ist bin, die einen binären Baum aus einem linken und einem rechten Teilbaum sowie einem Element des Datentyps T konstruiert.
  • Für einen gegebenen Baum liefern daher left und right den linken bzw. rechten Teilbaum, während value das Wurzelelement dieses Baumes ermittelt.

Für einen aus den Teilbäumen x und y sowie dem Element b konstruierten Baum bin(x,b,y) liefert left demnach den Teilbaum x, right den Teilbaum y und value das Element b. Die beiden weiteren Funktionen empty und is_empty werden zur Konstruktion eines leeren Baumes bzw. zum Test auf einen leeren Baum benötigt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Abstrakter Datentyp Binärer Baum

Abstrakter Datentyp Binärer Baum

type Tree(T)
import Bool
operators
  empty : → Tree
  bin : Tree × T × Tree → Tree
  left : Tree → Tree
  right : Tree → Tree
  value : Tree → T
  isempty : Tree → Bool
axioms ∀x,y: Tree, ∀b: T
  left (bin (x, b, y)) = x
  right (bin (x, b, y)) = y
  value (bin (x, b, y)) = b
  isempty (empty) = true
  isempty (bin (x, b, y)) = false

ADT Tree(T) mit Operatoren und Axiomen die das Verhalten der Operationen definieren

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Datenstrukturen

Datenstrukturen

Suchbaum

Knoten sind mit Daten und Schlüssel verknüpft

typeof root = node
typeof node = {
  left  : node,
  right : node,
  data  : data,
  key  : number
}

Blattsuchbaum

Knoten sind nur mit Schlüsseln verknüpft, d.h. innere Knoten sind Wegweiser, die Daten sind nur in den Blättern

typeof root = node
typeof node = {       leaf = {
  left  : node|leaf,    key  : number,
  right : node|leaf,    data : data
  key   : number      }
}

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

Es gibt wieder den bisher bekannten Satz an Basisoperationen die auf Bäume angewendet werden:

search(k)

Suche nach einem Datensatz mit dem Schlüssel k

insert(node | ⟨data,k⟩)

Einfügen eines neues Datensatzes mit dem Schlüssel k oder eine bereits erstellten Knotens.

remove(node|data|k)

Entfernen eines eines Knotens mit dem Schlüssel k, Suche nach dem Datensatz, Schlüssel, oder Knoten.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

Suche (Binärbaum)

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function search (node,k) {
  if (node.key==k) return node
  if (node.left && node.left.key<k) return search(node.left,k)
  if (node.right && node.right.key<k) return search(node.right,k)
  throw NOTFOUND
}
search(root,100)

Suche in einem Bereichsbaum nach dem Schlüüsel k

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

Suche (k-stelliger Baum)

• Hier gibt es mehr als zwei Nachfolger. Jeder Nachfolgeknoten ist ein Teilbaum mit einem Intervallbereich [k₁,k₂]. Dieses Intervall wird in einem Knoten als lowerBound und upperBound in keyRange gespeichert.

function node(data,k) { return { children:[],data:data,key:k,keyRange:[k,k] }}
function search (node,k) {
  if (node.key==k) return node
  for(i=0;i<length(node.children);i++) {
    if (node.children[i].keyRange[0]>=k && node.children[i].keyRange[1]<=k)
      return search(node.children[i],k)
  }
  throw NOTFOUND
}

Suche in einem Bereichsbaum nach dem Schlüüsel k

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

Strategien zur Traversierung

Es gibt verschiedene Strategien zur Traversierung (für Suche, Einfügen, Löschen von Knoten) eines Baums.

Ein Beispielsbaum mit den Knoten A,B,C,D,E,F und G

Inorder-Durchlauf

Hier wird zuerst rekursiv der linke Teilbaum besucht, dann der Knoten selbst und anschließend der rechte Teilbaum. Für den binären Baum aus der Abbildung entspricht das der Reihenfolge:

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Inorder-Durchlauf

D → B → E → A → F → C → G

Ein Beispiel für die Anwendung dieser Strategie ist das Auslesen eines Baumes für einen arithmetischen Ausdruck in Infixschreibweise.

Der Algorithmus für einen Inorder-Durchlauf lässt sich am einfachsten rekursiv formulieren. Der gesamte Baum wird nach der Inorder-Strategie durchlaufen, wenn der Algorithmus mit der Wurzel des Baumes als Parameter aufgerufen wird.

function Inorder (k) {
  // Eingabe: Knoten k eines binären Baumes mit Verweis auf
  // linken (k.left) und rechten (k.right) Teilbaum sowie
  // dem Element k seleber (Daten data und Schlüssel k)
  Inorder (k.left)  /* besuche linken Teilbaum */
  Process (k.data,k.key)  /* Verarbeite aktuellen Knoten */
  Inorder (k.right) /* besuche rechten Teilbaum */
}

Inorder-Traversierung

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Preorder-Durchlauf

Bei dieser Strategie wird zuerst der Knoten selbst besucht und erst danach erfolgt das Traversieren des linken bzw. rechten Teilbaumes. Für den Beispielbaum liefert das die Reihenfolge:

A → B → D → E → C → F → G

Neben der Ausgabe eines arithmetischen Ausdrucks in Präfixschreibweise ist die Erzeugung einer eingerückten Baumdarstellung für ein Dateisystem ein typisches Anwendungsbeispiel. Hier wird zuerst der Name des Verzeichnisses ausgegeben und darunter eingerückt eine Liste der darin enthaltenen Dateien und Verzeichnisse.

Der Algorithmus für den Preorder-Durchlauf kann wiederum rekursiv formuliert werden

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Preorder-Durchlauf

function Preorder (k) {
  // Eingabe: Knoten k eines binären Baumes mit Verweis auf
  // linken (k.left) und rechten (k.right) Teilbaum sowie
  // dem Element k seleber (Daten data und Schlüssel k)
  Process  (k.data,k.key)  /* Verarbeite aktuellen Knoten */
  Preorder (k.left)  /* besuche linken Teilbaum */
  Preorder (k.right) /* besuche rechten Teilbaum */
}

Preorder-Traversierung

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Postorder-Durchlauf

Beim Postorder-Durchlauf werden erst beide Teilbäume durchlaufen, bevor der Knoten selbst besucht wird. Dies führt in unserem Beispiel zur Reihenfolge

D → E → B → F → G → C → A

Ein Beispiel für die Anwendung dieser Strategie ist die Erstellung einer Stückliste mit Aufsummierung, etwa beim UNIX-Kommando du (disk usage), das den Platzbedarf eines Verzeichnisses und aller Unterverzeichnisse im Dateisystem ermittelt. Hierbei werden zuerst die Größen der Einträge in den Blättern (d.h. der Dateien) bestimmt und für den direkten Vaterknoten (d.h. das enthaltende Verzeichnis) addiert. Der Platzbedarf dieser Verzeichnisse wird wiederum zum Platzbedarf des übergeordneten Verzeichnisses zusammengefasst usw., bis die Gesamtgröße der Wurzel bestimmt werden kann.

Wie bereits bei den anderen beiden Strategien wird der Algorithmus zum Postorder-Durchlauf am einfachsten rekursiv formuliert

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Postorder-Durchlauf

function Postorder (k) {
  // Eingabe: Knoten k eines binären Baumes mit Verweis auf
  // linken (k.left) und rechten (k.right) Teilbaum sowie
  // dem Element k seleber (Daten data und Schlüssel k)
  Postorder (k.left)  /* besuche linken Teilbaum */
  Postorder (k.right) /* besuche rechten Teilbaum */
  Process   (k.data,k.key)  /* Verarbeite aktuellen Knoten */
}

Postorder-Traversierung

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Levelorder-Durchlauf

Während bei den ersten drei Strategien der Baum zuerst in der Tiefe durchwandert wird, entspricht der Levelorder-Durchlauf einer Breitensuche, d.h., auf jedem Niveau des Baumes werden erst alle Knoten besucht, bevor auf das nächste Niveau gewechselt wird. Danach ergibt sich die Reihenfolge:

A → B → C → D → E → F → G

Der Algorithmus zum Levelorder-Durchlauf ist im Gegensatz zu den bisher betrachteten Strategien nicht rekursiv. Stattdessen wird eine Warteschlange verwendet, in der die noch zu verarbeitenden Knoten abgelegt werden. Der Baum wird durchlaufen, indem der nächste zu besuchende Knoten aus der Warteschlange entnommen wird. Nach dem Besuch dieses Knotens werden die Kinder am Ende der Warteschlange eingetragen, bevor mit dem nächsten Knoten fortgefahren wird.

Die Levelorder-Strategie wird iterativ implementiert.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Levelorder-Durchlauf

function Levelorder (k) {
  // Eingabe: Knoten k eines binären Baumes
  q = [] // leere Warteschlange;
  addTail (q, k) /* Wurzel in die Warteschlange aufnehmen */
  while (length(q)!=0) {
    n = removeHead(q);
    Process (n.data, n.key)
    addTail(q, n.left)  /* linken Knoten eintragen */
    addTail(q, n.right) /* rechten Knoten eintragen */
  }
}

Levelorder-Traversierung

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

• Das klinkt sinnlos, da das Suchen scheinbar wieder einer lineare Liste entspricht.

• Aber bei Parallelisierung der Suche in Teilbäume (Divide-and-Conquer Methode) könnte dennoch eine geringere Suchzeit notwendig sein!

function parSearch(node,k) {
  if (node.key==k) terminateSearchWith(node)
  startProcess(parSearch,node.left,k)
  startProcess(parSearch,node.right,k)
}
parSearch(root,k)

Parallele Suche. Es werden bis zu N-1-L Prozesse gestartet, bei N Knoten und L Endknoten ohne Nachfolger.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

• Z.B. auch Suche im Internet (Suchmaschine!)

• Verteilung von Berechnungen auf Rechner mittels hierarchischer Teilung

• Baumstrukturen stellen verteilte Kommunikationsnetze dar (Verbindung von Rechnern), die Kanten sind Kommunikationskanäle.

• In Betriebssystemen (UNIX) können Prozesse weietere Prozesse starten. Die neuen Prozesse werden Kindprozesse des Elternprozesses ⇒ Baumstruktur!

• Dateisysteme sind Baumstrukturen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

• Höhe eines symmetrischen ideal besetzten Binärbaums: H=O(log N).

• Die Baum-Struktur hängt von Einfügereihenfolge in anfangs leeren Baum ab

  • Höhe kann linear zunehmen, sie kann aber auch in O(log N) sein, genau ⎡log2 (N+1)⎤.

Einfügen eines neues Elements (Schlüssel k=5) in einen bestehenden Baum verändert die Höhe des Baums und dessen Symmetrie

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

Einfügen

• Das Einfügen in einem geordneten Baum hängt von seiner Stelligkeit (Ordnung) ab.
  • Bei Binärbäumen sind häufig schon alle Kanten belegt, und der neue Knoten muss am Ende eingefügt werden
  • Bei k-stelligen Bäumen könnten noch freie Kanten für das Einhängen des neuen Knoten vorhanden sein, sofern die Ordnungsrelation noch gegeben ist (hie rnicht trival zu bestimmen).

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Einfügen (Binärbaum)

• Gegeben ist ein neuer Datensatz D mit dem Schlüssel k
• Es muss zuerst die korrekte Einfügeposition gefunden werden, so dass die Ordnung der Elemente nicht verletzt wird.
• Diese Position muss ein Knoten sein, dessen Schlüsselwert größer als der des einzufügenden Elementes ist und der noch keinen linken Nachfolger hat oder einen Knoten mit einem kleineren Schlüsselwert und einen freien Platz für den rechten Nachfolger. Dabei sind im Prinzip zwei Fälle zu unterscheiden:

1. Der Baum ist leer, d.h., der einzufügende Knoten wird die neue Wurzel.
2. Es gibt bereits Knoten im Baum. In diesem Fall ist der Knoten zu identifizieren, der Elternknoten des neuen Elementes werden soll.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Einfügen (Binärbaum)

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function insert(node,data,k) {
  if (node.key==k) throw Error;
  if (k>node.key) {
    if (!node.right) node.right=Node(data,k)
    else insert(node.right,data,k)
  } else {
    if (!node.left) node.left=Node(data,k)
    else insert(node.left,data,k)    
  }
}
if (!root) root=Node(data,k)
else insert(root,data,k)

Einfügen eines neuen Datensatzs in einen Binärbaum

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Einfügen (Binärbaum)

Beispiel des Einfügens eines neuen Knotens mit dem Schlüssel k=4

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Algorithmen

Entfernen eines Knotens

Die komplizierteste Operation im binären Suchbaum ist das Löschen. Dies liegt daran, dass beim Entfernen eines inneren Knotens einer der beiden Teilbäume des Knotens »hochgezogen« und gegebenenfalls umgeordnet werden muss.

Grundsätzlich müssen beim Löschen eines Knotens k drei Fälle berücksichtigt werden:

1. Der Knoten k ist ein Blatt. Dieser Fall ist der einfachste, da hier nur der Elternknoten zu bestimmen ist und dessen Verweis auf Knoten k entfernt werden muss.
2. Der Knoten k besitzt nur ein Kindknoten. In diesem Fall ist der Verweis vom Elternknoten auf den Kindknoten von k umzulenken.
3. Der Knoten k ist ein innerer Knoten mit zwei Kindknoten. Hierbei muss der Knoten durch den am weitesten links stehenden Knoten des rechten Teilbaumes ersetzt werden, da dieser in der Sortierreihenfolge der nächste Knoten ist. Alternativ kann auch der am weitestens rechts stehende Knoten des linken Teilbaumes verwendet werden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Entfernen eines Knotens

Für das Ersetzen eines Knotens gibt es wiederum zwei Varianten:

1. Entweder werden die Daten der Knoten ausgetauscht oder
2. es werden nur die Verweise auf die Knoten aktualisiert.

• Die erste Variante ist einfacher zu implementieren, die zweite Methode vermeidet ein unter Umständen aufwendiges Kopieren.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Entfernen eines Knotens

function removeNode(root,k) {
  // Eingabe: Wurzel vom Suchbaum T, Schlüssel k des zu löschenden Elementes
  node = searchNode (root, k)
  if (node = null) throw Error
  parent = searchParent (root, node) // Arrg, sollte mit Search kombiniert werden
  /* 1. Fall */
  if (!node.left && !node.right) { // node ist Blattknoten 
    if (parent.left===node) // node ist linkes Kind 
      parent.left = null
    else 
      parent.right = null
  /* 2. Fall */
  } else if (!node.left)  {
    if (parent.left===node)  // node ist linkes Kind 
      parent.left = node.right
    else 
      parent.right = node.right
  } else if (!node.right) {
    if (parent.left===node) // node ist linkes Kind 
      parent.left  = node.left
    else
      parent.right = node.left
  } else /* 3. Fall */
    child = minElement (node.right) 
    replaceNode(node,child) // Ersetze node durch child
  }

Entfernen eines Knotens mit dem Schlüssel k

Stefan Bosse - Algorithmen und Datenstrukturen - Modul T Bäume :: Algorithmen

Entfernen eines Knotens

function minElement(node) {
  if (!node.left && !node.right) return node;
  if (node.left) return minElement(node.left)
  else           return node
}

Minimales Element eines Teilbaums

asdp