DOC PREVIEW
Duke CPS 100E - Binary Trees

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 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 orecursion never required, often makes coding simplerCompSci 100E20.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 100E20.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, patholink from node N to M then N is parent of MM is child of Noleaf node has no childreninternal node has 1 or 2 childrenopath is sequence of nodes, N1, N2, … NkNi is parent of Ni+1sometimes edge instead of nodeodepth (level) of node: length of root-to-node pathlevel of root is 1 (measured in nodes)oheight of node: length of longest node-to-leaf pathheight of tree is height of rootABEDFCGCompSci 100E20.4Printing a search tree in 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 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 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 100E20.6Implementing Binary TreesTrees can have many shapes: short/bushy, long/stringyif height is h, number of nodes is between h and 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 100E20.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 100E20.8Tree traversalsDifferent traversals useful in different contextsInorder prints search tree in orderoVisit left-subtree, process root, visit right-subtreePreorder useful for reading/writing treesoProcess root, visit left-subtree, visit right-subtreePostorder useful for destroying treesoVisit left-subtree, visit right-subtree, process root“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”CompSci 100E20.9Insertion into search treeSimple 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 treeWhy is this important?Why must the idiom t = treeMethod(t,…) be used?CompSci 100E20.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 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 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 100E20.12Danny HillisThe 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

Duke CPS 100E - Binary Trees

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Binary 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 Binary 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 Binary 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?