1 Chapter 12 Binary Search Trees
CS 253: Algorithms Chapter 12 Binary Search Trees Credit: Dr. George Bebis
2 Binary Search Trees Tree representation: Node representation:
Left child Right child L R parent key data Tree representation: A linked data structure in which each node is an object Node representation: Key field Data Left: pointer to left child Right: pointer to right child p: pointer to parent (p [root [T]] = NIL) Satisfies the binary-search-tree property (see the next slide)
3 Binary Search Tree Property
If y is in left subtree of node x, then key [y] ≤ key [x] If y is in right subtree of node x, then key [y] ≥ key [x] 2 3 4 5 7 9
4 Binary Search Trees Support many dynamic set operations
INSERT, DELETE MINIMUM, MAXIMUM PREDECESSOR, SUCCESSOR Running time of basic operations on binary search trees On average: (lgn) The expected height of the tree is lgn In the worst case: (n) The tree is a linear chain of n nodes
6 Traversing a Binary Search Tree
Inorder tree walk: Root is printed between the values of its left and right subtrees: left, root, right keys are printed in sorted order Preorder tree walk: root printed first: root, left, right Postorder tree walk: root printed last: left, right, root Inorder: 2 3 4 5 7 9 Preorder: Postorder:
7 Traversing a Binary Search Tree
Alg: INORDER-TREE-WALK(x) if x NIL then INORDER-TREE-WALK ( left [x] ) print key [x] INORDER-TREE-WALK ( right [x] ) E.g.: Running time: (n), where n is the size of the tree rooted at x 2 3 4 5 7 9 Output:
8 Facts given only PREORDER traversal of the BST However
It is possible to construct a unique Binary Search Tree given only PREORDER traversal of the BST given only POSTORDER traversal of the BST It is not possible to construct a unique Binary Search Tree given only INORDER traversal of a BST However It is not possible to construct a unique Binary Tree given only INORDER or only POSTORDER or only PREORDER traversal of a Binary Tree.
9 Searching for a Key Given a pointer to the root of a tree and a key k:
Return a pointer to a node with key k if one exists Otherwise return NIL Start at the root; trace down a path by comparing k with the key of the current node x: If the keys are equal: we have found the key If k < key[x] search in the left subtree of x If k >key[x] search in the right subtree of x 2 3 4 5 7 9
10 Example: TREE-SEARCH Search for key 13: 15 6 7 13 3 2 4 6 7 13
18 17 20 9 Search for key 13: 15 6 7 13
12 Finding the Minimum in a Binary Search Tree
Goal: find the minimum value in a BST Following left child pointers from the root, until a NIL is encountered Alg: TREE-MINIMUM(x) while left [x] NIL do x ← left [x] return x Running time O(h), h – height of tree 3 2 4 6 7 13 15 18 17 20 9 Minimum = 2
13 Finding the Maximum in a Binary Search Tree
Goal: find the maximum value in a BST Following right child pointers from the root, until a NIL is encountered Alg: TREE-MAXIMUM(x) while right [x] NIL do x ← right [x] return x Running time O(h), h – height of tree 3 2 4 6 7 13 15 18 17 20 9 Maximum = 20
15 Finding the Successor Alg: TREE-SUCCESSOR(x) Running time:
if right [x] NIL % Case 1 then return TREE-MINIMUM(right [x]) y ← p[x] % Case 2 - y parent of x while y NIL and x == right [y] do x ← y y ← p[y] return y Running time: O (h), h – height of the tree Exercise: if x=20, what does this algorithm return? 3 2 4 6 7 13 15 18 17 20 9 y x
18 Example: TREE-INSERT Insert 13: x=root[T], y=NIL y 2 1 3 5 9 12 18 15
19 17 2 1 3 5 9 12 18 15 19 17 x 2 1 3 5 9 12 18 15 19 17 x 13 2 1 3 5 9 12 18 15 19 17 y x = NIL y = 15
20 Deletion Goal: Delete a given node z from a binary search tree
Case 1: z has no children Delete z by making the parent of z point to NIL 15 16 20 18 23 6 5 12 3 7 10 13 delete 15 16 20 18 23 6 5 12 3 7 10 z
21 Deletion Case 2: z has one child
Delete z by making the parent of z point to z’s child, instead of to z And parent of z becomes the parent of z’s child. 15 16 20 18 23 6 5 12 3 7 10 13 delete 15 20 18 23 6 5 12 3 7 10 z
22 Deletion Case 3: z has two children
z’s successor (y) is the minimum node in z’s right subtree y has either no children or one right child (but no left child) Delete y from the tree (via Case 1 or 2) Replace z’s key and satellite data with y’s. 6 15 16 20 18 23 6 5 12 3 7 10 13 delete z 15 16 20 18 23 7 6 12 3 10 13 y
23 TREE-DELETE(T, z) if left[z] = NIL or right[z] = NIL
then y ← z % z has at most one child: Case 1 or 2 else y ← TREE-SUCCESSOR(z) % z has 2 children: Case 3 if left[y] NIL then x ← left[y] else x ← right[y] if x NIL then p[x] ← p[y] z 15 16 20 18 23 6 5 12 3 7 10 13 y x
24 TREE-DELETE(T, z) – cont.
if p[y] = NIL then root[T] ← x else if y = left[p[y]] then left[p[y]] ← x else right[p[y]] ← x if y z then key[z] ← key[y] copy y’s satellite data into z return y 15 16 20 18 23 6 5 12 3 7 10 13 y x Running time: O(h) due to TREE-SUCCESSOR operation
25 Binary Search Trees - Summary
Operations on binary search trees: SEARCH O(h) PREDECESSOR O(h) SUCCESSOR O(h) MINIMUM O(h) MAXIMUM O(h) INSERT O(h) DELETE O(h) These operations are fast if the height of the tree is small Theorem 12.4 The expected height of a randomly built binary search tree on n distinct keys is O(lgn)
26 Problems Exercise What is the difference between the MAX-HEAP property and the binary search tree property? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? A: No. (sorting can not be done in O(n)) Add’l exercise: Can you use the heap property to design an efficient algorithm that searches for an item in a binary tree? A: no, it will be very inefficient! (why?)
27 Problems Let x be the root node of a binary search tree (BST). Write an algorithm BSTHeight(x) that determines the height of the tree. What would be its running time? Alg: BSTHeight(x) if (x==NULL) return -1; else return max(BSTHeight(left[x]), BSTHeight(right[x]))+1; This program should not take more than O(n) time. Why?
28 Problems In a binary search tree, are the insert and delete operations commutative? Insert: Start with only 10 in a BST and try to insert 4 followed by 6 Then change the order of insertions and try again Delete Delete 5 followed by 6 in the following tree Then Delete 6 followed by 5 4 2 6 5 8 7 4 2 8 7 4 2 7 8