Dictionaries
Dictionary: (Abstract) Set $S$ with each element having a unique key
- SEARCH(S, k): Return element $x$ with key $k$ or null
- INSERT(S, x, k): Add/replace $x$ to $S$ with key $k$
- DELETE(S, x): Remove $x$ from $S$ or do nothing
Implementation Running Times:
|
SEARCH |
INSERT |
DELETE |
| Array |
n |
n (find dup) |
n (shifting) |
| Sorted Array |
log(n) |
n |
n |
| LinkedList |
n |
n |
1 |
| Direct-access Table |
|
|
|
| (Space inefficient) |
1 |
1 |
1 |
| Hash Table |
n (avg 1) |
n (avg 1) |
n (avg 1) |
| BST |
n |
n |
n |
| Balanced Search Tree |
log(n) |
log(n) |
log(n) |
Binary Search Trees
Binary Search Tree: A tree where each node’s left child < it, right child > it
- INSERT: $\theta(h)$ Tree.root = Insert(Tree.root, x)
- If node is null, return a new node
If x < node, set left = Insert(left, x)
If x > node, set right = Insert(right, x)
If x = node, set item = x
(When node isn’t null, return current node)
- SEARCH: $\theta(h)$
- If root is null, return null
If k < node, return Search(left)
If k > node, return Search(right)
If k = node, return item
- DELETE: $\theta(h)$ Tree.root = Delete(Tree.root, x)
- If node is null, return null
If x < node, set left = Delete(left, x)
If x > node, set right = Delete(right, x)
- If x = node
- If left is null, return right
If right is null, return left
- If neither are null, move the smallest element in the right subtree here
- Worst-case height: $h=n$
Balanced Search Trees
Balanced Search Tree
- “Balance Factor” = height(left) - height(right)
- Balanced: For every node, height(left) = height(right) ± 1, or |BF| ≤ 1
(height(null) = -1)
AVL Tree (implements Balanced ST)]
- Every node stores its own height, update heights in INSERT, ROTATE, DELETE
- INSERT $O(\log n)$
- Do regular BST-INSERT
- Start at the intersection, work up to root, rotate when height difference > 1
(rotate right if left side is higher, left if right side is higher)