Popular in Advanced Data Structures and Algorithm Analysis
CRS 225 - M001
verified elite notetaker
Popular in ComputerScienence
verified elite notetaker
This 29 page Study Guide was uploaded by NikkitheNotetaker on Saturday March 26, 2016. The Study Guide belongs to COSC 600 at Towson University taught by Dr. Yanggon Kim in Spring 2016. Since its upload, it has received 14 views. For similar materials see Advanced Data Structures and Algorithm Analysis in ComputerScienence at Towson University.
Reviews for Study Guide
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 03/26/16
Chapter 4 Trees Trees are special subset of graphs. A tree is a collection of nodes. It consists of a) a distinguished node called root b) zero or more non empty subtrees T , T1……2. T , eack of these nodes connected by a directed edge from “r” c)recursive definition root T1 Tk T2 Tree is a directed graph without a cycle 1. each node of a tree has only one parent node except root 2 there is only one “path” from root to each node, no cycle Path: a sequence of nodes n1, n2….. nk such that ni is the parent of ni+1 Length of path: number of edges Depth of ni: length of the path from root to ni Height of ni: length of longest path from ni to leaf node Leaf node: which has no child also called as terminal node Linked list representation of a tree value Links to children nodes A D B C G E F value Next sibling Child = root of first sub tree Implementation: using linked lists A B C D D / / F / / E F E / A / B C / / Tree Search (tree traverse) 1) Depth first search(DFS)……………… use stacks 2)Breadth first search(BFS) …………… Use Queues Binary tree: special subset of tree, ordered tree Statement: each son of a vertex is distinguished either as a left son or as right son 2) no vertex has more than one left son nor more than one right son a tree in which no node can have more than two children Implementation: Linked list pointing to a left n right nodes Eg: A / BC / left value right / E / / F / Note: For a number of nodes begin N, the average height of all possible binary tree N is O ( √ ). Let F be the # number of nodes with 2 children and H be the # no of nodes with 1 child and L be the # no of nodes with no children then 1) F+H+L = N 2) 2F+H=N-1 from 1 &2, F=L-1 Traversal method for a binary tree 1) pre order: visit + traversal of left subtree + traversal of right subtree 2)In order: traversal of left subtree + visit + traversal of right subtree 3)post order: traversal of left subtree + traversal of right subtree + visit visit: print label of nodes A B C D G K H L F M E I Preorder for above tree: ABDGJKCEHFILM In order: DJGKBAHECLIMF Post order: JKGDBHELMIFCA Expression tree example: + * / 3 + * 4 2 4 8 2 Post order: 3 2 4 + * 8 2 * 4 / + Pre order: + * 3 + 2 4 / * 8 2 4 In order: ((3*(2+4) + ((8*2)/4)) Problem: Generate Algorithm to convert post order to in order (postfix to infix) Eg: a b + c d e + * * Algorithm: 1) read a token left to right If token = operand Create a one node tree and push it into a stack If token = operator Pop two trees T1, T2 from stack and from new tree whose root is the operator and whose left and right children are T2 and T1 First two symbols are operands push them into the stack a b Next is operator + so a, b are popped and new tree is formed and pushed into stack + a b Next c, d, e are read and they are placed in stack + a d b c e Next operator + is read so trees are merged + + a b c d e + + + + + Next operator * is read so we pop two trees and form new tree with * as root + * + + a b c + + + d e + + Finally, last symbol is read two trees are merged and final tree is left on the stack * + + * + a b c d + e Binary search tree: Subset of binary tree. It is a binary tree for a set ‘s’, s is a labeled binary tree such that each vertex V is labeled by an element l(v) ∈ s 1)each vertex ‘u’ in the left subtree of ‘v’ l(u) < l(v) 2)each vertex ‘u’ in the right subtree of ‘v’ l(u) > l(v) ∈ 3)each element a s, there is exactly one vertex v such that l(v)=a If left subtree < root, root < right subtree then only it is binary search tree and No two node values are same. Operations: 1)find(search) 2)insert 3)delete 4)find min/find max 5)print Find Operation • Time Complexity – O(Height of the Binary Search Tree) That is O(N) in worst case Example: Height of the tree = N Thus, Order of growth = O(N) Find (Worst Case Example) Order of growth will be O(N), no matter how the tree is structured. Find Max and Find Min For Find Max and Find Min operations, the worst case will have the time complexity order of O(N). • L is the smallest value in this BST. • I is the largest value in this BST. • For sorting in ascending order use in order (LVR) method. • For sorting in descending order use in order (RVL) method. • It will have the order of O(N). Traversal & Median Value • In order can be used to find the median value in the BST. • It will have the order of O(N). • We can use the balanced binary search tree in order to change the order O(N) to O (logN). • Traversal in a BST will have the order O(N). • Recursion can be used for traversal operation. Insertion operation Always follow the BST rules while inserting a new node in the tree. Case 1) New node will always be a terminal node. Example (2 is the new node) 5 4 7 2 Case 2) In order to find the location to insert the node in some cases when following the BST protocols. The complexity will be in the order O(N). Example (6 is the new node) 5 6 4 2 7 Time Complexity worst case – O (Height of the BST) Delete Operation: O(Height of BST) ≡ O(N) There are three possible cases: i)case one: The deleting node has no child ≡ terminal node (leaf) => just delete it! ii)case two: The deleting node has only one child => reconnect the child to its parent node. iii)case three: The deleting node has two children (two subtrees) a) Find the smallest node from its right subtree and replace the deleting node with it. Delete the replaced node. => no child or only one child. b) Find the largest node from its left subtree. Example: Build(construct) a BST for a given ‘N’ elements: 5,10,21,32,7 Repeat insert operations 5 10 7 21 32 10 21 7 32 7 21 32 5 10 5 T(N)=0+1+2+3+…+(N1) ≠ O(N) because we are looking for the worst case which = O(N ) And in average case time complexity = O (log N), (this one can the best case too). Average depth all nodes in a tree is O (log N) 5 On the assumption that all insertion sequences are “equally likely”. 7 10 21 32 Some of depth of all nodes ≡ internal path length Average case analysis: Insert operation repeatedly 5 4 3 2 1 5 4 3 2 1 2 5 1 3 4 2 1 5 3 4 2 4 1 3 5 2 1 4 3 5 Randomly generated BST N! 2 1 3 2 3 1 2 2 1 3 1 3 Binary search tree ᶿ(N ) insert/remove pairs. Theorem: The expected number of comparison ≡ depth of the node Needed to insert N random elements into an initially empty BST is: O (N log N) for N≥1 (on the average, roughly ) Balanced Binary Search Tree (AVL Tree) AVL Tree is similar to Balanced Binary Search Tree. Height of empty BST subtree is 1. For “every” node in the tree, its height of left and right subtrees can differ by at most 1. This is the similar to the condition of Balance. Example: 5 8 2 1 7 4 3 It is Binary Search Tree and a AVL Tree. After Inserting 10, 5 8 2 1 7 10 4 3 It is still a AVL Tree. After Inserting 9, 5 2 8 10 1 7 4 9 3 Still, it’s a AVL Tree. Example: Below Tree is not AVL Tree. 7 8 2 10 11 1 3 4 5 NOTE: Height information is kept for each node. After each insert operation, update the height information of all the nodes from new inserted node to root node. NOTE: The minimum number of nodes in an AVL Tree of height h, s(h) is S(h)=s(h1) + s(h2) + 1 s(h1) s(h2) s (0) =1 S (1) =2 S (2) =4 S(3)=7 S(4)=12 S(5)=20 [S(3)+S(4)+1] S(6)=33 [S(4)+S(5)+1] S(7)=54 [S(5)+S(6)+1] All the tree operations =O (log N) Except insertion needs special work called “Rotations”. Example: Inserting ‘6’ 5 5 2 AfIII 8 2 8 Insert 6 ___ ____=== 4 1 7 1 4 7 3 3 6 Height of each node =max of left or right subtree +1 5 2 7 1 3 4 6 8 NOTE: After one insert operation, only nodes that are on the path from the insertion point to the root might have their balance altered. =>Insert the node to root and update the balancing information. Node that must be “Rebalanced” Violating the balancing condition of AVL tree is .(Alpha) CASE 1 An insertion into the left subtree of the left child of CASE 2 An insertion into the right subtree of the left child of CASE 3 An insertion into the left subtree of the right child of CASE 4 An insertion into the right subtree of the right child of CASE 1 is similar to CASE 4 and CASE 2 is similar to CASE 3 CASE 1 INSER CASE 2 CASE 3 CASE 4 NOTE:(SINGLE ROTATION) The new height of the entire subtree is exactly the same. EXAMPLE 20 0 12 30 6 16 24 40 4 10 42 14 35 27 5 2 37 3 Node 6 violates AVL condition lecondition. AVL Tree after Rotation 20 30 12 2 40 24 4 16 6 14 35 42 2 27 5 10 37 3 CASE 1 SINGLE ROTATION K2 K2 K1 K1 Z X Y Z X Y CASE 2 DOUBLE K1 ROTATION K2 K3 K3 K1 K2 A B C D A B C D CASE 3 DOUBLE ROTATION K3 K1 K3 K3 K2 A A B C D B C D K3 CASE 4 SINGLE ROTATION K2 K1 K2 K1 X Z Y Z X Y EXAMPLE I) TO INSERT 5 12 8 16 4 10 14 2 5 6 2) SINGLE ROTATION 3) SINGLE ROTATION 12 12 16 8 SPLAY TREES 6 16 6 10 14 * It is a Binary Search Tree 8ut not a Balanced BST. 4 14 * Relatively simple. 4 10 * Guarantees that any M consecutive tree operations. * Starting from an empty tree take at most O(M log N) * != O(log N) for a single operat2on. 5 * O (log N) “amortized” (on the average) cost per operation. 3 5 IDEA After a node is accessed, it is pushed to the root by a series of AVL rotations. WHY? i) Likely to be accessed again in the future. =>Locality. ii) Not require the maintenance of height/balance information. METHOD 1 A Series of single rotations, bottom up. K5 K5 K4 K4 F K3 K3 E A B D C E F A B C D K2 K1 K2K1 K5 K5 K1 K4 K2 K4 F K1 F E K2 K3 K3 E A B C D A B C D K1 A B C D K5 E F K2 K3 K4 7 EXAMPLE 1,2,3,4,5,6,7 6 5 1 2 4 2 1 3 3 2 1 PROBLEM Another node might be almost as deep(M, N) used to be METHOD 2 Let X be a (nonroot) node on the access path at which we are rotating. RULE If the parent of X is the root of the tree, => Merely rotate X and root similar to last rotation. Otherwise, X has both a parent(p) and a grandparent(G). CASE 1 ZIG ZIG CASE (X is a right child and P is a left child or vice versa) Double Rotation. X G D D G P X A B C D A B C CASE 2 ZIGZIG CASE (X and P are both left children or right children) G X P P X G D A B C D A B C DELETE OPERATION 1) Accessing the node to be deleted. => push the node to root. T andT L R 2) Delete it(root)=> two subtrees . TL TL 3) Find largest element .=>it will be a root without right ch.ld of TR 4) will be the right subtree of the root. EXAMPLE To delete 12 16 16 12 25 25 31 6 6 14 20 24 12 20 31 2 2 8 22 29 4 8 14 22 10 4 10 2 4 6 8 12 120162 2529 31 After 12 10 6 16 2 8 14 25 20 31 4 22 After deleting 12, element 10 should be root. 29 B-Tree Main reason why it’s needed? o Reduces the disk access time M-ary Search trees o M-way branches: M M value increases == height decreases o M – (minus) 1 keys o Maintain M-ary search tree is balanced Properties of B- Tree (M and L) M = no. (#) of branches L = Record in each terminal/ block of data 1. Data items are stored at leaves 2. Non leaf nodes store up (m – 1) keys a. Key (i) represent the smallest key in subtree (i+1) 3. Root is either a leaf or has between two and more children 4. All non-leaf nodes (except root) have between [m/2] and m children 5. All leaves are at the same depth and have between [L/2] and L children for some L EXAMPLE 1 Assume one block = 8192 byte ==8k. And each key == 32 bytes. Link= 4 bytes Using M-ary B-tree formula M-1 = keys M= links 32(M-1) + 4 * M <= 8192 M= (up to) 228 L=? 8192/ (divide by) record size in this case the record size= 256 bytes So, = 8192/ (256) = 32 record/leaf. EXAMPLE 2 Suppose 10 million records Each leaf has between 16 and 32 records Each internal node (with the exception of the root) has at least 114 branches o 10,000,000/16 =(about) 625, 000 leaves ( worst case) To calculate worst case depth of B-tree o Use log functions log114 10,000,000 o The actual data is stored in leaf node o Time complexity is measured by B-tree (height)
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'