CodeUtility
Mach dir das Coderleben leicht!
Python-Algorithmen

Binärer Suchbaum in Python

Ein binärer Suchbaum hält kleinere Werte im linken und größere Werte im rechten Teilbaum, sodass jeder Vergleich die Hälfte des restlichen Baums ausschließt.

Was ist Binärer Suchbaum?

Ein binärer Suchbaum hält kleinere Werte im linken und größere Werte im rechten Teilbaum, sodass jeder Vergleich die Hälfte des restlichen Baums ausschließt.

Baue einen binären Suchbaum in Python: Werte einfügen, suchen und sortiert ausgeben.

Wann wird dieser Ansatz verwendet?

  • Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
  • Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
  • Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.

So funktioniert es

Füge Werte ein, um zu sehen, wo sie landen, suche einen Wert, um seinem Weg zu folgen, und starte eine Traversierung, um die Besuchsreihenfolge zu sehen.

Beispielcode

Code ausführen →
main.py
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None   # smaller values go left
        self.right = None  # larger values go right


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def contains(node, value):
    # Each comparison discards one whole subtree.
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def inorder(node):
    # Left subtree, node, right subtree: visits values in sorted order.
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

print("inorder:", inorder(root))
print("contains 60:", contains(root, 60))
print("contains 65:", contains(root, 65))
print("height:", height(root))

Erwartete Ausgabe

inorder: [20, 30, 40, 50, 60, 70, 80]
contains 60: True
contains 65: False
height: 3

So funktioniert es

insert() läuft von der Wurzel nach unten und hängt den Wert an seiner Stelle an. contains() folgt nur einem einzigen Pfad, was in einem ausgeglichenen Baum O(log n) Schritte dauert. Eine Inorder-Traversierung besucht links, Knoten, rechts, daher kommen die Werte sortiert heraus.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungsaufgaben

Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.

  1. Teste leere Eingaben, ein Element und doppelte Werte.
  2. Gib den Zustand nach jedem Schritt aus.
  3. Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.
In der Python-IDE ausführen →

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges