Slide #1.

Computer Science and Software Engineering University of Wisconsin - Platteville 10. Binary Search Tree Yan Shi CS/SE 2630 Lecture Notes Partially adopted from C++ Plus Data Structure textbook slides
More slides like this

Slide #2.

Review: Binary Search in a Sorted Array Based List  Examines the element in the middle of the array. Is it the sought item? If so, stop searching. Is the middle element too small? Then start looking in second half of array. Is the middle element too large? Then begin looking in first half of the array.  Repeat the process in the half of the list that should be examined next.  Stop when item is found, or when there is nowhere else to look and item has not been found.
More slides like this

Slide #3.

Example item = 45 15 26 info[0] [1] 38 [2] 57 [3] 62 [4] 78 [5] 84 [6] 91 [7] 108 119 [8] [9]
More slides like this

Slide #4.

Example item = 45 15 26 info[0] [1] 38 [2] 57 [3] first 62 [4] 78 [5] [6] 91 [7] 108 119 [8] [9] midPoint last LESS 15 26 info[0] [1] first 84 last = midPoint - 1 38 [2] midPoint 57 [3] 62 [4] 78 [5] 84 [6] 91 [7] last GREATER first = midPoint + 1 108 119 [8] [9]
More slides like this

Slide #5.

item = 45 15 info[0] 26 [1] 38 [2] 57 [3] 62 [4] 78 [5] 84 [6] 91 [7] 108 119 [8] [9] 108 119 [8] [9] first, last midPoint GREATER 15 26 info[0] [1] 38 [2] 57 [3] first = midPoint + 1 62 [4] 78 [5] 84 [6] 91 [7] first, midPoint, last LESS last = midPoint - 1
More slides like this

Slide #6.

item = 45 15 info[0] 26 38 [1] [2] last first 57 [3] first > last 62 [4] 78 [5] 84 [6] 91 [7] found = false 108 119 [8] [9]
More slides like this

Slide #7.

Motivations for Binary Search Tree  array-based list: — fast search: binary search O(log2N) — slow insertion/deletion  linear linked list: — fast insertion, deletion — slow search  Can we have fast search, addition and deletion? — Binary search tree
More slides like this

Slide #8.

What is a tree? Jake’s Pizza Shop Owner Jake Manager Carol Waitress Joyce Chef Waiter Chris Cook Max Brad Helper Len
More slides like this

Slide #9.

A Tree Has a Root Node ROOT NODE Owner Jake Manager Carol Waitress Joyce Chef Waiter Chris Cook Max Brad Helper Len
More slides like this

Slide #10.

Leaf Nodes have No Children Owner Jake Manager Carol Waitress Joyce LEAF NODES Chef Waiter Chris Cook Max Brad Helper Len
More slides like this

Slide #11.

A Tree Has Levels LEVEL 0 Owner Jake Manager Carol Waitress Joyce Chef Waiter Chris Cook Max Brad Helper Len
More slides like this

Slide #12.

Level One Owner Jake Manager Carol LEVEL 1 Waitress Joyce Chef Waiter Chris Cook Max Brad Helper Len
More slides like this

Slide #13.

Level Two Owner Jake Manager Carol Chef Brad LEVEL 2 Waitress Joyce Waiter Chris Cook Max Helper Len
More slides like this

Slide #14.

A Subtree Owner Jake Manager Carol Waitress Joyce Chef Waiter Chris LEFT SUBTREE OF ROOT NODE Cook Max Brad Helper Len
More slides like this

Slide #15.

Binary Tree  A binary tree is a structure in which: — Each node can have at most two children, and in which a unique path exists from the root to every other node. — The two children of a node are called the left child and the right child, if they exist.
More slides like this

Slide #16.

Implementing a Binary Tree with Pointers and Dynamic Data V Q L T E A K How many leaf nodes? descendant of Q? S ancestors of Q?
More slides like this

Slide #17.

Binary Search Tree (BST)  A special kind of binary tree in which: — Each node contains a distinct data value — The key values in the tree can be compared using “greater than” and “less than”, and — The key value of each node in the tree is less than every key value in its right sub-tree, and greater than every key value in its left sub-tree.  Similar as sorted list, the order is maintained when inserting new items into the tree
More slides like this

Slide #18.

