UNIT III Non Linear Data Structures - Trees.pptx

Non Linear Data Structure - Trees

1. UNIT 3 Non Linear Data Structures - Trees Tree ADT – tree traversals - Binary Tree ADT – expression trees – applications of trees – binary search tree ADT –Threaded Binary Trees- AVL Trees – B-Tree - B+ Tree - Heap – Applications of heap.

2. Nonlinear Data Structures The data structure where data items are not organized sequentially is called non linear data structure A data item in a non linear data structure could be attached to several other data elements to reflect a special relationship among them and all the data items cannot be traversed in a single run Data structures like trees and graphs are some examples of widely used non linear data structures

3. TREE A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges It stores the information naturally in the form of hierarchical style In this, the data elements can be attached to more than one element exhibiting the hierarchical relationship which involves the relationship between the child, parent , and grandparent A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees In a general tree, A node can have any number of children nodes but it can have only a single parent

4. Tree of species

5. BOOK AS TREE

6. TREE TERMINOLOGY

7. TREE TERMINOLOGIES

8. 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. 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 .

9. 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.

10. 3 . Parent

11. 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 .

12. 6 . Degree Degree of a node is the total number of children of that node. Degree of a tree is the highest degree of a node among all the nodes in the tree.

13. 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

14. 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

15. 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 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.

16. 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.

17. BINARY TREE  Binary tree is a special tree data structure in which each node can have at most 2 children .  Thus, in a binary tree , each node has either 0 child or 1 child or 2 children.

18. Binary Tree Representation 1. Array Representation 2. Linked Representation

19. Binary Tree using Array Representation

20. Contd..

21. Linked List Representation of Binary Tree Double linked list used to represent a binary tree. In a double linked list, every node consists of three fields . First field for storing left child address , second for storing actual data and third for storing right child address struct node { int data; struct node * leftchild ; struct node * rightChild ; };

22. Linked List Representation of Binary Tree In this linked list representation, a node has the following structure...

23. Binary Tree Traversals Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal. There are three types of binary tree traversals. In -Order Traversal Pre -Order Traversal Post -Order Traversal

24. 1. Inorder Traversal Algorithm- 1.Traverse the left sub tree i.e. call Inorder (left sub tree) 2.Visit the root 3.Traverse the right sub tree i.e. call Inorder (right sub tree) Left → Root → Right void inorder_traversal ( struct node * root) { if(root != NULL) { inorder_traversal (root- > leftChild ); printf ("%d ",root->data); inorder_traversal (root- > rightChild ); } }

25. 2. Preorder Traversal Algorithm- 1. Visit the root 2. Traverse the left sub tree i.e. call Preorder (left sub tree) 3. Traverse the right sub tree i.e. call Preorder (right sub tree) Root→Left→Right void preorder_traversal ( struct node* root) { if(root != NULL) { printf ("%d ",root->data); preorder_traversal (root-> leftChild ); preorder_traversal (root-> rightChild ); } }

26. 3. Postorder Traversal Algorithm- Traverse the left sub tree i.e. call Postorder (left sub tree) Traverse the right sub tree i.e. call Postorder (right sub tree) Visit the root Left → Right → Root void postorder_traversal ( struct node * root) { if(root != NULL) { postorder_traversal (root- > leftChild ); postorder_traversal (root- > rightChild ); printf ("%d ", root->data); } }

27. Types of Binary Trees FULL BINARY TREE PERFECT BINARY TREE COMPLETE BINARY TREE SKEWED BINARY TREE

28. 1 . Full / Strictly Binary Tree A binary tree in which every node has either 0 or 2 children is called as a Full binary tree . Full binary tree is also called as Strictly binary tree . 2. Perfect Binary Tree A Perfect binary tree that satisfies the following 2 properties- Every internal node has exactly 2 children. All the leaf nodes are at the same level.

29. 3.Complete Binary Tree A complete binary tree that satisfies the following 2 properties- All the levels are completely filled except possibly the last level. The last level must be strictly filled from left to right . 4. Skewed Binary Tree A skewed binary tree that satisfies the following 2 properties- All the nodes except one node has one and only one child. The remaining node has no child.

