Ein Binary Search Tree (BST) ist eine spezielle Art von binärem Baum, der zwei Eigenschaften aufweist:
Alle linken Kindknoten haben einen kleineren Wert als ihr Elternknoten.
Alle rechten Kindknoten haben einen größeren Wert als ihr Elternknoten.
Für jeden Knoten gilt also, dass entweder ein Kindknoten fehlt oder der linke Kindknoten einen kleineren Wert hat und der rechte Kindknoten einen größeren Wert – immer in Bezug auf den Elternknoten.
Ein Binary Search Tree mit 8 Knoten
Diese Eigenschaft ist besonders nützlich, um Elemente in einem binären Baum zu suchen. Wenn wir nach einem Wert x suchen, wissen wir dadurch immer, in welche Richtung wir gehen müssen, um diesen Wert zu finden. Im obigen Beispiel suchen wir beispielsweise den Knoten mit dem Wert 3. Zuerst schauen wir uns den Wurzelknoten mit dem Wert 5 an. Da 5 größer als 3 ist, gehen wir nach links. Anschließend betrachten wir den Knoten mit dem Wert 2. Da 2 kleiner als 3 ist, bewegen wir uns nach rechts weiter. Jetzt sehen wir den Knoten mit dem Wert 4. Dieser Wert ist größer als 3, also gehen wir nach links. Schließlich treffen wir auf den Knoten mit dem Wert 3. Da 3 dem gesuchten Wert 3 entspricht, haben wir den Knoten gefunden.
# Angenommen, dass nicht existierende Knoten None sind, anstatt den Wert 0 zu besitzen
def search(node: Node | None, x: int):
"""Gibt True zurück, falls x im Baum vorhanden ist, ansonsten False."""
if node is None: # Wenn wir das Ende des Baums erreicht haben
return False # wurde der Wert x nicht gefunden
if x == node.value: # Wenn x dem Wert des aktuellen Knotens entspricht
return True # => wir haben den Wert x im Baum gefunden
if x < node.value: # Ist x kleiner => wir müssen nach links gehen
return search(node.left) # Versuch, x im linken Teilbaum zu finden
return search(node.right) # Andernfalls versuchen wir es im rechten Teilbaum
Diese Suchmethode kann sehr effizient sein, wenn die Höhe des Baums gering genug ist. In jeder Iteration bewegen wir uns entweder zum linken oder zum rechten Teilbaum. Die Anzahl der benötigten Operationen ist somit im schlimmsten Fall gleich der Höhe des Baums.
Herausforderung: Prüfe, ob der gegebene Baum ein BST ist
Gegeben ist ein binärer Baum. Deine Aufgabe ist es zu überprüfen, ob er ein Binary Search Tree (BST) ist.
Eingabe
Die Eingabe enthält durch Leerzeichen getrennte Ganzzahlen, die die Werte der Knoten im binären Baum repräsentieren. Die Reihenfolge der Werte wird stets angegeben, indem zuerst der linke, dann der rechte Teilbaum durchlaufen wird. Ein Wert von 0 bedeutet, dass der Knoten nicht existiert. Es wird garantiert, dass das eingegebene binäre Baum-Format gültig ist und die Werte eindeutig sind.
Ausgabe
Das Programm soll “Yes” ausgeben, wenn der binäre Baum ein Binary Search Tree ist, andernfalls “No”.
Beispiele
Input
Output
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Erklärung
Beispiel 1: Obwohl alle rechten Kindknoten größere Werte haben als ihre Eltern, sind nicht alle linken Kindknoten kleiner als ihre Eltern.
Beispiel 2: Hier handelt es sich um einen Binary Search Tree, weil alle linken Kindknoten kleinere Werte als ihr Elternknoten besitzen und alle rechten Kindknoten einen größeren Wert als ihr Elternknoten aufweisen.
.png?table=block&id=18a2c681-664d-81ce-94c7-e3787941d7ee&cache=v2)
