Binärer Suchbaum

Binärer Suchbaum Eigenschaften

Die Organisation eines binären Suchbaums ermöglicht schnelle Suchoperationen, da man bei der Suche immer nur einen der beiden Teile des Baumes durchsuchen muss. Die folgenden Eigenschaften sind typisch für diese Datenstruktur:

• Der Wert des linken Kindknotens ist immer kleiner als der des Elternknotens.
• Der Wert des rechten Kindknotens ist immer größer als der des Elternknotens.
• Diese Eigenschaften gelten für jeden Knoten im Baum.

Diese Struktur macht binäre Suchbäume besonders geeignet für Operationen wie Suchen, Einfügen und Löschen.

Binärer Suchbaum Anwendung

Binäre Suchbäume werden in vielen Bereichen eingesetzt, von Datenbanken und Grafikanwendungen bis hin zu Routing und Bandbreitenmanagement in Netzwerken. Infolge seiner organisierten Struktur ermöglicht der binäre Suchbaum:

• Schnelles Suchen
• Geordnetes Durchlaufen
• Einfügen und Löschen von Elementen

Ein Beispiel für die Anwendung von binären Suchbäumen ist die Implementierung von Sortieralgorithmen. BSTs werden oft verwendet, um Vorgänge wie Sortieren und Prioritäts-Warteschlangen effizient zu verwalten.

Binärer Suchbaum Nachteile

Während binäre Suchbäume viele Vorteile bieten, ist es wichtig, ihre möglichen Nachteile zu kennen:

• Im schlechtesten Fall können Operationen wie das Einfügen oder Suchen nach einem Knoten eine Zeitkomplexität von $O(n)$ haben, wenn der Baum in eine Listenstruktur entartet. Dies geschieht, wenn die eingefügten Schlüssel bereits geordnet sind.
• Binäre Suchbäume können unausgewogen werden und erfordern Rebalancing-Techniken, was zusätzliche Komplexität hinzufügt.

Beispiel eines entarteten Baums:

 1
  \
   2
    \
     3
      \
       4
        \
         5

In diesem Fall funktioniert der binäre Suchbaum wie eine verkettete Liste und die Vorteile der Baumstruktur gehen verloren. Deshalb werden oft selbstbalancierende binäre Suchbäume verwendet, wie AVL-Bäume oder Rot-Schwarz-Bäume, die sicherstellen, dass der Baum nach jeder Einfüge- oder Löschoperation balanciert bleibt.

Wie erstellst du einen Binärer Suchbaum?

Die Erstellung eines binären Suchbaums konzentriert sich auf die Einhaltung der Grundprinzipien dieser Datenstruktur. Jeder eingefügte Knoten muss auf der Grundlage seines Schlüsselwerts korrekt positioniert werden. Fügst du einen Knoten in den Baum ein, ist es wichtig, die Struktur des Baums zu durchlaufen, beginnend bei der Wurzel und nach links oder rechts zu bewegen, abhängig davon, ob der neue Knoten einen kleineren oder größeren Schlüsselwert hat.

Binärer Suchbaum erstellen: Anleitung

Die genaue Anwendung kann je nach verwendetem Programmiersprache variieren, das zugrunde liegende Prinzip bleibt jedoch gleich. Hier ist eine schrittweise Anleitung, wie du einen binären Suchbaum erstellst: 1. Starte mit einem leeren Baum. Dies bedeutet im Allgemeinen, dass du eine Wurzelvariable erstellst, die auf null gesetzt ist. 2. Füge Knoten in den Baum ein. Dies erfolgt normalerweise durch eine Operation, die als "Einfügen" bezeichnet wird. 3. Beginne beim Einfügen eines Knotens an der Wurzel. Wenn der Baum leer ist, wird die Wurzel auf den neuen Knoten gesetzt. 4. Wenn der Baum nicht leer ist, verwende den Schlüsselwert des Knotens, um zu bestimmen, wo der Knoten eingefügt wird. Wenn der Schlüsselwert des Knotens kleiner ist als der des aktuellen Knotens, fahre mit dem linken Kindknoten fort. Wenn der Schlüsselwert größer ist, fahre mit dem rechten Kindknoten fort. 5. Wiederhole den vorherigen Schritt, bis du einen Null-Knoten erreichst, d.h. einen freien Platz im Baum. Dort wird der neue Knoten platziert.

Beispielcode:

function insert(node, key) {
  if (node === null) {
    return newNode(key);
  }
  if (key < node.key) {
    node.left = insert(node.left, key);
  } else if (key > node.key) {
    node.right = insert(node.right, key); 
  }
  return node;
}

Binärer Suchbaum Beispiel

Angenommen, du möchtest die Werte [15, 10, 20, 8, 12, 16, 25] in einem binären Suchbaum ablegen. Hier ist, wie du vorgehen würdest: 1. Der erste Wert ist 15. Da der Baum leer ist, setze 15 als Wurzel des Baums. 2. Der nächste Wert ist 10, der kleiner als 15 ist. Daher füge diesen Wert als linkes Kind der Wurzel hinzu. 3. Der nächste Wert ist 20, der größer als 15 ist. Daher füge diesen Wert als rechtes Kind der Wurzel hinzu. 4. Der nächste Wert ist 8, der kleiner als 15 und auch kleiner als 10 ist. Daher füge diesen Wert als linkes Kind des Knotens mit dem Wert 10 hinzu. 5. Und so weiter...

  15
 /  \