30. Expression Tree Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand Construction of Expression Tree: For constructing expression tree we use a stack. We loop through input expression and do following for every character. 1)If character is operand push that into stack 2)If character is operator pop two values from stack make them its child and push current node again.

31. Example expression tree for 3 + ((5+9)*2)

32. Applications of binary trees Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries. Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered. Binary Tries - Used in almost every high-bandwidth router for storing router-tables. Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available. Heaps - Used in implementing efficient priority-queues . Huffman Coding Tree (Chip Uni ) - used in compression algorithms , such as those used by the .jpeg and .mp3 file-formats.

33. BINARY SEARCH TREE Binary Search Tree is a special kind of binary tree in which nodes are arranged in a specific order 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

34. BINARY SEARCH TREE Create the binary search tree using the following data elements 43 , 10, 79, 90, 12, 54, 11, 9, 50. Insert 43 into the tree as the root of the tree. Read the next element, if it is lesser than the root node element, insert it as the root of the left sub-tree. Otherwise , insert it as the root of the right of the right sub-tree.

35. 43, 10, 79, 90, 12 , 54, 11, 9, 50

36. Operations on BST Search − Searches an element in a tree. FindMin – Find Minimum element in a tree FindMax – Find Maximum element in a tree Insert − Inserts an element in a tree. Delete − deletes an element in a tree.

37. 1 . Search Operation Compare the key with the value of root node. If the key is present at the root node, then return the root node. If the key is greater than the root node value, then recur for the root node’s right subtree . If the key is smaller than the root node value, then recur for the root node’s left subtree .

38. Routine: Search (ROOT, ITEM) IF ROOT --> DATA = ITEM OR ROOT == NULL Return ROOT ELSE IF ITEM < ROOT --> DATA Return search(ROOT --> LEFT , ITEM) ELSE Return search(ROOT --> RIGHT , ITEM) [END OF IF] [END OF IF]

39. Example Consider key = 45 has to be searched in the given BST- We start our search from the root node 25. •As 45 > 25, so we search in 25’s right subtree . •As 45 < 50, so we search in 50’s left subtree . •As 45 > 35, so we search in 35’s right subtree . •As 45 > 44, so we search in 44’s right subtree but 44 has no subtrees . •So, we conclude that 45 is not present in the above BST.

40. 2 . Insertion Operation If the item to be inserted, will be the first element of the tree, then the left and right of this node will point to NULL. Else , check if the item is less than the root element of the tree, if this is true, then recursively perform this operation with the left of the root. If this is false, then perform this operation recursively with the right sub-tree of the root.

41. Routine: Insert(ROOT , ITEM) IF ROOT == NULL Allocate memory for TREE SET ROOT --> DATA = ITEM SET ROOT --> LEFT = ROOT --> RIGHT = NULL ELSE IF ITEM < ROOT --> DATA Insert(ROOT --> LEFT , ITEM) ELSE Insert(ROOT --> RIGHT , ITEM) [END OF IF] [END OF IF]

42. Example Consider the following example where key = 40 is inserted in the given BST- We start searching for value 40 from the root node 100. As 40 < 100, so we search in 100’s left subtree . As 40 > 20, so we search in 20’s right subtree . As 40 > 30, so we add 40 to 30’s right subtree .

43. FIND MIN Approach for finding minimum element: Traverse the node from root to left recursively until left is NULL. The node whose left is NULL is the node with minimum value . Int minValue ( struct node * root) { Struct node * current = root; /* loop down to find the leftmost leaf */ while (current->left != NULL) { current = current->left; } return(current->key); }

44. FIND MIN

45. FIND MAX Approch for finding maximum element: Traverse the node from root to right recursively until right is NULL. The node whose right is NULL is the node with maximum value. Int maxValue ( struct node * root) { Struct node * current = root; /* loop down to find the leftmost leaf */ while (current->right != NULL) { current = current->right; } return(current- >key); }

46. FIND MIN

47. 5. Delete Delete a node, will arise three possibilities. 1)  Node to be deleted is leaf:  Simply remove from the tree . 2)  Node to be deleted has only one child:  Copy the child to the node and delete the child

