CompSci 100E18.1Binary Treesÿ Linked lists: efficient insertion/deletion, inefficient search ArrayList: search can be efficient, insertion/deletion notÿ Binary trees: efficient insertion, deletion, and search trees used in many contexts, not just for searching, e.g., expression trees search in O(log n) time like sorted array insertion/deletion O(1) like list, once location found! binary trees are inherently recursive, difficult to process trees non-recursively, but possible o recursion never required, often makes coding simplerCompSci 100E18.2From doubly-linked lists to binary treesÿ Instead of using previous and next to point to a linear arrangement, use them to divide the universe in half Similar to binary search, everything less goes left, everything greater goes right How do we search? How do we insert?“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”“pig”“hippo”“leopard”“koala”“koala”“koala”“koala”“koala”CompSci 100E18.3Basic tree definitionsÿ Binary tree is a structure: empty root node with left and right subtreesÿ terminology: parent, children, leaf node, internal node, depth, height, patho link from node N to M then N is parent of M M is child of No leaf node has no children internal node has 1 or 2 childreno path is sequence of nodes, N1, N2, … Nk Niis parent of Ni+1 sometimes edge instead of nodeo depth (level) of node: length of root-to-node path level of root is 1 (measured in nodes)o height of node: length of longest node-to-leaf path height of tree is height of rootABEDFCGCompSci 100E18.4Printing a search treein orderÿ When 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 100E18.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 iteratively How 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 cases For trees? For vectors? For linked lists? For arrays of linked-lists?CompSci 100E18.6Implementing Binary Treesÿ Trees can have many shapes: short/bushy, long/stringy if height is h, number of nodes is between hand 2h-1 single node tree: height = 1, if height = 3 Java 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 100E18.7Tree functionsÿ Compute 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 100E18.8Tree traversalsÿ Different traversals useful in different contexts Inorder prints search tree in ordero Visit left-subtree, process root, visit right-subtree Preorder useful for reading/writing treeso Process root, visit left-subtree, visit right-subtree Postorder useful for destroying treeso Visit left-subtree, visit right-subtree, process root“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”CompSci 100E18.9Insertion into search treeÿ Simple recursive insertion into treet = insert("foo", t);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 tree Why is this important? Why must the idiom t = treeMethod(t,…) be used?CompSci 100E18.10Balanced Trees and Complexityÿ A tree is height-balanced if Left and right subtrees are height-balanced Left and right heights differ by at most oneboolean isBalanced(Tree root){if (root == null) return true;else {returnisBalanced(root.left) &&isBalanced(root.right) &&Math.abs(height(root.left) – height(root.right)) <= 1;}}CompSci 100E18.11What is complexity?ÿ Assume trees are “balanced” in analyzing complexity Roughly half the nodes in each subtree Leads to easier analysisÿ How to develop recurrence relation? What is T(n)? What other work is done?ÿ How to solve recurrence relation Plug, expand, plug, expand, find pattern A real proof requires induction to verify correctnessCompSci 100E18.12Danny Hillisÿ The third culture consists of those scientistsand other thinkers in the empirical world who,through their work and expository writing, aretaking the place of the traditional intellectualin rendering visible the deeper meanings ofour lives, redefining who and what we are.(Wired 1998) And now we are beginning to dependon computers to help us evolve new computersthat let us produce things of much greatercomplexity. Yet we don't quite understand theprocess - it's getting ahead of us. We're nowusing programs to make much faster computersso the process can run much faster.That's what's so confusing - technologies are feeding back onthemselves; we're taking off. We're at that point analogous to whensingle-celled organisms were turning into multicelled organisms.We are amoebas and we can't figure out what the hell this thing isthat we're
View Full Document
Unlocking...