CMSC 132: Object-Oriented Programming IITrees & Binary Search TreesDepartment of Computer ScienceUniversity of Maryland, College ParkTreesTrees 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 nodesTreesTerminologyRoot ⇒⇒⇒⇒node with no parentLeaf ⇒⇒⇒⇒all nodes with no childrenInterior ⇒⇒⇒⇒all nodes with childrenRoot nodeLeaf nodesInterior nodesTreesTerminologySibling ⇒⇒⇒⇒node with same parentDescendent ⇒⇒⇒⇒children nodes & their descendentsSubtree⇒⇒⇒⇒portion of tree that is a tree by itself⇒⇒⇒⇒a node and its descendentsSubtreeSiblingsTreesTerminologyLevel ⇒⇒⇒⇒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 = 3Binary TreesBinary treeTree with 0–2 children per nodeLeft & right child / subtreeBinary TreeLeft ChildParentRight ChildTree 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 traversalTree TraversalGoalVisit every node in binary treeApproachesDepth firstPreorder⇒⇒⇒⇒parent before childrenInorder⇒⇒⇒⇒left child, parent, right childPostorder⇒⇒⇒⇒children before parentBreadth first ⇒⇒⇒⇒closer nodes firstTree 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 // lastTree 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} }Tree 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 treeTree 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, 62Types of Binary TreesDegenerateMostly 1 child / nodeHeight = O(n) Similar to linear listBalancedMostly 2 child / nodeHeight = O( log(n) )Useful 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 ) { … }…}Iterative 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 );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 subtreeOR 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 largestvalue in left subtreeReplacing 5 with largestvalue in left subtreeDeleting leafExample Deletion (Internal Node)Delete ( 10 )510302 25 45525302 25 45525302 45Replacing 10 with smallestvalue in right subtreeDeleting leaf Resulting treeBuilding 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’sPolymorphic 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 nodePolymorphic 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 ) { … }}Example : Standard
View Full Document
Unlocking...