Example  Insert ‘J’ ‘E’ ‘F’ ‘T’ ‘A’ to an empty BST. ‘J’ ‘T’ ‘E’ ‘A’ ‘F’  Insert ‘A’ ‘E’ ‘F’ ‘J’ ‘T’ to an empty BST. The shape of a BST depends on • its key values and • their order of insertion ‘A’ ‘E’ ‘F’ ‘J’ ‘T’
More slides like this

Slide #19.

Exercise ‘J’ ‘T’ ‘E’ ‘A’ ‘H’ ‘M’ ‘P’ ‘K’ Insert nodes containing these values in this order: ‘D’ ‘B’ ‘L’ ‘Q’ ‘S’ ‘V’ ‘Z’
More slides like this

Slide #20.

How many nodes do we have? ‘J’ ‘T’ ‘E’ ‘A’ ‘D’ ‘B’ ‘V’ ‘M’ ‘H’ ‘Z’ ‘P’ ‘K’ ‘L’ ‘Q’ ‘S’
More slides like this

Slide #21.

Count Nodes in a BST  CountNodes Algorithm v1: if left(tree) is NULL AND right(tree) is NULL return 1 else return CountNodes(Left(tree)) + CountNodes(Right(tree)) + 1 What if Left(tree) is NULL?
More slides like this

Slide #22.

Count Nodes in a BST  CountNodes Algorithm v2: if (Left(tree) is NULL) AND (Right(tree) is NULL) return 1 else if Left(tree) is NULL return CountNodes(Right(tree)) + 1 else if Right(tree) is NULL return CountNodes(Left(tree)) + 1 else return CountNodes(Left(tree)) + CountNodes(Right(tree)) + 1 What if the initial tree is NULL?
More slides like this

Slide #23.

Count Nodes in a BST  CountNodes Algorithm v3: if tree is NULL return 0 else if (Left(tree) is NULL) AND (Right(tree) is NULL) return 1 else if Left(tree) is NULL return CountNodes(Right(tree)) + 1 else if Right(tree) is NULL return CountNodes(Left(tree)) + 1 else return CountNodes(Left(tree)) + CountNodes(Right(tree)) + 1 Can we simplify it somehow?
More slides like this

Slide #24.

Count Nodes in a BST  CountNodes Algorithm Final Version: if tree is NULL return 0 else return CountNodes(Left(tree)) + CountNodes(Right(tree)) + 1 Does it cover all possible situations?
More slides like this

Slide #25.

Is ‘F’ in the binary search tree? ‘J’ ‘T’ ‘E’ ‘A’ ‘D’ ‘B’ ‘V’ ‘M’ ‘H’ ‘Z’ ‘P’ ‘K’ ‘L’ ‘Q’ ‘S’
More slides like this

Slide #26.

Search an item in a BST  Search Algorithm Given a BST tree and an item to find: if tree is NULL found = false else if ( item < current node’s info ) Search( left(tree), item ) else if ( item > current node’s info ) Search( right(tree), item ) else found = true  Similar algorithm for retrieving an item given its key
More slides like this

Slide #27.

Insert an item to a BST  Use recursion  Base case: — tree is NULL (empty tree or leaf node’s left/right) — CANNOT add  item already in the BST!  General case: — if item < tree->info, Insert item to left(tree) — else if item > tree->info, Insert item to right(tree)
More slides like this

Slide #28.

The “tree” Parameter bool BST::Insert( TNode * tree, Type item ) { if ( tree == NULL ) { tree = new TNode( item ); return true; } else if ( item < tree->info ) return Insert( tree->left, item ); else if ( item > tree->info ) return Insert( tree->right, item ); else return false; } //Is it correct?
More slides like this

Slide #29.

The “tree” parameter  Treat “tree” as a pointer pointing within the tree!  What happens when creating a new node? — tree become a real address instead of NULL!  Make “tree” a reference parameter!
More slides like this

Slide #30.

The “tree” Parameter bool BST::Insert( TNode * & tree, Type item ) { if ( tree == NULL ) { tree = new TNode( item ); return true; } else if ( item < tree->info ) return Insert( tree->left, item ); else if ( item > tree->info ) return Insert( tree->right, item ); else return false; } //tree is a reference parameter!
More slides like this

