Trees-SNM.pptx

Trees [email protected] Outline Tree – concept General tree Types of trees Binary tree: representation, operation Binary tree traversal Binary search tree BST- The data structure and implementation Threaded binary trees. Search Trees – – AVL tree, Multiway Search Tree, B Tree, B+ Tree, and Trie, Applications/Case study of trees. Summary Queries? Tree linear data structures – strings, arrays, lists, stacks and queues Non-linear data structure - tree. Mainly used to represent data containing a hierarchical relationship between elements, for example, records, family trees and table of contents. – E.g. a parent-child relationship A family tree A Tree Types of trees General tree Binary tree Binary search tree Threaded binary tree AVL Tree B tree B+ Tree Trie Heap Red black tree Splay tree Binary Tree Binary search Tree Red Black AVL Tree Tree Splay Tree Trie Heap (MinHeap) B Tree B+ Tree Tree Data structure A tree is an abstract model of a hierarchical structure that consists of nodes with a parent-child relationship. Tree is a sequence of nodes There is a starting node known as a root node Every node other than the root has a parent node. Nodes may have any number of children 10 11 1. Root The first node from where the tree originates is called as a root node. In any tree, there must be only one root node. We can never have multiple root nodes in a tree data structure. 12 2. Edge The connecting link between any two nodes is called as an edge. In a tree with n number of nodes, there are exactly (n- 1) number of edges. 3. Parent The node which has a branch from it to any other node is called as a parent node. In other words, the node which has one or more children is called as a parent node. In a tree, a parent node can have any number of child nodes. 4. Child The node which is a descendant of some node is called as a child node. All the nodes except root node are child nodes. 5. Siblings Nodes which belong to the same parent are called as siblings. In other words, nodes with the same parent are sibling nodes. 7. Internal Node The node which has at least one child is called as an internal node. Internal nodes are also called as non- terminal nodes. Every non-leaf node is an internal node. 8. Leaf Node The node which does not have any child is called as a leaf node. Leaf nodes are also called as external nodes or terminal nodes. 9. Level In a tree, each step from top to bottom is called as level of a tree. The level count starts with 0 and increments by 1 at each level or step. 10. Height Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node. Height of a tree is the height of root node. Height of all leaf nodes = 0 Computed from bottom to top 11. Depth Total number of edges from root node to a particular node is called as depth of that node. Depth of a tree is the total number of edges from root node to a leaf node in the longest path. Depth of the root node = 0 The terms “level” and “depth” are used interchangeably. Computed from top to bottom 12. Subtree In a tree, each child from a node forms a subtree recursively. Every child node forms a subtree on its parent node. 13. Forest A forest is a set of disjoint trees. 14. Path The sequence of consecutive edges from source node to destination node. 15. Keys Key represents a value of a node based on which a search operation is to be carried out for a node. Characteristics of trees Non-linear data structure Combines advantages of an ordered array and linked list Searching as fast as in ordered array Insertion and deletion as fast as in linked list Simple and fast Application Directory structure of a file storage Structure of an arithmetic expressions Used in almost every 3D video game to determine what objects need to be rendered. Used in almost every high-bandwidth router for storing router-tables. used in compression algorithms, such as those used by the.jpeg and.mp3 file formats Game trees Directory structure of a file storage Image courtesy: https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/image s/Chapter11/11_10_TwoLevelStructure.jpg Structure of an arithmetic expressions ge courtesy: https://media.geeksforgeeks.org/wp-content/uploads/expression-tre Object rendering in 3-D game Image Courtesy: https://www.bogotobogo.com/Games/images/BVH.png DNS Server entries Image Courtesy: https://res.cloudinary.com/practicaldev/image/fetch/s--b9G6DenD--/ c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https:// Compression Algorithm https://brilliant-staff-media.s3-us-west- 2.amazonaws.com/tiffany-wang/VEIWKBhSSc.png Game Tree Image Courtesy: https://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alpha Binary Trees A binary tree, T, is either empty or such that 1. T has a special node called the root node 2. T has two sets of nodes LT and RT , called the left subtree and right subtree of T, respectively. 3. LT and RT are binary trees. Binary Tree A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub- trees of the original tree. A left or right sub-tree can be empty. Each element of a binary tree is called a node of the tree Binary Tree Properties If a binary tree contains m nodes at level L, it contains at most 2m nodes at level L+1 Since a binary tree can contain at most 1 node at level 0 (the root), it contains at most 2L nodes at level L. A B E C F G D K H L M I J Samples of Trees Complete Binary Tree A A 1 A B B 2 B C C Skewed Binary Tree 3 D E F G D 4 H I E 5 CHAPTER 5 41 Types of Binary Tree Complete binary tree Strictly binary tree Almost complete binary tree A complete binary tree Binary tree types Strictly binary trees are binary trees where every node either has two children or is a leaf (has no children). Complete binary trees are strictly binary trees where every leaf is on the same "maximum" level. Almost complete binary trees are not necessarily strictly binary (although they can be), and are not complete. Full BT VS Complete BT A full binary tree of depth k is a binary k tree of depth k having 2 -1 nodes, k>=0. A binary tree with n nodes and depth k complete iff its nodes correspond to th nodes numbered from 1 to n in the full A A binary tree of depth B k. C B C D E F G D E F G H I J K L M N O H I Complete binary tree CHAPTER 5 Full binary tree of depth 45 4 Sequential A Representation B C (1) waste space (2) insertion/deletion D A A E problem B F -- B G C A H -- C I -- -- B C D D --.. D E F G E E H CHAPTER 5 I 46 Linked Representation typedef struct node *tree_pointer; typedef struct node { int data; tree_pointer left_child, right_child; }; data left_child data right_child left_child right_child CHAPTER 5 47 Array representaion of tree Binary tree traversal Traversal: visiting each node only once Traversal methods: Inorder : Left-Root-Right Preorder : Root-Left-Right Postorder : Left-Right-Root Binary Tree Traversals Let L, V, and R stand for moving left, visiting the node, and moving right. There are six possible combinations of traversal – LVR, LRV, VLR, VRL, RVL, RLV Adopt convention that we traverse left before right, only 3 traversals CHAPTER 5 remain 50 Binary Tree Traversals CHAPTER 5 51 Binary Tree Traversals Inorder - 10,20, 30 Preorder - 10,20,30 Postorder - 30, 20, 10 CHAPTER 5 52 Binary Tree Traversals 53 Binary Tree Traversals Preorder- 50, 34, 12,5, 23, 20,77, 56,98 79,120, 100, Postorder- 5, 20, 23, 12, 34, 56, 79, 100, 120, 98, 77, 50 Inorder- 5, 12, 20, 23, 34, 50, 56, 77,79, 98, 100, 120 54 Binary tree Traversal Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 Postorder: 1-6-5-17-21-19-10 Binary tree Traversal Inorder: ? Preorder: ? Postorder: ? Arithmetic Expression Using BT + inorder traversal A/B*C*D+E infix expression * E preorder traversal +**/ABCDE * D prefix expression postorder traversal AB/C*D*E+ / C postfix expression level order traversal A B +*E*D/CAB CHAPTER 5 57 Inorder Traversal (recursive version) void inorder(tree_pointer ptr) { A/B*C*D+E if (ptr) { inorder(ptr->left_child); printf(“%d”, ptr->data); indorder(ptr->right_child); } } CHAPTER 5 58 Preorder Traversal (recursive version) void preorder(tree_pointer ptr) { +**/ABCDE if (ptr) { printf(“%d”, ptr->data); preorder(ptr->left_child); predorder(ptr->right_child); } } CHAPTER 5 59 Postorder Traversal (recursive version) void postorder(tree_pointer ptr) { AB/C*D*E+ if (ptr) { postorder(ptr->left_child); postdorder(ptr->right_child); printf(“%d”, ptr->data); } } CHAPTER 5 60 Construction of binary tree from traversals Can be done with two pairs of information: – Inorder & Preorder – Inorder & Postorder Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 Binary Search Tree Binary Search Tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. The left and right subtree each must also be a binary search tree. Creation of Binary Search Tree from traversals For inorder & Preorder traversal pairs: Creation of Binary Search Tree from traversals For inorder & Preorder traversal pairs: – Read the preorder input from left to right – Mark the corresponding nodes in inorder traversal to mark and left & right subtrees recursively For inorder & Postorder traversal pairs: – Read the postorder input from right to left – Mark the corresponding nodes in inorder traversal to mark and right & left subtrees recursively Creation of Binary Search Tree from traversals Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 Step 1: read preorder sequence from left to right, mark the corresponding node in inorder. The preorder sequence gives roots and subroots while inorder sequence divides them in left and right part. Creation of Binary Search Tree from traversals 10 17,19,2 1,5,6 1 Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 (mark 5 as next root) 10 17,19,2 5 1 1 6 Creation of Binary Search Tree from traversals Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 (Mark 1 as next root, but it has no unmarked elements in inorder sequence i.e. it’s a leaf node) 10 17,19,2 5 1 1 6 Creation of Binary Search Tree from traversals Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 (Mark 6 as next root, but it has no unmarked elements in inorder sequence i.e. it’s a leaf node,too) 10 17,19,2 5 1 1 6 Creation of Binary Search Tree from traversals Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 (Mark 19 as next root) 10 5 19 1 6 17 21 Creation of Binary Search Tree from traversals Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 (Mark 17 as next root, it turns out to be a leaf node) 10 5 19 1 6 17 21 Creation of Binary Search Tree from traversals Inorder: 1-5-6-10-17-19-21 Preorder: 10-5-1-6-19-17-21 (Mark 21 as next root, it turns out to be a leaf node,too) 10 5 19 1 6 17 21 Creation of Binary Search Tree from traversals Follow same process for postorder and inorder sequence, but read the postorder from right to left. Construction of Binary Search Tree Construct a BST for: 10,45,23,90,21,65,100,4,78,50 50,78,4,100,65,21,90,23,45,10 65,4,50,10,78,45,100,23,90,21 Binary Search implementation Struct tree{ int data; struct tree *left; struct tree *right; } Struct tree *t; Insertion in BST Treetype insert(TreeType *root, int key) { CreateNode(NewNode) // find the position to insert the new node Treetype *temp = root; // Pointer parent maintains the trailing pointer of temp Treetype *parent = NULL; while (temp != NULL) { parent = temp; if (key < temp->data) temp = temp->left; else temp = temp->right; } // If the root is NULL i.e the tree is empty The new node is the root node if (parent == NULL) root = newnode; // If the new key is less then the leaf node key Assign the new node to be its left child else if (key < parent->data) parent->left = newnode; // else assign the new node its right child else parent->right = newnode; return root; } Count nodes int countNodes(TreeType t) { If (t==Null) Print “tree is empty” Else if (Left(t)==Null AND Right(t)==Null) return 1 Else return(CountNodes(Left(t) +CountNodes(Right(t))+1 } Binary Search tree deletion Cases: 1. Deletion from empty tree 2. The key to be deleted doesn’t exist in tree 3. The node to be deleted is the only node in tree 4. The node to be deleted is root 5. The node to be deleted has 1. No child 2. Exactly one child 3. Two children Deletion of a node in BST //Deletion from empty tree If (root==null) { print “Error” exit } //Deletion of only node If(root->data ==key && root->left==Null && root->right==Null) { temp=root Root=null Return(temp) } Parent = null Temp =root While(temp!=null && temp->data !=key) { if (key< temp->data) parent = temp; temp=temp->left else parent = temp; temp=temp->right } If (temp==null) Print “Error, element not found” Exit Elseif (temp->left== null && temp->right==Null) //node with no children { if (temp==parent->left) parent->left= Null Else parent->right=Null } Elseif(temp->left!= null && temp->right==Null) //node with only left child { if (temp==parent->left) parent->left= temp->left Else parent->right=temp->left } Elseif(temp->left== null && temp->right!=Null) //node with only right child { if (temp==parent->left) parent->left= temp->right Else parent->right=temp->right } //Deletion of node with two children AVL tree Named after their inventors Adelson, Velski & Landis, AVL trees are height balancing binary search tree. AVL tree Let’s consider creation of a BST i.e. insert values starting from an empty tree Insert values 1, 2, 3, 4, 5, 6, 7, 8, 9 into an empty BST If inserted in given order, what is the tree? Is inserting in the reverse order any better? BST: Efficiency of Operations? Problem: Worst-case running time: find, insert, delete buildTree How can we make a BST efficient? Observation Solution: Require a Balance Condition that When we build the tree, make sure it’s balanced. BUT…Balancing a tree only at build time is insufficient. We also need to also keep the tree balanced as we perform operations. Potential Balance Conditions Left and right subtrees Left and right subtrees The AVL Tree Data Structure An AVL tree is a self-balancing binary search tree. Structural properties Binary tree property (same as BST) Order property (same as for BST) Balance condition: balance of every node is between -1 and 1 where balance(node) = height(node.left) – height(node.right) Example #1: Is this an AVL Tree? Balance Condition: 6 balance of every node is between -1 and 1 where balance(node) = 4 height(node.left) – 8 height(node.right) 1 7 11 10 12 Example #2: Is this an AVL Tree? 6 Balance Condition: balance of every node is between -1 and 1 4 8 where balance(node) = height(node.left) – height(node.right) 1 5 7 11 3 2 AVL Trees 3 10 2 2 5 20 0 1 1 0 2 9 15 30 0 0 7 17 First insert example Insert(6) Insert(3) Insert(1) Third insertion What’s the only way to fix it? Fix: Apply “Single Rotation” AVL 3 6 Property violated at node 6 3 1 6 1 Single rotation: The basic operation we’ll use to rebalance – Move child of unbalanced node into parent position – Parent becomes the “other” child (always okay in a BST!) – Other subtrees move in only way BST allows (we’ll see in generalized example) TREE ROTATIONS: GENERALIZED Generalizing our examples… 12 5 23 2 9 18 30 1 4 7 10 Generalizing our examples… 12 5 23 2 9 18 30 1 4 7 10 Generalizing our examples… 12 5 E A C Generalizing our examples… 12 d b E A C Generalized Single Rotation d b E A C Generalized Single Rotation b d A C E Single Rotations (Figures by Melissa O’Neill, reprinted with her permission to Lilian) Rotations Insert 1,2,3 Right-Right or R-R case Solution: rotate left Insertion First, insert the new key as a new leaf just as in ordinary binary search tree Then trace the path from the new leaf towards the root. For each node x encountered, check if heights of left(x) and right(x) differ by at most 1. If yes, proceed to parent(x). If not, restructure by doing either a single rotation or a double rotation For insertion, once we perform a rotation at a node x, we won’t need to perform any rotation at any ancestor of x. Rotations Insert 3,2,1 Left-Left or L-L situation Solution: Rotate right Rotations Insert 1,2,3 Right-Right or R-Right situation Solution: one rotation Rotations Insert 1,3,2 Right-Left or R-L situation Solution: Two rotations – Rotate right  R-R – Rotate left Rotations Insert 1,3,2 Right-Left or R-L situation Solution: Two rotations – Rotate right R-R – Rotate left Rotations Insert 3,1, 2 Left-Right or L-R situation Solution: Two rotations – Rotate left L-L – Rotate right Rotation summary L-L then single rotation --> rotate right R-R then single rotation--> rotate left L-R then double rotation --> rotate left to get L-L then rotate right R-L then double rotation --> rotate right to get R-R then rotate left Example- 12, 45, 65, 23, 89, 50, 4, 35,100 Create AVL tree:10, 20, 30, 25, 40, 50, 35, 33, 37, 60,38 Balance the tree Example 3: 8,3,5,25,76, 45, 30,26,28,27 Case #1: d b E A C a ’ (Figures by Melissa O’Neill, reprinted with her permission to Lilian) Example #2 for left-left case: insert(16) 15 8 22 4 10 19 24 3 6 17 20 16 Case #2: (Figures by Melissa O’Neill, reprinted with her permission to Lilian) Example for right-right case: insert(26) 15 15 8 24 8 22 24 4 10 22 25 4 10 19 3 6 3 6 19 23 23 25 26 26 Case #3: (Figures by Melissa O’Neill, reprinted with her permission to Lilian) A Better Look at Case #3: (Figures by Melissa O’Neill, reprinted with her permission to Lilian) Case #3: Right-Left Case (after one rotation) right rotate A way to remember it: Move d to grandparent’s position. Put everything else in their only legal positions for a BST. (Figures by Melissa O’Neill, reprinted with her permission to Lilian) Practice time! Example of Case #4 Starting 60 Which of the with this following is 30 80 the updated AVL tree: AVL tree after 10 50 inserting 42? A B C D 42 30 50 ) 50 ) ) ) 30 60 10 50 30 60 30 60 10 50 80 42 60 80 10 42 80 10 42 80 Pros and Cons of AVL Trees Arguments for AVL trees: 1. All operations logarithmic worst-case because trees are always balanced 2. Height balancing adds no more than a constant factor to the speed of insert and delete Arguments against AVL trees: 3. Difficult to program & debug [but done once in a library!] 4. More space for height field 5. Asymptotically faster but rebalancing takes a little time 6. If amortized logarithmic time is enough, use splay trees (also in the text, not Queries? Thank you!

Document Details

Tags

Related

Full Transcript

Upgrade to continue