DOC PREVIEW
USF CS 112 - Trees

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

USF CS 112 - Trees

Documents in this Course
Structs

Structs

4 pages

Trees

Trees

25 pages

Strings

Strings

27 pages

Queues

Queues

3 pages

Trees

Trees

24 pages

Arrays

Arrays

5 pages

ArrayList

ArrayList

24 pages

Stacks

Stacks

2 pages

Stacks

Stacks

8 pages

Stacks

Stacks

8 pages

Queues

Queues

16 pages

Queues

Queues

17 pages

Queues

Queues

17 pages

Load more
Download Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?