Binary Search Trees
•
Dictionary Operations:
ƒget(key)
ƒ put(key, value)
ƒ remove(key)
•Additional operations:
ƒascend()
ƒ get(index)
(indexed binary search tree)
ƒremove(index) (indexed binary search tree)
Complexity Of Dictionary Operations
get(), put() and remove()
Data Structure Worst Case Expected
Hash Table O(n) O(1)
Binary Search Tree O(n) O(log n)
Balanced Binary Search TreeO(log n) O(log n)
nis number of elements in dictionary
Complexity Of Other Operations
ascend(), get(index), remove(index)
Data Structure ascend get and
remove
Hash Table O(D + n log n) O(D + n log n)
Indexed BST O(n) O(n)
Indexed
Balanced BST
O(n) O(log n)
Dis number of buckets
Definition Of Binary Search Tree
•
A binary tree
•Each node has a (key, value) pair
•For every node x, all keys in the left
subtree of xare smaller than that in x
•For every node x, all keys in the right
subtree of xare greater than that in x
Example Binary Search Tree
20
10
6
2 8 15
40
30
25
Only keys are shown
The Operation ascend()
20
10
6
2 8 15
40
30
25
Do an inorder traversal
O(n) time
The Operation get()
20
10
6
2 8 15
40
30
25
Complexity is
O(height) = O(n) , where n is number of nodes/elements
The Operation put()
20
10
6
2 8 15
40
30
25
Put a pair whose key is 35
35
The Operation put()
Put a pair whose key is 7
20
10
6
2 8 15
40
30
25
35
7
The Operation put()
20
10
6
2 8 15
40
30
25
Put a pair whose key is 18
35
7
18
The Operation put()
20
10
6
2 8 15
40
30
25
Complexity of put() is O(height)
35
7
18
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
Remove a leaf element key = 7
20
10
6
2 8 15
40
30
25
35
7
18
Remove From A Leaf (contd)
Remove a leaf element key = 35
20
10
6
2 8 15
40
30
25
35
7
18
Remove From A Degree 1 Node
Remove from a degree 1 node key = 40
20
10
6
2 8 15
40
30
25
35
7
18
Remove From A Degree 1 Node (contd)
Remove from a degree 1 node key = 15
20
10
6
2 8 15
40
30
25
35
7
18
Remove From A Degree 2 Node
Remove from a degree 2 node key = 10
20
10
6
2 8 15
40
30
25
35
7
18
Remove From A Degree 2 Node
20
10
6
2 8 15
40
30
25
Replace with largest key in left subtree (or smallest in right subtree)
35
7
18
Remove From A Degree 2 Node
20
10
6
2 8 15
40
30
25
Replace with largest key in left subtree (or smallest in right subtree)
35
7
18
Remove From A Degree 2 Node
20
8
6
2 8 15
40
30
25
Replace with largest key in left subtree (or smallest in right subtree)
35
7
18
Remove From A Degree 2 Node
20
8
6
2 8 15
40
30
25
Largest key must be in a leaf or degree 1 node
35
7
18
Another Remove From A Degree 2 Node
Remove from a degree 2 node key = 20
20
10
6
2 8 15
40
30
25
35
7
18
Remove From A Degree 2 Node
20
10
6
2 8 15
40
30
25
Replace with largest in left subtree
35
7
18
Remove From A Degree 2 Node
20
10
6
2 8 15
40
30
25
Replace with largest in left subtree
35
7
18
Remove From A Degree 2 Node
18
10
6
2 8 15
40
30
25
Replace with largest in left subtree
35
7
18
Remove From A Degree 2 Node
18
10
6
2 8 15
40
30
25
Complexity is O(height)
35
7
Indexed Binary Search Tree
•
Binary search tree
•Each node has an additional field
ƒ leftSize = number of nodes in its left subtree
Example Indexed Binary Search Tree
20
10
6
2 8 15
40
30
25
35
7
18
0
0
1
1
4
0
0 7
0 0
1 3
leftSize
values are in red
leftSize And Rank
Rank of an element is its position in inorder (inorder = ascending key order)
[2,6,7,8,10,15,18,20,25,30,35,40]
rank(2) = 0 rank(15) = 5 rank(20) = 7
leftSize(x) = rank(x) with respect to elements in
subtree rooted at x
leftSize And Rank
20
10
6
2 8 15
40
30
25
35
7
18
0
0
1
1
4
0
0 7
0 0
1 3
sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]
get(index) And remove(index)
720
10
6
2 8 15
40
30
25
35
7
18
0
0
1
1
4
0
0
0 0
1 3
sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]
get(index) And remove(index)
•
if index = xleftSize desired element is xelement
•if index < xleftSize desired element is
index ’th element in left subtree of x
•if index > xleftSize desired element is (index xleftSize1) ’th element in right
subtree of x
Applications
(Complexities Are For Balanced Trees)
Bestfit bin packing in O(n log n) time
Representing a linear list so that get(index) , add(index, element) , and remove(index)
run in O(log(list size)) time (uses an indexed binary tree, not indexed binary search tree)
Can’t use hash tables for either of these applications Linear List As Indexed Binary Tree
h
e
b
a d f
l
j
i
k
c
g
0
0
1
1
4
0
0 7
0 0
1 3
list = [a,b,c,d,e,f,g,h,i,j,k,l]
add(5,’m’)
h
e
b
a d f
l
j
i
k
c
g
0
0
1
1
4
0
0 7
0 0
1 3
list = [a,b,c,d,e,f,g,h,i,j,k,l]
add(5,’m’)
h
e
b
a d f
l
j
i
k
c
g
0
0
1
1
4
0
0 7
0 0
1 3
list = [a,b,c,d,e, m, f,g,h,i,j,k,l]
find node with element 4 (e)
add(5,’m’)
h
e
b
a d f
l
j
i
k
c
g
0
0
1
1
4
0
0 7
0 0
1 3
list = [a,b,c,d,e, m, f,g,h,i,j,k,l]
find node with element 4 (e)