48. 3)  Node to be deleted has two children:   Delete the smallest data of the right subtree and recursively delete that node.

49. Example:

50. Example:

51. Advantages of using binary search tree Searching become very efficient in a binary search tree since, we get a hint at each step, about which sub tree contains the desired element The binary search tree is considered as efficient data structure in compare to arrays and linked lists In searching process, it removes half sub tree at every step Searching for an element in a binary search tree It also speed up the insertion and deletion operations as compare to that in array and linked list

52. Threaded Binary Tree The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion.  There are two types of threaded binary trees. Single Threaded :  Where a NULL right pointers is made to point to the inorder successor (if successor exists) Double Threaded :  Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively.

53. AVL Tree - Problem behind the BST When the BST starting with the data: 10,20,30,40 It is similar to the normal linear search Unbalanced tree

54. AVL Tree Adelson-Velsk y and Landis (AVL) trees is a self-balancing binary search trees. Balancing factor of each node is either 0 or 1 or -1. Properties : Maximum possible number of nodes in AVL tree of height  

55. AVL Trees Named after their inventor  Adelson ,  Velski  &  Landis ,  AVL trees  are height balancing binary search tree. A VL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the  Balance Factor BalanceFactor = height(left- sutree ) − height(right- sutree ) If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some rotation techniques.

56. AVL NODE DECLARATION Struct node { Int data ; Int h ; Struct node *left , *right; } *T=null;

57. Calculating Balancing Factor BF=height(t- >right) -height(t->left) The balance factor(bf) of an AVL tree may take on one of the values -1, 0, +1

58. Calculating Balancing Factor Another Eg . to calculate BF,

59. AVL Rotations To balance, AVL tree perform the four kinds of rotations  Left rotation Right rotation Left-Right rotation Right-Left rotation The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, at least need a tree of height 2

60. Right Rotation AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree . The tree then needs a right rotation. Imbalance occur when inserting at Left of Left sub tree,

61. RR Routine Pos SRWL( pos k2 ) { Pos k1 ; k1=k2->left; k2->left=k1->right; k1->right=k2; k2->h=1+max(height(k2->left),height(k2->right)); k1- > h=1+max(height(k1- >left), height(k1- >right)); return k1; }

62. Left Rotation If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree , then we perform a single left rotation Imbalance occur when inserting data at Right of Right sub tree,

63. LR Routine Pos SRWR ( pos k1) { pos k2; k2=k1-->right; k1--> right=k2 -->left; k2 --> left=k1; k1- ->h=1+max(height(k1 -->left),height(k1 -->right)); K2-->h=1+max(height(k2--> left), height(k2--> right)); return k2; }

64. Double Rotation -Left Right Rotation A node has been inserted into the right subtree of the left subtree . first perform the left rotation on the left subtree of  3. This makes  1 , the left subtree of  2 . Node  3  is still unbalanced, however now, it is because of the left- subtree of the left- subtree now right-rotate the tree, making  2  the new root node of this subtree .  3  now becomes the right subtree of its own left subtree .

65. LRR Routine Pos DRWL ( pos k3) { k3- ->left=SRWR(k3 -->left); return SRWL(k3); }

66. Double Rotation - (Right Left Rotation ) A node has been inserted into the left subtree of the right subtree . This makes  1 , an unbalanced node with balance factor 2. perform the right rotation along  3  node, making  3  the right subtree of its own left subtree   2 . Now,  2  becomes the right subtree of  A . Node  1  is still unbalanced because of the right subtree of its right subtree and requires a left rotation.

67. RLR Routine Pos DRWR( pos k1 ) { k1->right=SRWL(k1->right); return SRWR(k1); }

