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 22Still need to talk about …Binary Search Trees Eileen KraemerCSCI 2720The University of GeorgiaSpring 2007OverviewBinary 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 {Node insert ( Value data1 ) { … }}Class NonEmptyNode {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,key_val );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 );else // In right subtreereturn Find( n.right );}Find( root );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 – InsertionAlgorithmPerform search for value XSearch will end at node Y (if X not in tree)If X < Y, insert new leaf X as new left subtree for Y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 Perform search for value XIf X is a leaf, delete XElse // must delete internal nodea) Replace with largest value Y on left subtree OR smallest value Z on right subtreeb) 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 treeStill need to talk about …Static BSTs (we looked at some example)Optimal BSTsProbability-balanced treesMedian split treesbut in the meantime, let’s jump forward to AVL