10   20
/ \  /  \
8 12 16  25

Beachte, dass in diesem Beispiel jeder Knoten die Eigenschaften eines binären Suchbaums erfüllt: für jeden Knoten sind alle Werte in seinem linken Unterbaum kleiner und alle Werte in seinem rechten Unterbaum größer als der eigene Wert.

Beispiel

Angenommen, du hast einen binären Suchbaum und du möchtest den Wert 14 einfügen. Du würdest mit der Wurzel beginnen und dich nach links bewegen (weil 14 kleiner als 15 ist), dann nach rechts (weil 14 größer als 10 ist). Da es kein rechtes Kind von 10 gibt, würdest du hier den neuen Knoten einfügen.

Binärer Suchbaum Operationen

Um einen Binären Suchbaum (BST) effektiv nutzen zu können, ist es wichtig, die grundlegenden Operationen zu verstehen, die auf diese Datenstruktur angewendet werden können. Diese Operationen umfassen das Einfügen eines neuen Knotens, das Löschen eines existierenden Knotens und das Durchsuchen des Baums nach einem bestimmten Wert.

Binärer Suchbaum einfügen: Schritt-für-Schritt Anleitung

Um einen neuen Knoten in einem binären Suchbaum richtig einzufügen, sind die folgenden Schritte erforderlich: 1. Beginne mit der Wurzel des Baums. Wenn der Baum noch leer ist, dann ist der einzufügende Knoten der Wurzelknoten. 2. Falls der Baum nicht leer ist, dann vergleiche den einzufügenden Schlüssel mit dem Schlüssel des Wurzelknotens. 3. Ist der einzufügende Schlüssel kleiner als der des Wurzelknotens, gehe zum linken Unterbaum und wiederhole den Vorgang. 4. Ist der einzufügende Schlüssel größer als der des Wurzelknotens, gehe zum rechten Unterbaum und wiederhole den Vorgang.

function insertNode(node, newNode) { 
  if(newNode.data < node.data) { 
    if(node.left === null) 
      node.left = newNode; 
    else
      insertNode(node.left, newNode);  //Recursive call
  } else { 
    if(node.right === null) 
      node.right = newNode; 
    else
      insertNode(node.right, newNode);  //Recursive call
  } 
} 

Wie kannst du Elemente in Binärer Suchbaum löschen?

Die Operation zum Löschen von Knoten ist etwas komplexer. Es gibt drei verschiedene Fälle, die zu berücksichtigen sind: 1. Der zu löschende Knoten ist ein Blattknoten (hat keine Kinder). In diesem Fall kann der Knoten einfach entfernt werden. 2. Der zu löschende Knoten hat genau ein Kind. In diesem Fall kann der Knoten entfernt werden und der einzige Kindknoten nimmt seinen Platz ein. 3. Der zu löschende Knoten hat zwei Kinder. In diesem Fall muss der Knoten, der den zu löschenden Knoten ersetzen soll, sorgfältig ausgewählt werden. Typischerweise wird dieser Ersatzknoten ("Nachfolger") der kleinste Knoten des rechten Unterbaums oder der größte Knoten des linken Unterbaums sein.

function removeNode(node, key) {
  if(node === null) 
    return null; 
  else if(key < node.data) { 
    node.left = removeNode(node.left, key); 
    return node; 
  } else if(key > node.data) { 
    node.right = removeNode(node.right, key); 
    return node; 
  } else { 
    if(node.left === null && node.right === null) // case 1 - leaf node
      node = null; 
    else if(node.left === null)  // case 2 - one child
      node = node.right; 
    else if(node.right === null) // case 2 - one child
      node = node.left;
    else { //Case 3 - two children
      var aux = findMinNode(node.right); 
      node.data = aux.data;
      node.right = removeNode(node.right, aux.data); 
    } 
    return node; 
  } 
} 

Binärer Suchbaum in Java: Codierungsbeispiel

Die Implementierung eines binären Suchbaums in Java kann unter Verwendung von Klassen und Objekten durchgeführt werden. Jeder Knoten des Baums kann als eigenständiges Objekt mit Attributen für den Schlüsselwert, den linken Kindknoten und den rechten Kindknoten repräsentiert werden. Im folgenden Beispiel wird eine einfache Implementierung eines solchen BST in Java gezeigt.

class Node { 
  int key; 
  Node left, right; 

  public Node(int item) { 
    key = item; 
    left = right = null; 
  } 
} 

class BinaryTree { 
 Node root; 

 BinaryTree(int key) { 
  root = new Node(key); 
 } 

 BinaryTree() { 
  root = null; 
 } 
  
 void insert(int key) { 
  root = insert_rec(root, key); 
 } 

 Node insert_rec(Node root, int key) { 
  if (root == null) { 
   root = new Node(key); 
   return root; 
 }
 if (key < root.key) 
  root.left = insert_rec(root.left, key); 
 else if (key > root.key) 
  root.right = insert_rec(root.right, key);
 return root; 
}

In diesem Code ist die BinaryTree Klasse ein binärer Suchbaum und die Node Klasse repräsentiert einen Knoten im binären Suchbaum. Der insert() Methodenaufruf ist eine Wrapper-Methode für die rekursive Hilfsmethode insert_rec(), die zum Einfügen neuer Knoten verwendet wird.