CS146 Data Structures and Algorithms
Chapter 12: Binary Search Tree
BST: Dynamic Sets
• Next few lectures will focus on data structures rather than straight algorithms
• In particular, structures for dynamic sets
§ Elements have a key and satellite data
§ Dynamic sets support queries such as: o Search(S, k), Minimum(S), Maximum(S),
Successor(S, x), Predecessor(S, x)
§ They may also support modifying operations like: o Insert(S, x), Delete(S, x)
• Basic operations take time proportional to the height of the tree – O(h).
L12.2
Binary Search Trees
• Binary Search Trees (BSTs) are an important data structure for dynamic sets
• Represented by a linked data structure of nodes.
• In addition to satellite data, elements have:
§ key: an identifying field inducing a total ordering
§ left: pointer to a left child : root of left subtree (may be NULL)
§ right: pointer to a right child : root of right subtree (may be NULL)
§ p: pointer to a parent node (NULL for root)
L12.3
Binary Search Trees
• BST property:
key[leftSubtree(x)] £ key[x] £ key[rightSubtree(x)]
• Example:
F BH
ADK
L12.4
Binary Search Tree Property
• Stored keys must satisfy the binary search tree property.
§ ” y in left subtree of x, 26 then y.key £ x.key
§ ” y in right subtree of x, then y.key 3 x.key.
56
200
18 12
28
190
213
24 27
L12.5
Inorder Traversal
The binary-search-tree property allows the keys of a binary search tree to be printed, in (monotonically increasing) order, recursively.
Inorder-Tree-Walk (x) 1. ifx1NIL
2. 3. 4.
then Inorder-Tree-Walk(x.left) print x.key
Inorder-Tree-Walk(x.right)
56
26
18 28
12 24 27
200
190
213
w How long does the walk take? w Can you prove its correctness?
L12.6
Correctness of Inorder-Walk
• Must prove that it prints all elements, in order, and that it terminates.
• By induction on size of tree. Size = 0: Easy.
• Size >1:
§ Prints left subtree in order by induction.
§ Prints root, which comes after all elements in left subtree (still in order).
§ Prints right subtree in order (all elements come after root, so still in order).
L12.7
Querying a Binary Search Tree
• All dynamic-set search operations can be supported in O(h) time.
• h = Q(lg n) for a balanced binary tree (and for an average tree built by adding nodes in random order.)
• h = Q(n) for an unbalanced tree that resembles a linear chain of n nodes in the worst case.
• A binary tree with n nodes (leaf nodes and internal nodes, including the root node) and height h is balanced if the following is true: 2h−1≤ n <2h. Otherwise it is unbalanced. For example, a binary tree with height 4 can have between 8 and 15 nodes (between 1 and 8 leaf nodes) to be balanced.
L12.8
Tree Search
Tree-Search(x, k)
1. 2.
3. 4. 5.
ifx==NILork==x.key return x
ifk
if u is a left child */
else if u == u.p.left u.p.left = v
/* if u is a left subtree of its parent */
/* then v must replace u as the left subtree of u’s parent */
/* otherwise u is a right subtree and v must replace u as the right subtree of u’s parent */
/* if u is a right child */
5. else u.p.right = v
/* update v.p if v is non-NIL */
6. ifv1NIL
7. v.p = u.p
/* if v has replaced u (and thus is not NIL) */ /* v must have the same parent as u */
L12.33
Transplant(T, 56, 200)? 56
26
28
200
18
12
190
213
24 27
Deletion Using Transplant(T, u, v)
Tree-Delete(T, z)
/* (a) z has no left child */ 1 if z.left == NIL
2.
3 4
5 6 7 8 9
10 11 12
Transplant(T, z, z.right)
/* (b) z has a left child, but no right child */ else if z.right == NIL
Transplant(T, z, z.left)
/* z has two children */
else y = Tree-Minimum(z.right) /* find z’s successor */
if y.p 1 z /* (d) y lies within y’s right subtree but is not the root of this subtree */ Transplant(T, y, y.right)
y.right = z.right
y.right.p = y
/* (c) if y is z’s right child */
Transplant(T, z, y)
y.left = z.left /* replace y’s left child by z’s left child */ y.left.p = y
TOTAL: O(h) time to delete a node BST Animation
L12.35
(a)
r
(b)
q
l
(c)
q
z
NIL
q
z
l NIL
q
Tree-Delete(T, z)
/* (a) z has no left child */ 1 if z.left == NIL
r
2.
3 4
5 6
7 8 9
10 11 12
Transplant(T, z, z.right)
/* (b) z has a left child, but no right child */ else if z.right == NIL
Transplant(T, z, z.left)
/* z has two children */
else y = Tree-Minimum(z.right) /* find z’s successor */
if y.p 1 z /* (d) y lies within y’s right subtree but is not the root of this subtree */
Transplant(T, y, y.right) y.right = z.right y.right.p = y
/* (c) if y is z’s right child */ Transplant(T, z, y)
qq
y.left = z.left y.left.p = y
/* replace y’s left child by z’s left child */
z
y
Deletion Using Transplant(T, u, v)
lylx
x
NIL
L12.36
(d)
l
y
/* (a) z has no left child */ 1 if z.left == NIL
NIL
2.
3 4
5 6
7 8 9
10 11 12
Transplant(T, z, z.right)
/* (b) z has a left child, but no right child */ else if z.right == NIL
Transplant(T, z, z.left)
/* z has two children */
else y = Tree-Minimum(z.right) /* find z’s successor */
if y.p 1 z /* (d) y lies within z’s right subtree but is not the root of this subtree */
Transplant(T, y, y.right) y.right = z.right y.right.p = y
/* (c) if y is z’s right child */ Transplant(T, z, y)
q
z
r
x
q
Deletion Using Transplant(T, u, v) Tree-Delete(T, z)
l
r x
zy NIL
q
y.left = z.left y.left.p = y
/* replace y’s left child by z’s left child */
l
x
y
r
L12.37
Theorem 12.3
• The dynamic-set operations, INSERT and DELETE can be made to run in O(h) time on a binary search tree of height h.
L12.38
The End
• The primary purpose of BST is dynamic-set operations: search, insert, and delete.
§ Dynamic operations guarantee a O(lg n) height
§ Comparison based – inorder sorting v.s. Quicksort § BST Sorting O(n lg n)
• Which do you think is better, quicksort or BSTSort? Why?
• A: quicksort
§ Better constant performance
§ Sorts in place
§ Doesn’t need to build data structure tree
L12.39