Ein binärer Suchbaum (BST) ist eine binäre Baumdatenstruktur, bei der jeder Knoten höchstens zwei Kinder hat, die als linkes und rechtes Kind bezeichnet werden.
In einem BST sind die Schlüsselwerte der Knoten im linken Teilbaum kleiner als der Schlüsselwert der Wurzel, und die Schlüsselwerte der Knoten im rechten Teilbaum sind größer als der Schlüsselwert der Wurzel. Diese Eigenschaft ermöglicht effiziente Such-, Einfüge- und Löschoperationen, wodurch BSTs nützlich für die Implementierung von Algorithmen wie der binären Suche und verschiedenen Datenstrukturen wie Mengen und Maps sind.

BST-Implementierung

class TreeNode:
    def __init__(self, key):
        # Initialize a new TreeNode with a given key value
        self.key = key
        self.left = None  # Initialize left child pointer to None
        self.right = None  # Initialize right child pointer to None

class BST:
    def __init__(self):
        # Initialize an empty Binary Search Tree (BST) with no root
        self.root = None

    def insert(self, key):
        # Insert a new key into the BST
        if self.root is None:  # If the tree is empty, create a new root node
            self.root = TreeNode(key)
        else:
            self._insert_recursive(self.root, key)  # Otherwise, call recursive insertion

    def _insert_recursive(self, root, key):
        # Recursively insert the key into the appropriate position in the tree
        if key < root.key:  # If the key is less than the current node's key, go left
            if root.left is None:  # If the left child is None, insert a new node
                root.left = TreeNode(key)
            else:
                self._insert_recursive(root.left, key)  # Otherwise, continue recursion to the left
        elif key > root.key:  # If the key is greater than the current node's key, go right
            if root.right is None:  # If the right child is None, insert a new node
                root.right = TreeNode(key)
            else:
                self._insert_recursive(root.right, key)  # Otherwise, continue recursion to the right

    def delete(self, key):
        # Delete a key from the BST
        self.root = self._delete_recursive(self.root, key)  # Call recursive deletion

    def _delete_recursive(self, root, key):
        # Recursively delete the key from the tree
        if root is None:  # If the tree is empty or key not found, return None
            return root
        if key < root.key:  # If the key is less than the current node's key, go left
            root.left = self._delete_recursive(root.left, key)  # Recursively delete from the left subtree
        elif key > root.key:  # If the key is greater than the current node's key, go right
            root.right = self._delete_recursive(root.right, key)  # Recursively delete from the right subtree
        else:  # Key found, perform deletion
            if root.left is None:  # If the left child is None, return the right child
                return root.right
            elif root.right is None:  # If the right child is None, return the left child
                return root.left
            else:  # Node has both children, find successor and replace key with successor
                successor = self._find_min(root.right)
                root.key = successor.key
                root.right = self._delete_recursive(root.right, successor.key)
        return root

    def search(self, key):
        # Search for a key in the BST
        return self._search_recursive(self.root, key)  # Call recursive search

    def _search_recursive(self, root, key):
        # Recursively search for the key in the tree
        if root is None or root.key == key:  # If root is None or key found, return root
            return root
        if key < root.key:  # If the key is less than the current node's key, search left subtree
            return self._search_recursive(root.left, key)
        return self._search_recursive(root.right, key)  # Otherwise, search right subtree

Grundlegende Operationen Zeitkomplexität

Hinweis

Ein balancierter Baum ist eine Datenstruktur, bei der sich die Höhen der Teilbäume eines Knotens um höchstens eins unterscheiden. Wir werden dies in den nächsten Abschnitten ausführlicher besprechen.

1. Einfügen:

   • Best- und Durchschnittsfall (O(log n)): In einem balancierten BST beinhaltet das Einfügen das Durchlaufen des Baums von der Wurzel, um die geeignete Position für den neuen Knoten zu finden. Auf jeder Ebene wird der Suchraum halbiert, wodurch sich die Suchzeit logarithmisch in Bezug auf die Anzahl der Knoten verringert;
   • Schlimmster Fall (O(n)): Wenn der Baum unausgeglichen wird, wie z.B. wenn Knoten in sortierter Reihenfolge eingefügt werden, kann der Baum zu einer verketteten Liste degenerieren. In diesem Fall wird die Einfügeoperation linear in Bezug auf die Anzahl der Knoten, da jeder neue Knoten einfach an das Ende der Liste angehängt wird.

2. Löschen:

   • Best- und Durchschnittsfall (O(log n)): Ähnlich wie beim Einfügen beinhaltet das Löschen in einem balancierten BST das Durchlaufen des Baums, um den zu löschenden Knoten zu finden. Der Suchraum wird auf jeder Ebene halbiert, was zu einer logarithmischen Zeitkomplexität führt;
   • Schlimmster Fall (O(n)): Wie beim Einfügen kann das Löschen, wenn der Baum unausgeglichen wird, auf O(n) Zeitkomplexität abfallen. Zum Beispiel kann das Löschen eines Knotens aus einem schiefen Baum erfordern, dass man durch die meisten oder alle Knoten geht.

3. Suche:

   • Best- und Durchschnittsfall (O(log n)): Die Struktur des BST ermöglicht eine effiziente Suche durch rekursives Durchlaufen des Baums von der Wurzel. Der Suchraum wird auf jeder Ebene halbiert, was zu einer logarithmischen Zeitkomplexität führt;
   • Schlimmster Fall (O(n)): Im schlimmsten Fall ist der Baum unausgeglichen, was zu einer linearen Suchzeit führt. Dies tritt auf, wenn der Baum zu einer verketteten Liste degeneriert und die Suche durch die meisten oder alle Knoten geht.