263 Lecture 3

Dictionary
Stores S={X_1, ..., X_n}
X_i.key is a uniq index
Operations:
Search(S, k): Find X, X.key=K
Insert(S, x): S <- S \union {x}
Delete(S, x): S <- S - {x}
AVL-Tree
Height ≤ 1.44 log_2(n+1) ∈ O(log(n))
Note: height of a missing child is -1
∀x, |BF(x)| ≤ 1
Addition: Do not need to change bf of parent.
Deletion: Might (not) need to change bf of parent.
Heap
Heapify: O(logn)
Maintain max/min-heap property.
Build-Heap: O(n)
Produce a max/min-heap from an unordered input array.
Heapsort: O(nlogn)