Search TreesOverviewTree BasicsImplementationTraversalsSlide 6Binary TreesBinary Search TreesAVL TreesSingle RotationDouble RotationRed Black TreesProblemsOther TypesApplicationsSummaryReferencesQuestionsSearch TreesDouglas HowellJanuary 29, 2008COT 4810Overview•Basics•Traversals•Implementation•Binary Search Trees•AVL Trees•Red Black Trees•Other Trees•ApplicationsTree Basics•Root node: first node in tree•Parent-Child relationships•Leaf node: node with no child•Height: length from node to deepest leaf •Depth: length from root to nodeImplementation•Linked lists•Fields:–Data–Pointer to child nodes•Alternate method–First child / next siblingTraversals•Pre-order: Root, Left, Right•In-order: Left, Root, Right•Post-order: Left, Right, Root•Level-order: Top down, left to right•Pre-Order: 1 2 4 5 3 6 7•In-Order: 4 2 5 1 6 3 7•Post-Order: 4 5 2 6 7 3 1•Level-Order: 1 2 3 4 5 6 712 34 5 6 7TraversalsBinary Trees•No more than 2 child nodes•Useful:–Compiler expressions–Huffman Coding–Binary Search TreesBinary Search Trees•All nodes in the left sub-tree must have a value less than the root node•All nodes in the right sub-tree must have a value greater than the root node•Faster searching, worst depth still O(n)AVL Trees•Height of left and right subtrees cannot differ by more than 1•Depth close to logN•Inserting / Removing balance issuesSingle Rotation41 62 5 73=>42 63 5 71Double Rotation52 634=>32 54 611Red Black Trees•Nodes must be red or black•Root must be black•Red nodes must have black children•Each path must have equal black nodes42 63 5 71•Serious balancing issues!•Single / Double rotations•Color changesProblemsOther Types•aa-trees: red-black tree, left children cannot be red•b-trees: data stored in leaf nodes, parents guide the search•Splay trees: accessed nodes become root•Ternary search trees: three way trees•2-3-4 trees: nodes have 2, 3, or 4 children and have 1,2, or 3 elements in that nodeApplications•O.S. file storage•Searching algorithms•Text processing•Compiler design•Overall: structures that are fast at looking up and inserting data, log N time averageSummary•Basics: root, parent-child, leaf nodes•Implementation: linked lists, arrays•Traversals: pre, in, post, level-order•Binary Search Trees•AVL Trees: single, double rotations•Red-Black Trees and others•Very useful in computer science!References•Weiss, Mark A. Data Structures & Problem Solving Using Java, 3rd Ed. Pearson, 2006.•Dewdney, A. K. The New Turing Omnibus, Henry Holt and Company, New York, 1989.•www.wikipedia.com, 2008.Questions•1) Name 3 types of search trees.•2) Give the pre, in, post, and level order traversals of this tree.94 83 725
View Full Document
Unlocking...