Binärer Suchbaum (BST)

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Definition

Linker Teilbaum eines Knotens:
- Werte kleiner als der Knoten selbst
Rechter Teilbaum eines Knotens:
- Werte größer als der Knoten selbst
Linker und rechter Teilbaum müssen binäre Suchbäume sein

Schematische Darstellung eines binären Suchbaums.

Implementierung

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None

Suche

Suche nach 72

Schematische Darstellung eines binären Suchbaums.

Suche

Suche nach 72

Schematische Darstellung eines binären Suchbaums, bei dem der Wurzelknoten gelb markiert ist.

Suche

Suche nach 72

Schematische Darstellung eines binären Suchbaums, bei dem die Wurzel und ihr linker Teilbaum grau markiert sind. Der erste Knoten des rechten Teilbaums ist gelb markiert.

Suche

Suche nach 72

Schematische Darstellung eines binären Suchbaums. Der linke Teilbaum des letzten Wurzelknotens und der letzte Wurzelknoten sind grau markiert. Der neue Wurzelknoten ist gelb markiert.

Suche

Suche nach 72

Schematische Darstellung eines binären Suchbaums, bei dem der neue Wurzelknoten gelb und die übrigen Knoten grau markiert sind.

Suche

Suche nach 72

Schematische Darstellung eines binären Suchbaums, bei dem der neue Wurzelknoten gelb und die übrigen Knoten grau markiert sind. Der markierte Knoten hat die Zahl 72.

Suche

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

Einfügen

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Grafische Darstellung eines neuen Knotens.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

Grafische Darstellung des neuen Knotens, der zum Wurzelknoten geworden ist.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

Grafische Darstellung eines neuen Knotens und eines Wurzelknotens mit rechtem Kind.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

Grafische Darstellung eines neuen Knotens und eines Wurzelknotens mit rechtem Kind. Der Wurzelknoten ist current_node.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

Grafische Darstellung eines Wurzelknotens mit rechtem und linkem Kind. Der Wurzelknoten ist current_node. Der neue Knoten ist das linke Kind.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

Grafische Darstellung eines neuen Knotens und eines Binärsuchbaums mit einigen Elementen. Der Wurzelknoten ist current_node.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

Grafische Darstellung eines neuen Knotens und eines Binärsuchbaums mit einigen Elementen. current_node ist das linke Kind der Wurzel.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

Grafische Darstellung eines neuen Knotens und eines Binärsuchbaums mit linkem Teilbaum.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

Grafische Darstellung eines Binärsuchbaums mit linkem Teilbaum. Der neue Knoten ist jetzt das rechte Kind der Wurzel.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

Grafische Darstellung eines neuen Knotens und eines Binärsuchbaums mit einigen Elementen.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Grafische Darstellung eines neuen Knotens und eines Binärsuchbaums mit einigen Elementen. current_node ist das rechte Kind der Wurzel.

Einfügen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Grafische Darstellung eines neuen Knotens und eines Binärsuchbaums mit einigen Elementen. current_node ist das rechte Kind der Wurzel. Der neue Knoten ist das linke Kind von current_node.

Löschen

Keine Kinder

Grafische Darstellung eines Binärsuchbaums mit einigen Elementen. Ein Knoten ist rot markiert, da er entfernt wird. Dieser Knoten hat keine Kinder.

Löschen

Keine Kinder
- löschen

Grafische Darstellung eines Binärsuchbaums mit einigen Elementen. Der zu entfernende Knoten ist aus dem Baum verschwunden.

Löschen

Ein Kind

Grafische Darstellung eines Binärsuchbaums mit einigen Elementen. Ein Knoten ist rot markiert, da er entfernt wird. Dieser Knoten hat ein rechtes Kind.

Löschen

Ein Kind
- löschen
- Kind mit Elternknoten verbinden

Grafische Darstellung eines Binärsuchbaums mit einigen Elementen. Der entfernte Knoten ist verschwunden und die Wurzel zeigt auf das rechte Kind des entfernten Knotens.

Löschen

Ein Kind
- löschen
- Kind mit Elternknoten verbinden

Grafische Darstellung eines Binärsuchbaums.

Löschen

Zwei Kinder

Grafische Darstellung eines Binärsuchbaums, bei dem der Wurzelknoten gelöscht werden soll und rot markiert ist.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:

Grafische Darstellung eines Binärsuchbaums, bei dem der Wurzelknoten gelöscht werden soll und rot markiert ist.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen

Grafische Darstellung eines Binärsuchbaums, bei dem der Wurzelknoten gelöscht werden soll und rot markiert ist. Das rechte Kind der Wurzel ist gelb markiert.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen
  - dann links entlang bis zum Ende

Grafische Darstellung eines Binärsuchbaums, bei dem der Wurzelknoten gelöscht werden soll und rot markiert ist. Ein weiterer Knoten ist gelb markiert, um den Nachfolger zu finden.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen
  - dann links entlang bis zum Ende

Grafische Darstellung eines Binärsuchbaums, bei dem der Wurzelknoten gelöscht werden soll und rot markiert ist. Ein weiterer Knoten ist gelb markiert, um den Nachfolger zu finden.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen
  - dann links entlang bis zum Ende

Grafische Darstellung eines Binärsuchbaums, bei dem der Wurzelknoten gelöscht werden soll und rot markiert ist. Ein weiterer Knoten ist gelb markiert, um den Nachfolger zu finden. Der Nachfolger wurde gefunden und ist die Zahl 13.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen
  - dann links entlang bis zum Ende

Grafische Darstellung eines Binärsuchbaums. Der Wurzelknoten wurde durch den Nachfolger ersetzt.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen
  - dann links entlang bis zum Ende
  - falls der Nachfolger ein rechtes Kind hat:

Grafische Darstellung eines Binärsuchbaums, bei dem der Nachfolger ein rechtes Kind hat.

Löschen

Zwei Kinder
- durch den Nachfolger ersetzen
  - der Knoten mit dem kleinsten Wert, der größer ist als der des Knotens
- Nachfolger finden:
  - rechtes Kind besuchen
  - dann links entlang bis zum Ende
  - falls der Nachfolger ein rechtes Kind hat:
    - Kind wird linkes Kind des Nachfolger-Elterns.

Grafische Darstellung eines Binärsuchbaums, bei dem der Nachfolger ein rechtes Kind hatte. Dieses Kind wurde zum linken Kind des Nachfolger-Elterns, und die Wurzel wurde durch den Nachfolger ersetzt.

Einsatzgebiete

Listen effizient ordnen
Viel schnelleres Suchen als in Arrays und verketteten Listen
Viel schnelleres Einfügen und Löschen als in Arrays
Dient zur Implementierung fortgeschrittener Datenstrukturen:
- dynamische Mengen
- Lookup-Tabellen
- Prioritätswarteschlangen

Lass uns üben!

Datenstrukturen und Algorithmen in Python