68. Insert in AVL Void insert( int x, pos ) { if(t==NULL) { t=( pos ) malloc ( sizeof ( struct node )); t->data=x; t->h=0; t->left=t->right=NULL; } else if(x<t->data) { t->left=insert( x,t ->left); if(height(t->left)-height(t->right)==2) { if(x<t->left->data) else if(x>t->data) { t->right=insert( x,t ->right); if(height(t->right)-height(t->left)==2) { if(x>t->right->data) t=SRWR(t ); else t=DRWR(t ); } } else printf ("element is in the tree already"); t- >h=1+max(height(t->left),height(t->right)); return t; } t=SRWL(t); else t=DRWL(t); }

69. BST

70. Splay Tree Splay tree is another variant of a binary search tree. In a splay tree, recently accessed element is placed at the root of the tree. It follow self adjusting mechanism In a splay tree, every operation is performed at the root of the tree. All the operations in splay tree are involved with a common operation called  "Splaying" .  Splaying an element, is the process of bringing it to the root position by performing suitable rotation operations. In a splay tree, splaying an element rearranges all the elements in the tree so that splayed element is placed at the root of the tree.

71. Rotations in Splay Tree 1.  Zig Rotation – right rotation 2.  Zag Rotation – left rotation 3.  Zig - Zig Rotation 4.  Zag - Zag Rotation 5.  Zig - Zag Rotation 6.  Zag - Zig Rotation

72. Zig Rotation The  Zig Rotation  in splay tree is similar to the single right rotation in AVL Tree rotations. In zig rotation, every node moves one position to the right from its current position.

73. Zag Rotation The  Zag Rotation  in splay tree is similar to the single left rotation in AVL Tree rotations. In zag rotation, every node moves one position to the left from its current position.

74. Zig-Zig Rotation The  Zig-Zig Rotation  in splay tree is a double zig rotation. In zig-zig rotation, every node moves two positions to the right from its current position.

75. Zag-Zag Rotation The  Zag-Zag Rotation  in splay tree is a double zag rotation. In zag-zag rotation, every node moves two positions to the left from its current position. 

76. Zig-Zag Rotation The  Zig-Zag Rotation  in splay tree is a sequence of zig rotation followed by zag rotation. In zig-zag rotation, every node moves one position to the right followed by one position to the left from its current position.

77. Zag-Zig Rotation The  Zag-Zig Rotation  in splay tree is a sequence of zag rotation followed by zig rotation. In zag-zig rotation, every node moves one position to the left followed by one position to the right from its current position

78. Insertion Operation in Splay Tree The insertion operation in Splay tree is performed using following steps... Step 1 -  Check whether tree is Empty. Step 2 -  If tree is Empty then insert the  newNode  as Root node and exit from the operation. Step 3 -  If tree is not Empty then insert the newNode as leaf node using Binary Search tree insertion logic. Step 4 -  After insertion,  Splay  the  newNode Deletion Operation in Splay Tree The deletion operation in splay tree is similar to deletion operation in Binary Search Tree. But before deleting the element, we first need to  splay  that element and then delete it from the root position. Finally join the remaining tree using binary search tree logic.

79. What is B tree ? Intro Invented by Rudolf Bayer and Ed McCreight in 1972 at Boeing Research Labs. B-Tree is known as balanced m-way tree and used in external sorting . It is a binary search tree Node with more than one keys Node with sorted data like 4,7,9 All leave should be in same level

80. Properties of B tree Each node has a maximum of M children and minimum of m/2 children Each node should have maximum of m-1 keys Root 2 childran Minimum key 1 (root) Other nodes [m/2]-1 Keys should be arranged in a defined order within the node Key to be inserted into a fullnode , the node is splitted into two nodes by taking the median value . All Leaves are to be at same level . no empty subtrees

81. B tree Example With Order m=4

82. Operations on B trees Basic three operations Insertion Deletion Search

83. Searching  Searching in B Trees is similar to that in Binary search tree For example, if we search for an item 49 in the following B Tree. The process will something like following : Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree. Since, 40<49<56, traverse right sub-tree of 40. 49>45, move to right. Compare 49. match found, return.

84. Searching

85. Inserting Insertions are done at the leaf node level Traverse the B Tree in order to find the appropriate leaf node at which the node can be inserted. If the leaf node contain less than m-1 keys then insert the element in the increasing order. Else, if the leaf node contains m-1 keys, then follow the following steps. Insert the new element in the increasing order of elements. Split the node into the two nodes at the median. Push the median element upto its parent node. If the parent node also contain m-1 number of keys, then split it too by following the same steps.

86. Insert the node 8 into the B Tree of order 5

87. Deletion Deletion is also performed at the leaf nodes. Locate the leaf node. If there are more than m/2 keys in the leaf node then delete the desired key from the node. If the leaf node doesn't contain m/2 keys then complete the keys by taking the element from eight or left sibling.

88. Heap A Heap is a special Tree-based data structure in which the tree is a complete binary tree . Max-Heap : In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children.  Min-Heap : In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children.

89. Popular topics in Heap Binary Heap Binomial Heap Fibonacci Heap Leftist Heap K- ary Heap Heap Sort Iterative Heap Sort

90. Binary Heap A Binary Heap is a Binary Tree with following properties. 1 ) It’s a complete tree ( All levels are completely filled except possibly the last level and the last level has all keys as left as possible). 2 ) A Binary Heap is either Min Heap or Max Heap .

