Binary Search Trees Nelson Padua Perez Chau Wen Tseng Department of Computer Science University of Maryland College Park Overview Binary trees Binary search trees Find Insert Delete Hierarchical Data Structures One to many relationship between elements Tree Single parent multiple children Binary tree Tree with 0 2 children per node Tree Binary Tree Trees Terminology Root no predecessor Leaf no successor Interior non leaf Height distance from root to leaf Root node Interior nodes Leaf nodes Height Types of Binary Trees Degenerate only one child Balanced mostly two children Complete always two children Degenerate binary tree Balanced binary tree Complete binary tree Binary Trees Properties Degenerate Height O n for n nodes Similar to linear list Degenerate binary tree Balanced Height O log n for n nodes Useful for searches Balanced binary tree Binary Search Trees Key property Value at node Smaller values in left subtree Larger values in right subtree Example X Y X X Z Y Z Binary Search Trees Examples 5 10 5 2 10 45 30 5 45 30 2 25 45 2 10 25 30 25 Binary search trees Non binary search tree Binary Tree Implementation Class 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 NonEmpty void insert Value data1 Iterative Search of Binary Tree Node 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 Tree Node Find Node n Value key if n null Not found return n else if n data key Found it return n else if n data key In left subtree return Find n left key else In right subtree return Find n right key Find root keyValue Example Binary Searches Find 2 10 5 2 10 2 left 30 25 5 5 2 left 45 2 2 2 found 5 2 left 45 30 10 25 2 2 found Example Binary Searches Find 25 10 5 2 10 25 right 30 25 5 30 25 left 45 2 25 25 found 5 25 right 45 30 10 45 25 left 30 25 left 10 25 right 25 25 found 25 Binary Search Properties Time of search Proportional to height of tree Balanced binary tree O log n time Degenerate tree O n time Like searching linked list unsorted array Requires Ability to compare key values Binary Search Tree Construction How to build maintain binary trees Insertion Deletion Maintain key property invariant Smaller values in left subtree Larger values in right subtree Binary Search Tree Insertion Algorithm 1 Perform search for value X 2 Search will end at node Y if X not in tree 3 If X Y insert new leaf X as new left subtree for Y 4 If X Y insert new leaf X as new right subtree for Y Observations O log n operation for balanced tree Insertions may unbalance tree Example Insertion Insert 20 10 5 10 20 right 30 20 left 30 25 20 left 2 25 20 45 Insert 20 on left Binary Search Tree Deletion Algorithm 1 Perform search for value X 2 If X is a leaf delete X 3 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 subtree Observation O log n operation for balanced tree Deletions may unbalance tree Example Deletion Leaf Delete 25 10 5 2 10 25 right 30 25 10 5 30 25 left 45 25 25 delete 2 30 45 Example Deletion Internal Node Delete 10 10 5 2 5 30 25 5 45 Replacing 10 with largest value in left subtree 2 5 30 25 2 45 Replacing 5 with largest value in left subtree 2 30 25 45 Deleting leaf Example Deletion Internal Node Delete 10 10 5 2 25 30 25 5 45 Replacing 10 with smallest value in right subtree 2 25 30 25 5 45 Deleting leaf 2 30 45 Resulting tree
View Full Document
Unlocking...