Slide #31.

Delete an item in the BST  Use recursion  Base case: — If item's key matches key in Info(tree), delete node pointed to by tree. — If tree is empty, cannot delete.  General case: — if item < tree->info, Delete item in left(tree) — else if item > tree->info, Delete item in right(tree) How to delete a node?
More slides like this

Slide #32.

Code for Delete bool BST::Delete( TNode * & tree, Type item ) { we are changing the structure of the tree! if ( tree == NULL ) return false; if ( item < tree->info ) return Delete( tree->left, item ); else if ( item > tree->info ) return Delete( tree->right, item ); else { // How to do this? DeleteNode( tree ); return true; } }
More slides like this

Slide #33.

Deleting a Leaf Node
More slides like this

Slide #34.

Deleting a Node with One Child
More slides like this

Slide #35.

Deleting a Node with Two Children
More slides like this

Slide #36.

Delete a Node in BST  Algorithm: if (Left(tree) is NULL) AND (Right(tree) is NULL) Set tree to NULL else if Left(tree) is NULL Set tree to Right(tree) else if Right(tree) is NULL Set tree to Left(tree) else Find predecessor Set Info(tree) to Info(predecessor) Delete predecessor Indirect Recursion!
More slides like this

Slide #37.

How to find a predecessor?  Algorithm: if ( tree->left != NULL ) { tree = tree->left; while (tree->right != NULL) tree = tree->right; predecessor = tree->info; }
More slides like this

Slide #38.

Tree Traversal  In-order — from smallest to largest  pre-order — current info first — then left — then right  post-order — left first — then right — then current info
More slides like this

Slide #39.

In-Order Print  Algorithm: if tree is not NULL InOrderPrint( left(tree) ) print tree->info InOrderPrint( right(tree) )  How about pre-order and post-order print?
More slides like this

Slide #40.

Big-3 for BST  Destructor: — need to delete all node — traverse the tree in which order? post-order!  Copy constructor and assignment operator: — How to copy a tree? — traverse the tree in which order? — How to implement operator=? pre-order!
More slides like this

Slide #41.

Iterative Solutions for BST  Binary Search: Has( item )  Insert: Add( item )  Delete: Remove( item )
More slides like this

Slide #42.

Iterative Solution for Search  Algorithm for search: Has( item ) Set nodePtr to tree while more elements to search if item < Info(nodePtr) Set nodePtr to Left(nodePtr) else if item > Info(nodePtr) Set nodePtr to Right(nodePtr) else return true return false
More slides like this

Slide #43.

Iterative Solution for Insert 1. create a node to contain the new item 2. find the insertion place — similar as the previous search — need to keep track of parent as well 3. insert new node — insert as either the left or right child of parent
More slides like this

Slide #44.

Example: Insert Insert 13 to the tree
More slides like this

Slide #45.

Insert 13 to the tree
More slides like this

Slide #46.

Insert 13 to the tree
More slides like this

Slide #47.

Insert 13 to the tree
More slides like this

Slide #48.

Insert 13 to the tree
More slides like this

Slide #49.

Iterative Solution for Delete TNode * node, * parent; bool found = false; FindNode( item, found, node, parent ); if ( found == false ) return false; if ( node == root ) DeleteNode( root ); else if ( parent->left == node ) DeleteNode( parent->left ); //why parent->left? else DeleteNode( parent->right ); return true; is it really iterative if we use the previous DeleteNode function?
More slides like this

Slide #50.

nodePtr and parentPtr Are External to the Tree
More slides like this

Slide #51.

parentPtr is External to the Tree, but parentPtr-> left is an Actual Pointer in the Tree
More slides like this

Slide #52.

Full and Complete BST  Full Binary Tree: A binary tree in which all of the leaves are on the same level and every non-leaf node has two children  Complete Binary Tree: A binary tree that is either full or full through the next-to-last level, with the leaves on the last level as far to the left as possible
More slides like this

Slide #53.

Examples
More slides like this

Slide #54.

Array Representation of BST For any tree node nodes[index] • left child: nodes[index*2 + 1] • right child: nodes[index*2 + 2] • parent: nodes[(index – 1)/2]
More slides like this

Slide #55.

Array Representation of NonComplete BST  Use dummy values to fill the space
More slides like this