CMSC 132: Object-Oriented Programming IITrees & Binary Search TreesDepartment of Computer ScienceUniversity of Maryland, College Park1TreesTrees are hierarchical data structures One-to-many relationship between elements Tree node / elementContains dataReferred to by only 1 (parent) nodeContains links to any number of (children) nodesParent nodeChildren nodes2TreesTerminologyRoot node with no parentLeaf all nodes with no childrenInterior all nodes with childrenRoot nodeLeaf nodesInterior nodes3TreesTerminologySibling node with same parentDescendent children nodes & their descendentsSubtree portion of tree that is a tree by itself a node and its descendentsSubtreeSiblings4TreesTerminologyLevel is a measure of a node’s distance from rootDefinition of levelIf node is the root of the tree, its level is 1Else, the node’s level is 1 + its parent’s levelHeight (depth) max level of any node in treeHeight = 35Binary TreesBinary treeTree with 0–2 children per nodeLeft & right child / subtreeBinary TreeLeft ChildParentRight Child6Tree TraversalOften we want to 1. Find all nodes in tree 2. Determine their relationshipCan do this by1. Walking through the tree in a prescribed order 2. Visiting the nodes as they are encounteredProcess is called tree traversal7Tree TraversalGoalVisit every node in binary treeApproachesDepth firstPreorder parent before childrenInorder left child, parent, right childPostorder children before parentBreadth first closer nodes first8Tree Traversal MethodsPre-order1. Visit node // first2. Recursively visit left subtree3. Recursively visit right subtreeIn-order1. Recursively visit left subtree2. Visit node // second3. Recursively right subtreePost-order1. Recursively visit left subtree2. Recursively visit right subtree3. Visit node // last9Tree Traversal MethodsBreadth-firstBFS(Node n) {Queue Q = new Queue();Q.enqueue(n); // insert node into Q while ( !Q.empty()) {n = Q.dequeue(); // remove next nodeif ( !n.isEmpty()) {visit(n); // visit nodeQ.enqueue(n.Left()); // insert left subtree in QQ.enqueue(n.Right());// insert right subtree in Q} }10Tree Traversal ExamplesPre-order (prefix)+ 2 3 / 8 4In-order (infix)2 3 + 8 / 4Post-order (postfix)2 3 8 4 / +Breadth-first+ / 2 3 8 4+/2 3 8 4Expression tree11Tree Traversal ExamplesPre-order44, 17, 32, 78, 50, 48, 62, 88In-order17, 32, 44, 48, 50, 62, 78, 8888441778325048 62Binary search treeSorted order!Post-order32, 17, 48, 62, 50, 88, 78, 44Breadth-first44, 17, 78, 32, 50, 88, 48, 6212Types of Binary TreesDegenerateMostly 1 child / nodeHeight = O(n) Similar to linear listBalancedMostly 2 child / nodeHeight = O( log(n) )Useful for searchesDegenerate binary treeBalanced binary tree13Binary Search TreesKey propertyValue at nodeSmaller values in left subtreeLarger values in right subtreeExampleX > YX < ZYXZ14Binary Search TreesExamplesBinary search treesNon-binary search tree510302 25 45510452 25 30510302254515Binary Tree ImplementationClass Node {Value data; Node left, right; // null if empty void insert ( Value data1 ) { … }void delete ( Value data2 ) { … }Node find ( Value data3 ) { … }…}16Iterative Search of Binary TreeNode Find( Node n, Value key) { while (n != null) {if (n.data == key) // Found itreturn n;if (n.data > key) // In left subtreen = n.left;else // In right subtreen = n.right;} return null;}Find( root, keyValue );17Recursive 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 );18Example Binary SearchesFind ( 2 )510302 25 45510302254510 > 2, left5 > 2, left2 = 2, found5 > 2, left2 = 2, found19Example Binary SearchesFind ( 25 )510302 25 45510302254510 < 25, right30 > 25, left25 = 25, found5 < 25, right45 > 25, left30 > 25, left10 < 25, right25 = 25, found20Binary Search PropertiesTime of searchProportional to height of treeBalanced binary treeO( log(n) ) timeDegenerate treeO( n ) timeLike searching linked list / unsorted arrayRequiresAbility to compare key values21Binary Search Tree ConstructionHow to build & maintain binary trees?InsertionDeletionMaintain key property (invariant)Smaller values in left subtreeLarger values in right subtree22Binary 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 tree23Example InsertionInsert ( 20 )510302 25 4510 < 20, right30 > 20, left25 > 20, leftInsert 20 on left2024Binary 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 subtreeOR smallest value Z on right subtreeb) Delete replacement value (Y or Z) from subtreeObservationO( log(n) ) operation for balanced treeDeletions may unbalance tree25Example Deletion (Leaf)Delete ( 25 )510302 25 4510 < 25, right30 > 25, left25 = 25, delete510302 4526Example Deletion (Internal Node)Delete ( 10 )510302 25 4555302 25 4525302 25 45Replacing 10 with largestvalue in left subtreeReplacing 5 with largestvalue in left subtreeDeleting leaf27Example Deletion (Internal Node)Delete ( 10 )510302 25 45525302 25 45525302 45Replacing 10 with smallestvalue in right subtreeDeleting leaf Resulting tree28Building Maps w/ Search TreesSearch trees often used to implement mapsEach non-empty node containsKeyValueLeft and right childNeed to be able to compare keysGeneric type <K extends Comparable<K>>Denotes any type K that can be compared to K’s29Polymorphic Binary Search TreesWhat do we mean by polymorphic?Implement two subtypes of Tree1. EmptyTree2. NonEmptyTreeUse EmptyTree to represent the empty treeRather than nullInvoke methods on tree nodesWithout checking for nullGet empty or nonempty functionalitySelected by type of tree node30Polymorphic 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 NonEmptyTree insert ( Value data1 ) { … }}31Example : Standard Binary TreeClass Node {Node left, right;}Node X
View Full Document
Unlocking...