CSE310 Lecture 15: Binary Search TreesTopics of this lectureBinary Search TreesExample, Tree TraversalsRepresentation of Binary TreesInorder and Preorder Tree WalksTree SearchMinimum and MaximumSuccessorExample: How to Insert a Node?InsertionExample: How to Delete a Node?DeletionTree HeightBalanced Binary Search [email protected] Lecture 15: Binary Search TreesCSE310 Lecture 15: Binary Search TreesGuoliang XueComputer Science and EngineeringArizona State [email protected] of this lectureTopics of this lectureBinary Search TreesRepresentationSearchMin and MaxSuccessorInsertion[email protected] Search TreesBinary Search TreesA search tree is a data structure that supports both dictionary and priority queue operations:Minimum, Maximum;Predecessor, Successor;Search, Insert, Delete.A binary search tree is a binary tree with the following property: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? [email protected], Tree TraversalsExample, Tree TraversalsPreorder: root - left subtree - right subtree7 5 5 6 8 9 5 2 5 6 5 9Inorder: left subtree - root - right subtree5 5 6 7 8 9 2 5 5 5 6 9Postorder: left subtree - right subtree - root5 6 5 9 8 7 2 5 9 6 5 55 6 95 875 962 [email protected] of Binary TreesRepresentation of Binary TreesA tree node is defined by an object of at least four fields:Tree-nodedata: string // also called keyparent, left, right: pointer to a tree node leftnilrightrootdataleftparentrightdataleftparentrightdataroot.left = xroot.right = yx.parent = rooty.parent = [email protected] and Preorder Tree WalksInorder and Preorder Tree WalksInorder-Tree-Walk(x)1. if x nil then2. 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 then2. print(x.data)3. Preorder-Tree-Walk(x.left)4. Preorder-Tree-Walk(x.right)[email protected] SearchTree SearchTree-Search(root, key)1. if root = nil or root.data = key then2. return root3. if key < root.data4. 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 do2. if key < root.data3. then root = root.left4. else root = root.right5. return [email protected] and MaximumMinimum and MaximumTree-Minimum(root)1. while root nil and root.left nil do2. root = root.left3. return rootTree-Maximum(root)1. while root nil and root.right nil do2. root = root.right3. return root2 437917 201815613The running timeis O(h)[email protected](x)1. if x.right nil then2. return Tree-Minimum(x.right) //e.g., 15 --> 173. y := x.parent // e.g., node 134. while y nil and x = y.right do // find a "right" parent5. x := y6. y := y.parent7. return y2 43713917 201815x = &(13) y = &(7)x = &(7) y = &(6)x = &(6) y = &(15)now x y.right6The running time is O(h): it either moves up or [email protected]: How to Insert a Node?Example: How to Insert a Node?2 9512181917141413152 9512181917141513Guoliang.Xue@asu.edu11InsertionInsertionTree-Insertion(T, key)1. z := new-treenode(key, nil, nil, nil)2. x := root[T]3. if x = nil then root[T] = z return else4. while x nil do5. y := x6. if key < x.data7. then x = x.left8. else x = x.right9. z.parent = y10. if key < y.data11. then y.left := z12. else y.right := zz := new-treenode(k, p, l, r)z.data := kz.parent := pz.left := lz.right := rThe running time is O(h): it moves down from [email protected]: How to Delete a Node?Example: How to Delete a Node?Three cases:15531067231618201312z1553106723161820121553106723182013121563107231618201312y15536231618201312z107(1)no child15531067231618201312z(2)has one child15531067231618201312zy(3)[email protected](T, z) // z is the index to the node to delete1. if z.left = nil or z.right = nil2. then y := z3. else y := Tree-Successor(z)4. if y.left nil5. then x = y.left6. else x = y.right7. if x nil8. then x.parent := y.parent9. if y.parent = nil10. then root[T] = x11. else if y = y.parent.left // y is the left child of its parent12. then y.parent.left := x13. else y.parent.right := x14. if y z15. then z.data := y.data 16. // if a node has other fields, copy all17. return yO(h)The running time is O(h), there is no other [email protected] HeightTree HeightAll 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)Theorem: The average height of a randomly built (insertion) binary search tree on n distinct keys is O(lgn) h = n - 1 = O(n)[email protected] Binary Search TreesBalanced Binary Search TreesWe 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 [email protected] the tree in pr eorder : *x+*abc {prefix notation} Print the tree in inorder :x*a*b + c {infix notation}(x*(a*b + c)) Print the tree in postorder:xab*c+* {postfix notation}x*+*[email protected]Binary Search Trees and Its OperationsMaterials 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
View Full Document
Unlocking...