Veröffentlicht · wird verbessert
Algorithm
Baumbegriffe und Traversierungen, Suchen, Einfügen und Löschen im binären Suchbaum sowie binäre Heaps und Prioritätswarteschlangen mit Komplexität und Code.
Ein Baum ist eine hierarchische Datenstruktur, die bei einer Wurzel beginnt und sich in Eltern- und Kindknoten verzweigt. Ergänzt man einen Binärbaum um die Regel "kleinere Schlüssel links, größere rechts", entsteht ein binärer Suchbaum (BST); mit der Regel "jeder Elternknoten ist nicht größer als seine Kinder" und einer vollständigen Form entsteht ein binärer Heap. Dieses Thema behandelt Baumbegriffe, die vier Traversierungen, Suchbäume, balancierte Bäume, Heaps und Prioritätswarteschlangen.
Bäume und Heaps tragen viele reale Systeme. Datenbankindizes sind B-Bäume, std::map in C++ und TreeMap in Java sind Rot-Schwarz-Bäume, und Scheduler, Timer und Dijkstras kürzeste Wege stützen sich auf Bäume oder Heaps. Wer versteht, dass die Höhe die Laufzeit bestimmt und ein Heap in ein einziges Array passt, wählt die passende Struktur und ist für typische Fragen in technischen Interviews gerüstet.
Zeichnen Sie zuerst einen kleinen Baum auf Papier und verfolgen Sie Pre-, In-, Post- und Level-Order-Traversierung von Hand. Implementieren Sie danach Einfügen, Suchen und Löschen im Suchbaum sowie Sift-up und Sift-down im Heap selbst und machen Sie sich klar, warum Heapify O(n) kostet. Lösen Sie schließlich Aufgaben wie Top-K oder das Zusammenführen sortierter Listen mit Python heapq, C++ priority_queue und Java PriorityQueue.
Begriffe wie Wurzel, Blatt, Tiefe und Höhe sowie Pre-, In-, Post- und Level-Order reichen aus, um die meisten Baumaufgaben zu lesen und zu lösen.
Weil kleinere Schlüssel links und größere rechts liegen, kosten Suchen, Einfügen und Löschen Zeit proportional zur Höhe, und die In-Order-Traversierung liefert die sortierte Reihenfolge.
Bei sortierter Eingabe entartet ein Suchbaum zur verketteten Liste. AVL- und Rot-Schwarz-Bäume halten die Höhe mit Rotationen bei O(log n).
Ein vollständiger Binärbaum in einem Array bietet Zugriff auf das Minimum in O(1), Einfügen und Entnehmen in O(log n) und Heapify eines ganzen Arrays in O(n).
Eine Klasse Node bildet den binären Suchbaum: bst_insert vergleicht Schlüssel, bis eine freie Stelle für den neuen Knoten gefunden ist, und bst_search läuft in einer Schleife nach unten. Die In-Order-Traversierung zeigt, dass die Schlüssel sortiert herauskommen. MinHeap speichert die Elemente in einer Liste und stellt die Heap-Eigenschaft mit Sift-up in push und Sift-down in pop wieder her, sodass die Werte aufsteigend herauskommen.
trees_and_heaps.py
# Binary search tree (insert/search) and a binary min-heap
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = bst_insert(root.left, key)
elif key > root.key:
root.right = bst_insert(root.right, key)
return root # duplicates are ignored
def bst_search(root, key):
while root is not None and root.key != key:
root = root.left if key < root.key else root.right
return root is not None
def inorder(root, out):
if root is not None:
inorder(root.left, out)
out.append(root.key)
inorder(root.right, out)
return out
class MinHeap:
def __init__(self):
self.a = []
def push(self, x):
a = self.a
a.append(x)
i = len(a) - 1
while i > 0 and a[(i - 1) // 2] > a[i]: # sift up
p = (i - 1) // 2
a[i], a[p] = a[p], a[i]
i = p
def pop(self):
a = self.a
top, last = a[0], a.pop()
if a:
a[0] = last
i, n = 0, len(a)
while True: # sift down
small = i
for c in (2 * i + 1, 2 * i + 2):
if c < n and a[c] < a[small]:
small = c
if small == i:
break
a[i], a[small] = a[small], a[i]
i = small
return top
def __len__(self):
return len(self.a)
root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
root = bst_insert(root, k)
print(inorder(root, [])) # [20, 30, 40, 50, 60, 70, 80]
print(bst_search(root, 60), bst_search(root, 65)) # True False
heap = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
heap.push(x)
print([heap.pop() for _ in range(len(heap))]) # [1, 2, 3, 5, 8, 9]
python trees_and_heaps.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Bäume und Heaps.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Bäume und Heaps aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.