Binary Search TreesOverviewHierarchical Data StructuresTreesTypes of Binary TreesBinary Trees PropertiesBinary Search TreesSlide 8Binary Tree ImplementationPolymorphic Binary Tree Implement.Iterative Search of Binary TreeRecursive Search of Binary TreeExample Binary SearchesSlide 14Binary Search PropertiesBinary Search Tree ConstructionBinary Search Tree – InsertionExample InsertionBinary Search Tree – DeletionExample Deletion (Leaf)Example Deletion (Internal Node)Slide 22Binary Search Trees Nelson Padua-PerezChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewBinary treesBinary search treesFindInsertDeleteHierarchical Data StructuresOne-to-many relationship between elements TreeSingle parent, multiple childrenBinary treeTree with 0–2 children per nodeTree Binary TreeTreesTerminologyRoot no predecessorLeaf no successorInterior non-leafHeight distance from root to leafRoot nodeLeaf nodesInterior nodesHeightTypes of Binary TreesDegenerate – only one childBalanced – mostly two childrenComplete – always two childrenDegenerate binary treeBalanced binary treeComplete binary treeBinary Trees PropertiesDegenerateHeight = O(n) for n nodesSimilar to linear listBalancedHeight = O( log(n) ) for n nodesUseful for searchesDegenerate binary treeBalanced binary treeBinary Search TreesKey propertyValue at nodeSmaller values in left subtreeLarger values in right subtreeExampleX > YX < ZYXZBinary Search TreesExamplesBinary search treesNon-binary search tree510302 25 45510452 25 305103022545Binary Tree ImplementationClass Node {Value data; Node left, right; // null if empty void insert ( Value data1 ) { … }void delete ( Value data2 ) { … }Node find ( Value data3 ) { … }…}Polymorphic Binary Tree Implement.Interface Node {Node insert ( Value data1 ) { … }}Class EmptyNode implements Node {Node insert ( Value data1 ) { … }}Class NonEmptyNode implements Node {Value data; Node left, right; // Either Empty or NonEmptyvoid insert ( Value data1 ) { … }}Iterative Search of Binary TreeNode Find( Node n, Value key) { while (n != null) { if (n.data == key) // Found it return n;if (n.data > key) // In left subtree n = n.left;else // In right subtree n = n.right; } return null;}Find( root, keyValue );Recursive Search of Binary TreeNode Find( Node n, Value key) {if (n == null) // Not foundreturn( n );else if (n.data == key) // Found itreturn( n );else if (n.data > key) // In left subtreereturn Find( n.left, key );else // In right subtreereturn Find( n.right, key );}Find( root, keyValue );Example Binary SearchesFind ( 2 )510302 25 45510302254510 > 2, left5 > 2, left2 = 2, found5 > 2, left2 = 2, foundExample Binary SearchesFind ( 25 )510302 25 45510302254510 < 25, right30 > 25, left25 = 25, found5 < 25, right45 > 25, left30 > 25, left10 < 25, right25 = 25, foundBinary Search PropertiesTime of searchProportional to height of treeBalanced binary treeO( log(n) ) timeDegenerate treeO( n ) timeLike searching linked list / unsorted arrayRequiresAbility to compare key valuesBinary Search Tree ConstructionHow to build & maintain binary trees?InsertionDeletionMaintain key property (invariant)Smaller values in left subtreeLarger values in right subtreeBinary Search Tree – InsertionAlgorithm1. Perform search for value X2. Search will end at node Y (if X not in tree)3. If X < Y, insert new leaf X as new left subtree for Y4. If X > Y, insert new leaf X as new right subtree for YObservationsO( log(n) ) operation for balanced treeInsertions may unbalance treeExample InsertionInsert ( 20 )510302 25 4510 < 20, right30 > 20, left25 > 20, leftInsert 20 on left20Binary Search Tree – DeletionAlgorithm 1. Perform search for value X2. If X is a leaf, delete X3. Else // must delete internal nodea) Replace with largest value Y on left subtree OR smallest value Z on right subtreeb) Delete replacement value (Y or Z) from subtreeObservationO( log(n) ) operation for balanced treeDeletions may unbalance treeExample Deletion (Leaf)Delete ( 25 )510302 25 4510 < 25, right30 > 25, left25 = 25, delete510302 45Example Deletion (Internal Node)Delete ( 10 )510302 25 4555302 25 4525302 25 45Replacing 10 with largest value in left subtreeReplacing 5 with largest value in left subtreeDeleting leafExample Deletion (Internal Node)Delete ( 10 )510302 25 45525302 25 45525302 45Replacing 10 with smallest value in right subtreeDeleting leaf Resulting
View Full Document
Unlocking...