Dynamic Dictionaries
Primary Operations:
get(key) => search put(key, element) => insert remove(key) => delete
Additional operations:
ascend() get(index) remove(index)
Complexity Of Dictionary Operations get(), put() and remove()
Data Structure Worst Case Hash Table O(n) Expected O(1) O(log n) O(log n)
Binary Search O(n) Tree Balanced O(log n) Binary Search Tree
n is number of elements in dictionary
Complexity Of Other Operations ascend(), get(index), remove(index)
Data Structure ascend Hash Table Indexed BST get and remove O(D + n log n) O(D + n log n) O(n) O(n) O(log n)
Indexed O(n) Balanced BST
D is number of buckets
The Operation put()
20
10 6 15 30
40
25
35
Put a pair whose key is 35.
The Operation remove()
Three cases:
Element is in a leaf. Element is in a degree 1 node. Element is in a degree 2 node.
Remove From A Leaf
20
10 6 15 30
40
2 7
18
25
35
Remove a leaf element. key = 7
Remove From A Degree 1 Node
20
10 6 15 30
40
2 7
18
25
35
Remove from a degree 1 node. key = 40
Remove From A Degree 1 Node (contd.)
20
10 6 15 30
40
2 7
18
25
35
Remove from a degree 1 node. key = 15
Remove From A Degree 2 Node
20
10 6 15 30
40
2 7
18
25
35
Remove from a degree 2 node. key = 10
Remove From A Degree 2 Node
20
10 6 15 30
40
2 7
18
25
35
Replace with largest key in left subtree (or smallest in right subtree).
Remove From A Degree 2 Node
20
10 6 15 30
40
2 7
18
25
35
Replace with largest key in left subtree (or smallest in right subtree).
Remove From A Degree 2 Node
20
8 6 15 30
40
2 7
18
25
35
Replace with largest key in left subtree (or smallest in right subtree).
Remove From A Degree 2 Node
20
8 6 15 30
40
2 7
18
25
35
Largest key must be in a leaf or degree 1 node.
Another Remove From A Degree 2 Node
20
10 6 15 30
40
2 7
18
25
35
Remove from a degree 2 node. key = 20
Remove From A Degree 2 Node
20
10 6 15 30
40
2 7
18
25
35
Replace with largest in left subtree.
Remove From A Degree 2 Node
20
10 6 15 30
40
2 7
18
25
35
Replace with largest in left subtree.
Remove From A Degree 2 Node
18
10 6 15 30
40
2 7
18
25
35
Replace with largest in left subtree.
Remove From A Degree 2 Node
18
10 6 15 30
40
2 7
25
35
Complexity is O(height).
Yet Other Operations
Priority Queue Motivated Operations:
find max and/or min remove max and/or min initialize meld
Max And/Or Min
20 10 6 15 30 40
25
Follow rightmost path to max element. Follow leftmost path to min element. Search and/or remove => O(h) time.
Initialize
20
10
6 15 30
40
25
Sort n elements.
Initialize search tree. Output in inorder (O(n)).
Initialize must take O(n log n) time, because it isnt possible to sort faster than O(n log n).
10 6 15
Meld
1
5
12
10
17
6
8
17
15
12
Meld And Merge
Worst-case number of comparisons to merge two sorted lists of size n each is 2n-1. So, complexity of melding two binary search trees of size n each is W(n). So, logarithmic time melding isnt possible.
O(log n) Height Trees
Full binary trees.
Exist only when n = 2k 1.
Complete binary trees.
Exist for all n. Cannot insert/delete in O(log n) time.
10 6 15 8
=
1
15
10
Balanced Search Trees
Height balanced.
AVL (Adelson-Velsky and Landis) trees
Weight Balanced. Degree Balanced.
2-3 trees 2-3-4 trees red-black trees B-trees
AVL Tree
binary tree for every node x, define its balance factor
balance factor of x = height of left subtree of x height of right subtree of x
balance factor of every node x is 1, 0, or 1
Balance Factors
-1
1
0 1
1
-1 0
-1 0
This is an AVL tree.
Height Of An AVL Tree
The height of an AVL tree that has n nodes is at most 1.44 log2 (n+2).
The height of every n node binary tree is at least log2 (n+1). log2 (n+1) <= height <= 1.44 log2 (n+2)
Proof Of Upper Bound On Height
Let Nh = min # of nodes in an AVL tree whose height is h. N0 = 0. N1 = 1.
Nh, h > 1
L
Both L and R are AVL trees. The height of one is h-1. The height of the other is h-2. The subtree whose height is h-1 has Nh-1 nodes. The subtree whose height is h-2 has Nh-2 nodes. So, Nh = Nh-1 + Nh-2 + 1.
Fibonacci Numbers
F0 = 0, F1 = 1. Fi = Fi-1 + Fi-2 , i > 1. N0 = 0, N1 = 1. Nh = Nh-1 + Nh-2 + 1, i > 1. Nh = Fh+2 1. Fi ~ fi/sqrt(5). f = (1 + sqrt(5))/2.
AVL Search Tree
-1 10
1
7 0 3 0 1 5 0 8 -1 20 0 0 1 30 35 0 40
1
-1 45 0 60
25