Bst

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

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.