CMSC 132 Object Oriented Programming II Trees Binary Search Trees Department of Computer Science University of Maryland College Park 1 Trees Trees are hierarchical data structures One to many relationship between elements Parent node Tree node element Contains data Referred to by only 1 parent node Contains links to any number of children nodes Children nodes 2 Trees Terminology Root node with no parent Leaf all nodes with no children Interior all nodes with children Root node Interior nodes Leaf nodes 3 Trees Terminology Sibling node with same parent Descendent children nodes their descendents Subtree portion of tree that is a tree by itself a node and its descendents Siblings Subtree 4 Trees Terminology Level is a measure of a node s distance from root Definition of level If node is the root of the tree its level is 1 Else the node s level is 1 its parent s level Height depth max level of any node in tree Height 3 5 Binary Trees Binary tree Tree with 0 2 children per node Left right child subtree Parent Left Child Right Child Binary Tree 6 Tree Traversal Often we want to 1 Find all nodes in tree 2 Determine their relationship Can do this by 1 Walking through the tree in a prescribed order 2 Visiting the nodes as they are encountered Process is called tree traversal 7 Tree Traversal Goal Visit every node in binary tree Approaches Depth first Preorder Inorder parent before children left child parent right child Postorder children before parent Breadth first closer nodes first 8 Tree Traversal Methods Pre order 1 Visit node first 2 Recursively visit left subtree 3 Recursively visit right subtree In order 1 Recursively visit left subtree 2 Visit node second 3 Recursively right subtree Post order 1 Recursively visit left subtree 2 Recursively visit right subtree 3 Visit node last 9 Tree Traversal Methods Breadth first BFS Node n Queue Q new Queue Q enqueue n insert node into Q while Q empty n Q dequeue remove next node if n isEmpty visit n visit node Q enqueue n Left insert left subtree in Q Q enqueue n Right insert right subtree in Q 10 Tree Traversal Examples Pre order prefix 23 84 In order infix 2 3 8 4 Post order postfix 23 84 Breadth first 2 3 8 4 2384 Expression tree 11 Tree Traversal Examples Pre order 44 17 32 78 50 48 62 88 Sorted order In order 17 32 44 48 50 62 78 88 Post order 32 17 48 62 50 88 78 44 Breadth first 44 78 17 88 50 32 48 62 Binary search tree 44 17 78 32 50 88 48 62 12 Types of Binary Trees Degenerate Mostly 1 child node Height O n Similar to linear list Degenerate binary tree Balanced Mostly 2 child node Height O log n Useful for searches Balanced binary tree 13 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 14 Binary Search Trees Examples 5 10 2 5 10 45 30 5 45 30 2 25 45 2 10 25 30 25 Binary search trees Non binary search tree 15 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 16 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 17 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 18 Example Binary Searches Find 2 10 5 5 10 2 left 30 5 2 left 2 5 2 left 45 2 2 found 2 2 found 2 25 30 45 10 25 19 Example Binary Searches Find 25 10 5 5 10 25 right 30 30 25 left 2 45 25 25 found 2 25 5 25 right 45 25 left 30 25 left 30 45 10 10 25 right 25 25 found 25 20 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 21 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 22 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 23 Example Insertion Insert 20 10 5 10 20 right 30 20 left 30 25 20 left 2 25 45 Insert 20 on left 20 24 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 25 Example Deletion Leaf Delete 25 10 5 10 10 25 right 30 5 30 25 left 30 25 25 delete 2 25 45 2 45 26 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 27 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 28 Building Maps w Search Trees Search trees often used to implement maps Each non empty node contains Key Value Left and right child Need to be able to compare keys Generic type K extends Comparable K Denotes any type K that can be compared to K s 29 Polymorphic Binary Search Trees What do we mean by polymorphic Implement two subtypes of Tree 1 EmptyTree 2 NonEmptyTree Use EmptyTree to represent the empty tree Rather than null Invoke methods on tree nodes Without checking for null Get empty or nonempty functionality Selected by type of tree node 30 Polymorphic Binary Tree Implement Interface Tree Tree insert Value data1 Class EmptyTree implements Tree Tree insert Value data1 Class NonEmptyTree implements Tree Value data Tree left right Either Empty or NonEmpty Tree insert Value data1 31 Example Standard …
View Full Document
Unlocking...