91. Binary Heap A Binary Heap is a Binary Tree with following properties. 1 ) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). 2 ) A Binary Heap is either Min Heap or Max Heap.

92. Process of Insertion : First increase the heap size by 1, so that it can store the new element. Insert the new element at the end of the Heap.(create the hole) This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap,  heapify (percolate the hole)  this newly inserted element following a bottom-up approach. Heapify is the process of creating a heap data structure from a binary tree

93. Insert the new element at the end of the tree. (Max heap)

94. Heapify the tree.

95. Process of Deletion Replace the root or element to be deleted by the last element. Delete the last element from the Heap. Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore,  heapify   the last node placed at the position of root.

96. Select the element to be deleted

97. Swap it with the last element

98. Remove the last element.

99. Heapify the tree

100. Application of heap Heap is used to construct a priority queue. Heap sort  is one of the fastest sorting algorithms with time complexity of O(N* log(N), and it’s easy to implement. Best First Search (BFS)  - technique is implemented using a priority queue. Patient treatment: In a hospital, an emergency patient, or the patient with more injury is treated first. Here the priority is the degree of injury. Systems concerned with security use heap sort, like the Linux kernel.

101. Red-black tree Properties of Red-Black tree The red-Black tree  is a binary search tree Each node in the Red-black tree contains an extra bit that represents a color to ensure that the tree is balanced during any operations performed on the tree like insertion, deletion. 0 bit denotes the black color while 1 bit denotes the red color of the node Red-Black tree is a self-balanced binary search tree AVL is also a height-balanced tree. AVL tree requires many rotations when the tree is large whereas the Red-Black tree requires a maximum of two rotations to balance the tree The main difference between the  AVL tree  and the Red-Black tree is that the AVL tree is strictly balanced, while the Red-Black tree is not completely height-balanced.  Insertion is easier in the AVL tree as the AVL tree is strictly balanced, whereas deletion and searching are easier in the Red-Black tree as the Red-Black tree requires fewer rotations.

102. the node is either colored in  Red  or  Black  color In the Red-Black tree, the root node is always black in color. In a binary tree, we consider those nodes as the leaf which have no child. I n contrast, in the Red-Black tree, the nodes that have no child are considered the internal nodes and these nodes are connected to the NIL nodes that are always black in color. The NIL nodes are the leaf nodes in the Red-Black tree. If the node is Red, then its children should be in Black color. In other words, we can say that there should be no red-red parent-child relationship. Every AVL tree can be a Red-Black tree if we color each node either by Red or Black color. But every Red-Black tree is not an AVL because the AVL tree is strictly height-balanced while the Red-Black tree is not completely height-balanced.

103. Insertion in Red Black tree If the tree is empty, then we create a new node as a root node with the color black. If the tree is not empty, then we create a new node as a leaf node with a color red. If the parent of a new node is black, then exit. If the parent of a new node is Red, then we have to check the color of the parent's sibling of a new node. If the color is Black, then we perform rotations and recoloring . If the color is Red then we recolor the node. We will also check whether the parents' parent of a new node is the root node or not; if it is not a root node, we will recolor and recheck the node.