Data Structures and Algorithms
Chapter 11
Binary Search Trees • Can be used to implement a sorted map.
• Each internal position p in a binary search tree stores (k, v) pair.
• Binary search tree is a proper binary tree with the following properties:
For each internal position p with entry (k, v) pair,
– Keys stored in the left subtree of p are less than k.
– Keys stored in the right subtree of p are greater than k.
• Note: In the above definition leaves are “placeholders,” which is shown as small squares in the graph.
Binary Search Trees • Example (only keys are shown):
27
78
66
25 43 74 85
16 39 51 68 82
94
32
48
91
44
49
Binary Search Trees • Search (successful search)
search for 48
66
27
78
25 43 74 85
16 39 51 68 82
94
32
48
91
44
49
Binary Search Trees • Search (unsuccessful search)
Binary Search Trees • Search pseudocode
Algorithm TreeSearch(p, k) if p is external then
// unsuccessful search // successful search
return p
else if k == key(p)
return p
else if k < key(p)
return TreeSearch(left(p), k) else
// recurse on left subtree
// recurse on right subtree
return TreeSearch(right(p), k) • Running time: O(h)
Binary Search Trees • Inserting an entry with (k, v)
– Perform a search operation.
– If an entry with key k is found (i.e., successful search),
the existing value is replaced with the new value v.
– If there is no entry with key k, then we add an entry at the leaf node where the unsuccessful search ended up.
Binary Search Trees • Insert illustration
Running time: O(h)
Binary Search Trees • Deleting an entry with (k, v)
– Slightly more complex – Perform search
• If we reach a leaf node, do nothing • If we find the entry at position p
– Case 1: at most one child of p is an internal node
– Case 2: p has two children, both of which are internal
Binary Search Trees • Deletion Case 1
– If both children are leaf nodes, then p is replaced with a leaf node.
– If p has one internal-node child, then that child node replaces p
delete 51
66
27
78
25 43 74 85
16 39 51 68 82 r
94
32
48
91
44
49
p
Binary Search Trees • Deletion Case 1
– If p has one internal-node child (continued) 51 was deleted 66 48 was promoted
27 78
25 43 74 85
16 39 48 68 82
94
32
44 49
r
91
Binary Search Trees • Deletion Case 2
– First, we find the node r that has the largest key that is strictly less than p’s key. This node is called the predecessor of p in the ordering of keys, which is the rightmost node in p’s left subtree.
– We let r replace p.
– Since r is the rightmost node in p’s left subtree, it
does not have a right child. It has only a left child.
– The node r is removed and the subtree rooted at r’s left child is promoted to r’s position.
Binary Search Trees • Deletion Case 2
delete 83 66 80 is the predecessor
p
27
83
25 43 71 87
16 39 51 68 80 85
94
74
79
76
r
Binary Search Trees • Deletion Case 2
83 was deleted 66 80 is in its place
r
27
80
25 43 71 87
16 39 51 68 76 85
94
• Running time: O(h)
74 79
Binary Search Trees
• Most binary search tree operations run in O(h).
• In the worst case, a tree is just a linked list. In this case,
running times are O(n).
30
40
20 10
• To guarantee O(h), a tree needs to be balanced.
Balanced Search Trees
• When a binary search tree is unbalanced, it is necessary
to rebalance the tree.
• Primary operation for rebalancing a binary search tree is
rotation.
T1 T2
T2 T3
yx
xy T3 T1
• Can rotate in either direction.
• Binary search tree property is maintained after rotation.
Balanced Search Trees
• A trinode restructuring performs a broader rebalancing.
• It involves three positions: x, y, and z
• y is the parent of x and z is the grandparent of x.
• Goal: Restructure the subtree rooted at z to reduce the path length from z to x and its subtrees.
• Use secondary labels, a, b, and c, for the three positions such that a comes before b and b comes before c in an inorder tree traversal of the tree.
• There are four different configurations. This secondary labels allow us to describe the trinode restruring operations in a uniform way.
Balanced Search Trees • Outline of the algorithm:
– (T1, T2, T3, T4) are left-to-right listing of subtrees of x, y, and z.
– The subtree rooted at z is replaced with the subtree rooted at b.
– Make a the left child of b.
– Make T1 and T2 the left and right subtree of a,
respectively.
– Make c the right child of b.
– Make T3 and T4 the left and right subtree of c, respectively.
Balanced Search Trees • Trinode restructuring: single rotation 1
Balanced Search Trees • Trinode restructuring: single rotation 2
ax
T3 T1 T2 T3 T4
T1 T2
cz by single rotation
byT4 axcz
Balanced Search Trees • Trinode restructuring: double rotation 1
az bx double rotation
T1
bx
cy azcy
T2
T3
T4
T1 T2 T3 T4
T1
z
x
T2
y
T3
T4
Balanced Search Trees • Trinode restructuring: double rotation 2
T1
bx
T1 T2 T3 T4
cz bx double rotation
ay aycz T4
T2 T3
T1
T2
y
T3
z
x T4
• Recall
AVL Trees
– The height of a node is the number of edges on the longest path from that node to a leaf node.
– The height of a tree (or a subtree) is the height of the root of the tree (or a subtree).
– Theheightofaleafnodeiszero.
• An AVL tree is a binary search tree that satisfies the
following height-balance property:
For every internal node p of T, the heights of the children of p differ by at most one.
•
AVL Trees AVL tree example:
1
42 90 42 90 21011
24
73 92
24
73 92
AVL tree Not an AVL tree
44
66 66
2332
1
1
78
29
2
AVL Trees • Updating an AVL tree
– A node p in a binary search tree is said to be balanced if the heights of p’s children differ by at most one.
– Otherwise, a node is said to be unbalanced.
– Therefore, every node in an AVL tree is balanced.
– When we insert a node to an AVL tree or remove a node from an AVL tree, the resulting tree may violate the height-balance property.
– So, we need to perform post-processing.
– We will discuss only insertion.
AVL Trees
• When a node is inserted, the leaf node p where the new node is inserted becomes an internal node (with the entry of the new node).
• So, ancestors of p may be unbalanced.
• Restructuring is necessary.
• Consider the following tree:
4
23
17
78
44
12
32 50 88
1
1
1
48 62
AVL Trees
• After inserting 54, the node with 78 is unbalanced
After insertion, before rebalancing
5
44
24
17 78 131
32 50 88
12
48
62
1
54
• Post-processing
– Search-and-repair strategy
AVL Trees
– Search a node z that is the lowest ancestor of p that is unbalanced.
– y is z’s child with the greater height
– x is y’s child with the greater height
5
44
24
17 78 131
32
y 50 88 12
T1
T2
p 54
T3
48 x62
1 T4
z
AVL Trees
• Perform double rotation to rebalanced the tree
(a) After insertion, before
rebalancing
(b) After rebalancing 5 double rotation 4
44
44
2423x 17 78z 17 62
131122
32 y50 88 32 50y z78 12 111 48 x62 48 54 88
T1 p54 T3 T2
T1 T2
T4
1T4 T3
References
• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, “Data Structures and Algorithms in Java,” Sixth Edition, Wiley, 2014.