CSE310 Lecture 15 Binary Search Trees Guoliang Xue Computer Science and Engineering Arizona State University Guoliang Xue asu edu Topics of this lecture Binary Search Trees Representation Search Min and Max Successor Insertion Deletion 2 Guoliang Xue asu edu Binary Search Trees A search tree is a data structure that supports both dictionary and priority queue operations A binary search tree is a binary tree with the following property Minimum Maximum Predecessor Successor Search Insert Delete For each node i in the tree if x is any node in its left sub tree and y is any node in its right sub tree then key x key i key y Is a heap a binary search tree No 3 Guoliang Xue asu edu Example Tree Traversals 7 5 5 5 8 6 2 5 9 6 5 Preorder root left subtree right subtree 755689 525659 Inorder left subtree root right subtree 556789 255569 Postorder left subtree right subtree root 565987 259655 4 9 Guoliang Xue asu edu Representation of Binary Trees A tree node is defined by an object of at least four fields Tree node data string also called key parent left right pointer to a tree node root left x root root right y nil x parent root left data right y parent root y x parent parent left data right left data right 5 Guoliang Xue asu edu Inorder and Preorder Tree Walks Inorder Tree Walk x 1 if x nil then 2 Inorder Tree Walk x left left x 3 print x data data x 4 Inorder Tree Walk x right right x Preorder Tree Walk x 1 if x nil then 2 print x data 3 Preorder Tree Walk x left 4 Preorder Tree Walk x right 6 Guoliang Xue asu edu Tree Search Tree Search root key 1 if root nil or root data key then 2 return root 3 if key root data 4 then return Tree Search root left key 5 else return Tree Search root right key Iterative Tree Search root key 1 while root nil and root data key do 2 if key root data 3 then root root left 4 else root root right 5 return root 7 Guoliang Xue asu edu Minimum and Maximum Tree Minimum root 1 while root nil and root left nil do 2 root root left 3 return root Tree Maximum root 1 while root nil and root right nil do 2 root root right 15 3 return root 6 7 The running time 3 17 13 is O h 2 4 8 18 20 9 Guoliang Xue asu edu Successor Successor x 1 if x right nil then 2 return Tree Minimum x right e g 15 17 3 y x parent e g node 13 4 while y nil and x y right do find a right parent 5 x y 6 y y parent 21 7 return y x 13 y 7 15 x 7 y 6 18 6 x 6 y 15 7 17 20 3 now x y right 13 2 4 9 The running time is O h 9it eitherGuoliang Xue asu edu moves up or down Example How to Insert a Node 14 12 14 5 2 18 19 15 9 13 17 12 5 2 18 19 15 9 13 17 14 10 Guoliang Xue asu edu Insertion Tree Insertion T key 1 z new treenode key nil nil nil 2 x root T 3 if x nil then root T z return else 4 5 6 7 8 9 10 11 12 while x nil do y x if key x data then x x left else x x right z parent y if key y data then y left z else y right z 11 z new treenode k p l r z data k z parent p z left l z right r The running time is O h it moves down from root Guoliang Xue asu edu Example How to Delete a Node Three cases 15 5 3 1 5 12 20 18 13 z 10 no child 15 16 3 23 2 3 10 has one child 3 20 18 13 15 3 16 12 10 y 6 7 13 7 15 y 6 5 23 6 7 z 20 18 12 10 23 6 3 23 7 15 5 16 z 12 18 6 7 15 20 12 10 6 5 16 z 3 18 10 23 6 16 12 20 13 15 5 3 20 13 7 12 18 16 12 10 23 20 13 18 23 7 Guoliang Xue asu edu Deletion Tree Deletion T z z is the index to the node to delete 1 if z left nil or z right nil 2 then y z 3 else y Tree Successor z 4 if y left nil O h 5 then x y left 6 else x y right The running time 7 if x nil is O h there is 8 then x parent y parent no other loops 9 if y parent nil 10 then root T x 11 else if y y parent left y is the left child of its parent 12 then y parent left x 13 else y parent right x 14 if y z 15 then z data y data 16 if a node has other fields copy all 17 return y 13 Guoliang Xue asu edu Tree Height All dynamic set operations on a binary search are of O h What is the relationship between h and n the number of keys stored in the tree For n 15 h 3 lg n 1 1 O lgn h 7 n 1 2 1 O n h n 1 O n Theorem The average height of a randomly built insertion binary search tree on n distinct keys is O lgn 14 Guoliang Xue asu edu Balanced Binary Search Trees We note that binary search tree is useful data structure We also note that most operations related to binary search trees have worst case time complexity proportional to the height of the tree Therefore it is good to have a balanced tree without too much extra cost We will study one such tree the red black tree 15 Guoliang Xue asu edu Applications Print the tree in preorder x abc prefix notation x Print the tree in inorder x a b c infix notation x a b c c a b Print the tree in postorder xab c postfix notation 16 Guoliang Xue asu edu Summary Binary Search Trees and Its Operations Materials in Sections 12 1 12 3 and 13 1 Exercises 12 1 1 12 2 1 It is important that you understand search insertion deletion and successor of binary search trees 17 Guoliang Xue asu edu
View Full Document
Unlocking...