DOC PREVIEW
FIU COT 5407 - Binary Search Trees

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Binary Search TreesSlide 2BST – RepresentationBinary Search Tree PropertyInorder TraversalCorrectness of Inorder-WalkQuerying a Binary Search TreeTree SearchIterative Tree SearchFinding Min & MaxPredecessor and SuccessorPseudo-code for SuccessorSlide 13BST Insertion – PseudocodeAnalysis of InsertionExercise: Sorting Using BSTsTree-Delete (T, x)Slide 18Deletion – PseudocodeSlide 20Correctness of Tree-DeleteSlide 22Red-black trees: OverviewRed-black TreeRed-black Tree – ExampleRed-black PropertiesHeight of a Red-black TreeSlide 28Hysteresis : or the value of lazynessBinary Search TreesBinary Search TreesMany of the slides are from Prof. Plaisted’s resources at University of North Carolina at Chapel HillBinary Search TreesView today as data structures that can support dynamic set operations.»Search, Minimum, Maximum, Predecessor, Successor, Insert, and Delete.Can be used to build»Dictionaries.»Priority Queues.Basic operations take time proportional to the height of the tree – O(h).BST – Representation Represented by a linked data structure of nodes.root(T) points to the root of tree T.Each node contains fields: »key»left – pointer to left child: root of left subtree.»right – pointer to right child : root of right subtree.»p – pointer to parent. p[root[T]] = NIL (optional).Binary Search Tree PropertyStored keys must satisfy the binary search tree property. y in left subtree of x, then key[y]  key[x]. y in right subtree of x, then key[y]  key[x].5626 20018281902131224 27Inorder TraversalInorder-Tree-Walk (x)1. if x  NIL2. then Inorder-Tree-Walk(left[p])3. print key[x]4. Inorder-Tree-Walk(right[p])Inorder-Tree-Walk (x)1. if x  NIL2. then Inorder-Tree-Walk(left[p])3. print key[x]4. Inorder-Tree-Walk(right[p])How long does the walk take?Can you prove its correctness?The binary-search-tree property allows the keys of a binary search tree to be printed, in (monotonically increasing) order, recursively.5626 20018281902131224 27Correctness 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).Querying a Binary Search TreeAll dynamic-set search operations can be supported in O(h) time.h = (lg n) for a balanced binary tree (and for an average tree built by adding nodes in random order.)h = (n) for an unbalanced tree that resembles a linear chain of n nodes in the worst case.Tree SearchTree-Search(x, k)1. if x = NIL or k = key[x]2. then return x 3. if k < key[x]4. then return Tree-Search(left[x], k)5. else return Tree-Search(right[x], k)Tree-Search(x, k)1. if x = NIL or k = key[x]2. then return x 3. if k < key[x]4. then return Tree-Search(left[x], k)5. else return Tree-Search(right[x], k)Running time: O(h)5626 20018281902131224 27Iterative Tree SearchIterative-Tree-Search(x, k)1. while x  NIL and k  key[x]2. do if k < key[x]3. then x  left[x]4. else x  right[x]5. return x Iterative-Tree-Search(x, k)1. while x  NIL and k  key[x]2. do if k < key[x]3. then x  left[x]4. else x  right[x]5. return x The iterative tree search is more efficient on most computers.The recursive tree search is more straightforward.5626 20018281902131224 27Finding Min & MaxTree-Minimum(x) Tree-Maximum(x)1. while left[x]  NIL 1. while right[x]  NIL 2. do x  left[x] 2. do x  right[x]3. return x 3. return xTree-Minimum(x) Tree-Maximum(x)1. while left[x]  NIL 1. while right[x]  NIL 2. do x  left[x] 2. do x  right[x]3. return x 3. return xQ: How long do they take?The binary-search-tree property guarantees that:» The minimum is located at the left-most node.» The maximum is located at the right-most node.Predecessor and SuccessorSuccessor of node x is the node y such that key[y] is the smallest key greater than key[x].The successor of the largest key is NIL.Search consists of two cases.»If node x has a non-empty right subtree, then x’s successor is the minimum in the right subtree of x.»If node x has an empty right subtree, then:•As long as we move to the left up the tree (move up through right children), we are visiting smaller keys.•x’s successor y is the node that x is the predecessor of (x is the maximum in y’s left subtree).•In other words, x’s successor y, is the lowest ancestor of x whose left child is also an ancestor of x.Pseudo-code for SuccessorTree-Successor(x) if right[x]  NIL 2. then return Tree-Minimum(right[x]) 3. y  p[x] 4. while y  NIL and x = right[y]5. do x  y6. y  p[y]7. return yTree-Successor(x) if right[x]  NIL 2. then return Tree-Minimum(right[x]) 3. y  p[x] 4. while y  NIL and x = right[y]5. do x  y6. y  p[y]7. return yCode for predecessor is symmetric.Running time: O(h)5626 20018281902131224 27Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.BST Insertion – Pseudocode Tree-Insert(T, z)1. y  NIL2. x  root[T]3. while x  NIL4. do y  x5. if key[z] < key[x]6. then x  left[x]7. else x  right[x]8. p[z]  y9. if y = NIL10. then root[t]  z11. else if key[z] < key[y]12. then left[y]  z13. else right[y]  zTree-Insert(T, z)1. y  NIL2. x  root[T]3. while x  NIL4. do y  x5. if key[z] < key[x]6. then x  left[x]7. else x  right[x]8. p[z]  y9. if y = NIL10. then root[t]  z11. else if key[z] < key[y]12. then left[y]  z13. else right[y]  zChange the dynamic set represented by a BST.Ensure the binary-search-tree property holds after change.Insertion is easier than deletion.5626 2001828190213122427Analysis of InsertionInitialization: O(1)While loop in lines 3-7 searches for place to insert z, maintaining parent y.This takes O(h) time.Lines 8-13 insert the value: O(1)  TOTAL: O(h) time to insert a node.Tree-Insert(T, z)1. y  NIL2. x 


View Full Document

FIU COT 5407 - Binary Search Trees

Download Binary Search Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Binary Search Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Binary Search Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?