From doubly-linked lists to binary treesBasic tree definitionsImplementing binary treesPrinting a search tree in orderTree traversalsTree exercisesInsertion and Find? Complexity?What does insertion look like?Tree functionsBalanced Trees and ComplexityRotations and balanced treesWhat is complexity?Balanced trees we won't studyBalanced trees we will studyRotation to rebalanceRotation up close (doLeft)Slide 17Double rotation completeAVL tree practiceAVL practice: continued, and finishedTrie: efficient search of words/suffixesTrie picture and code (see trie.cpp)ScoreboardBoggle: Tries, backtracking, structureCompSci 100e9.1From doubly-linked lists to binary treesInstead of using prev and next to point to a linear arrangement, use them to divide the universe in halfSimilar to binary search, everything less goes left, everything greater goes rightHow do we search?How do we insert?“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”“pig”“hippo”“leopard”“koala”“koala”“koala”“koala”“koala”CompSci 100e9.2Basic tree definitionsBinary tree is a structure:emptyroot node with left and right subtreesterminology: parent, children, leaf node, internal node, depth, height, path•link from node N to M then N is parent of M–M is child of N•leaf node has no children–internal node has 1 or 2 children•path is sequence of nodes, N1, N2, … Nk–Ni is parent of Ni+1–sometimes edge instead of node•depth (level) of node: length of root-to-node path–level of root is 1 (measured in nodes)•height of node: length of longest node-to-leaf path–height of tree is height of rootABEDFCGCompSci 100e9.3Implementing binary treesTrees can have many shapes: short/bushy, long/stringyif height is h, number of nodes is between h and 2h-1single node tree: height = 1, if height = 3Java implementation, similar to doubly-linked listpublic class TreeNode{ String info; TreeNode left; TreeNode right; TreeNode(String s, TreeNode llink, TreeNode rlink){ info = s; left = llink; right = rlink; }};CompSci 100e9.4Printing a search tree in orderWhen is root printed?After left subtree, before right subtree. void visit(TreeNode t) { if (t != null) { visit(t.left); System.out.println(t.info); visit(t.right); } }Inorder traversal“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”“pig”“hippo”“leopard”CompSci 100e9.5Tree traversalsDifferent traversals useful in different contextsInorder prints search tree in order•Visit left-subtree, process root, visit right-subtreePreorder useful for reading/writing trees•Process root, visit left-subtree, visit right-subtreePostorder useful for destroying trees•Visit left-subtree, visit right-subtree, process root“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”CompSci 100e9.6Tree exercises1. Build a treePeople standing up are nodes that are currently in the treePoint at a sitting down person to make them your childIs it a binary tree? Is it a BST?Traversals, height, deepest leaf?2. How many different binary search trees are there with specified elements?E.g given elements {90,13,2 ,3}, how many possible legal BSTs are there?3. Convert a binary search tree to a doubly linked list in O(n) time without creating any new nodes.CompSci 100e9.7Insertion and Find? Complexity?How do we search for a value in a tree, starting at root?Can do this both iteratively and recursively, contrast to printing which is very difficult to do iterativelyHow is insertion similar to search?What is complexity of print? Of insertion?Is there a worst case for trees?Do we use best case? Worst case? Average case?How do we define worst and average casesFor trees? For vectors? For linked lists? For arrays of linked-lists?CompSci 100e9.8What does insertion look like?Simple recursive insertion into tree (accessed by root)root = insert("foo", root); public TreeNode insert(TreeNode t, String s) { if (t == null) t = new Tree(s,null,null); else if (s.compareTo(t.info) <= 0) t.left = insert(t.left,s); else t.right = insert(t.right,s); return t; }Note: in each recursive call, the parameter t in the called clone is either the left or right pointer of some node in the original treeWhy is this important?Why must the idiom t = treeMethod(t,…) be used? What would removal look like?CompSci 100e9.9Tree functionsCompute height of a tree, what is complexity? int height(Tree root) { if (root == null) return 0; else { return 1 + Math.max(height(root.left), height(root.right) ); } }Modify function to compute number of nodes in a tree, does complexity change?What about computing number of leaf nodes?CompSci 100e9.10Balanced Trees and ComplexityA tree is height-balanced ifLeft and right subtrees are height-balancedLeft and right heights differ by at most one boolean isBalanced(Tree root) { if (root == null) return true; return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) – height(root.right)) <= 1; } }CompSci 100e9.11Rotations and balanced treesHeight-balanced treesFor every node, left and right subtree heights differ by at most 1After insertion/deletion need to rebalanceEvery operation leaves tree in a balanced state: invariant property of treeFind deepest node that’s unbalanced then make sure:On path from root to inserted/deleted nodeRebalance at this unbalanced point onlyAre these trees height-balanced?CompSci 100e9.12What is complexity?Assume trees are “balanced” in analyzing complexityRoughly half the nodes in each subtreeLeads to easier analysisHow to develop recurrence relation?What is T(n)?What other work is done?How to solve recurrence relationPlug, expand, plug, expand, find patternA real proof requires induction to verify correctnessCompSci 100e9.13Balanced trees we won't studyB-trees are used when data is both in memory and on diskFile systems, really large data setsRebalancing guarantees good performance both asymptotically and in practice. Differences between cache, memory, disk are importantSplay trees rebalance during insertion and during search, nodes accessed often more closer to rootOther nodes
View Full Document
Unlocking...