Trees•Faster than linear data structures•More natural fit for some kinds of data•Examples?Why a tree?Example TreerootActivitiesTeaching ResearchSami’s Home PagePapers PresentationsCS211CS101Terminology•Root•Parent •Child•Sibling•External node•Internal node•Subtree•Ancestor•DescendantExample TreerootActivitiesTeaching ResearchSami’s Home PagePapers PresentationsCS211CS101Root?Parent – papers, activities Children – cs101, research Sibling - teachingExternal nodesInternal nodesSubtree – left subtree of research?Ancestor – papers ancestor of activities?Descendant – papers descendant of home?Ordered Trees•Linear relationship between child nodes•Binary tree – max two children per node –Left child, right childDavidsonTrumanRollinsTaft ZunigaRalsonBrownrootAnother Ordered Binary TreeRalsonTrumanBrownTaft ZunigaRollinsDavidsonrootTree Traversal•Pre-order traversal–Visit node, traverse left subtree, traverse right subtree•Post-order traversal–Traverse left subtree, traverse right subtree, visit nodeExample•Pre-order •Post-orderDavidsonTrumanRollinsTaft ZunigaRalsonBrownrootExample•Pre – Rollins, Davidson, Brown, Ralson, Truman, Taft, Zuniga•Post – Brown, Ralson, Davidson, Taft, Zuniga, Truman, RollinsDoTrimmerRollinsTilkidjieva YuciusReardonBenderskyrootAnother ExampleRalsonTrumanBrownTaft ZunigaRollinsDavidsonroot•Pre – Brown, Truman, Taft, Ralson, Davidson, Rollins, Zuniga•Post – Davidson, Rollins, Ralson, Taft, Zuniga, Truman, BrownIn-order Traversal•Traverse left subtree, visit node, traverse right subtree–Brown, Davidson, Ralson, Rollins, Taft, Truman, ZunigaDavidsonTrumanRollinsTaft ZunigaRalsonBrownrootAnother ExampleRalsonTrumanBrownTaft ZunigaRollinsDavidsonroot•In-order – Brown, Davidson, Ralson, Rollins, Taft, Truman, ZunigaImplementation – TreeNode•Data members?•Functions?Name = RollinsImplementation – Tree •Data Members•Functions–Pre/post/in-order printSmithRollinsrootBrownImplementation – Pre-ordervoid preOrderPrint(TreeNode* curnode) {o.print();if(curnode->getLeftChild() != NULL) preOrderPrint(curnode->getLeftChild());if(curnode->getRightChild() != NULL) preOrderPrint(curnode->getRightChild());}Tree* t = …; t->preOrderPrint(t->getRoot());BSTs•Elements in left subtree nodes are before (are less than) element in current node•Element in current node is before (less than) elements in right subtreefind Operation•Algorithm for finding element in BSTRalsonTrumanBrownTaft ZunigaRollinsDavidsonrootfind Algorithmif current node is nullreturn not foundelse if target is in current nodereturn foundelse if target is before current nodereturn find(left child)elsereturn find(right child)find Complexity•Worst case•Best case•Average caseinsert Operation•Algorithm for inserting element in BSTRalsonTrumanBrownTaft ZunigaRollinsDavidsonrootinsert Algorithmif new_elt is before current and current left child is nullinsert as left childelse if new_elt is after current and current right child is nullinsert as right childelse if new_elt is before currentinsert in left subtreeelseinsert in right subtreeremove Operation•Algorithm for removing element in BSTRalsonTrumanBrownTaft ZunigaRollinsDavidsonrootremove Algorithmelt = find node to removeif elt left subtree is nullreplace elt with right subtreeelse if elt right subtree is nullreplace with left subtreeelse find successor of elt (go right once and then left until you hit null) replace elt with successor call remove on
View Full Document