Binary TreesFrom doubly-linked lists to binary treesBasic tree definitionsPrinting a search tree in orderInsertion and Find? Complexity?Implementing Binary TreesTree functionsTree traversalsInsertion into search treeBalanced Trees and ComplexityWhat is complexity?Danny HillisCompSci 100E20.1Binary TreesLinked lists: efficient insertion/deletion, inefficient searchArrayList: search can be efficient, insertion/deletion notBinary trees: efficient insertion, deletion, and searchtrees used in many contexts, not just for searching, e.g., expression treessearch in O(log n) time like sorted arrayinsertion/deletion O(1) like list, once location found!binary trees are inherently recursive, difficult to process trees non-recursively, but possible orecursion never required, often makes coding simplerCompSci 100E20.2From doubly-linked lists to binary treesInstead of using previous 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 100E20.3Basic tree definitionsBinary tree is a structure:emptyroot node with left and right subtreesTerminology: parent, children, leaf node, internal node, depth, height, patholink from node N to M then N is parent of MM is child of Noleaf node has no childreninternal node has 1 or 2 childrenopath is sequence of nodes, N1, N2, … NkNi is parent of Ni+1sometimes edge instead of nodeodepth (level) of node: length of root-to-node pathlevel of root is 1 (measured in nodes)oheight of node: length of longest node-to-leaf pathheight of tree is height of rootABEDFCGCompSci 100E20.4Printing a search tree in orderWhen is root printed?After left subtree, before right subtree. void visit(Node 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 100E20.5Insertion 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 100E20.6Implementing 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 Tree{ String info; Tree left; Tree right; Tree(String s, Tree lptr, Tree rptr){ info = s; left = lptr; right = rptr; }}CompSci 100E20.7Tree 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 100E20.8Tree traversalsDifferent traversals useful in different contextsInorder prints search tree in orderoVisit left-subtree, process root, visit right-subtreePreorder useful for reading/writing treesoProcess root, visit left-subtree, visit right-subtreePostorder useful for destroying treesoVisit left-subtree, visit right-subtree, process root“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”CompSci 100E20.9Insertion into search treeSimple recursive insertion into tree t = insert(t, "foo"); Tree insert(Tree 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?CompSci 100E20.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; else { return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) – height(root.right)) <= 1; } }CompSci 100E20.11What 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 100E20.12Danny HillisThe third culture consists of those scientists and other thinkers in the empirical world who, through their work and expository writing, are taking the place of the traditional intellectual in rendering visible the deeper meanings of our lives, redefining who and what we are. (Wired 1998) And now we are beginning to depend on computers to help us evolve new computers that let us produce things of much greater complexity. Yet we don't quite understand the process - it's getting ahead of us. We're now using programs to make much faster computers so the process can run much faster. That's what's so confusing - technologies are feeding back on themselves; we're taking off. We're at that point analogous to when single-celled organisms were turning into multicelled organisms. We are amoebas and we can't figure out what the hell this thing is that we're
View Full Document