Released · improving
Algorithm
Learn tree vocabulary and traversals, binary search tree insert, search and delete, and binary heaps with priority queues, with complexity and code.
A tree is a hierarchical data structure that starts at a root and branches into parents and children. Add the rule "smaller keys go left, larger keys go right" to a binary tree and you get a binary search tree (BST); add "every parent is no larger than its children" plus a complete shape and you get a binary heap. This topic covers tree vocabulary, the four traversals, BSTs, balanced trees, heaps and priority queues together.
Trees and heaps are the backbone of many real systems. Database indexes are B-trees, C++ std::map and Java TreeMap are red-black trees, and operating system schedulers, timers and Dijkstra's shortest paths all rely on trees or heaps. Knowing that height drives performance and that a heap fits in a single array tells you which structure to choose, and these ideas come up constantly in coding interviews.
Start by drawing a small tree on paper and tracing pre-order, in-order, post-order and level-order traversals by hand. Then implement BST insert, search and delete and the heap's sift up and sift down yourself, and work out why heapify is O(n). Finally, solve problems such as top-K and merging sorted lists with standard tools like Python heapq, C++ priority_queue and Java PriorityQueue.
Terms such as root, leaf, depth and height, plus pre-, in-, post- and level-order traversal, are enough to read and solve most tree problems.
Because smaller keys go left and larger keys go right, search, insert and delete cost time proportional to the height, and an in-order traversal yields sorted order.
On sorted input a BST degrades into a linked list. AVL and red-black trees use rotations to keep the height at O(log n).
A complete binary tree stored in an array gives O(1) peek, O(log n) insert and remove-min, and O(n) heapify of a whole array.
A Node class forms the binary search tree: bst_insert compares keys to find an empty slot for the new node, and bst_search walks down in a loop. The in-order traversal confirms the keys come out sorted. MinHeap keeps items in a list, restoring the heap property with sift up in push and sift down in pop, so values come out smallest first.
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.pySix chapters that take you from installation to the core ideas of Trees and heaps.
Ask questions, share experience and trade opinions about Trees and heaps.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.