DOC PREVIEW
Duke CPS 100E - Lecture

This preview shows page 1-2 out of 6 pages.

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

Unformatted text preview:

CompSci 100e9.1From doubly-linked lists to binary trees! Instead of using prev and next to point to a lineararrangement, 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 100e9.2Basic tree definitions! Binary tree is a structure:! empty! root node with left and right subtrees! terminology: 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 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 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 order! When 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 traversals! Different traversals useful in different contexts! Inorder prints search tree in order• Visit left-subtree, process root, visit right-subtree! Preorder useful for reading/writing trees• Process root, visit left-subtree, visit right-subtree! Postorder useful for destroying trees• Visit left-subtree, visit right-subtree, process root“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”CompSci 100e9.6Tree exercises1. Build a tree" People standing up are nodes that are currently in thetree" Point at a sitting down person to make them your child" Is it a binary tree? Is it a BST?" Traversals, height, deepest leaf?2. How many different binary search trees are there withspecified elements?" E.g given elements {90,13,2,3}, how many possiblelegal 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 toprinting 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 oflinked-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 iseither 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?! What would removal look like?CompSci 100e9.9Tree 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, doescomplexity change?! What about computing number of leaf nodes?CompSci 100e9.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; return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) – height(root.right)) <= 1; } }CompSci 100e9.11Rotations and balanced trees! Height-balanced trees! For every node, left andright subtree heights differby at most 1! After insertion/deletionneed to rebalance! Every operation leaves treein a balanced state: invariantproperty of tree! Find deepest node that’sunbalanced then make sure:! On path from root toinserted/deleted node! Rebalance at thisunbalanced point onlyAre these trees height-balanced?CompSci 100e9.12What 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 100e9.13Balanced trees we won't study! B-trees are used when data is both in memory and on disk! File systems, really large data sets! Rebalancing guarantees good performance bothasymptotically and in practice. Differences betweencache, memory, disk are important! Splay trees rebalance during insertion and during search,nodes accessed often more closer to root! Other nodes can move further from root, consequences?• Performance for some nodes gets better, for others …! No guarantee running time for a single operation, butguaranteed good performance for a sequence ofoperations, this is good amortized cost (vectorpush_back)CompSci 100e9.14Balanced trees we will study! Both kinds have worst-case O(log n) time for tree operations! AVL (Adel’son-Velskii and Landis), 1962! Nodes are “height-balanced”, subtree heights differ by 1! Rebalancing requires per-node bookkeeping of height! http://www.seanet.com/users/arsen/avltree.html! Red-black tree uses same rotations, but can rebalance in onepass, contrast to AVL


View Full Document

Duke CPS 100E - Lecture

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

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 Lecture
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 Lecture 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 Lecture 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?