Geethanjali College of Engineering and Technology Data Structures AR22 Il year/l sem By D. Subhashini Sr. Asst. Professor CS Dept Geethanjali College of Engineering and TechnologyUNIT Ill Trees — Terminology, Representation of Trees, Binary tree ADT, Properties of Binary Trees, Binary Tree Representations-array and linked representations, Binary Tree traversals, Threaded binary trees. Max Priority Queue ADT - implementation-Max Heap-Definition, Insertion into a MaxHeap, Deletion from a Max Heap. Sorting- Merge sort, Heap Sort, Radix Sort, Binary insertion sort Comparison of Sorting methods. . Subhashini Asst ProfTree Basic A Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root. The nodes other than the root node are partitioned into the non empty sets where each one of them is to be called sub-tree, Nodes of a tree either maintain a parent-child relationship between them or they are sister nodes. In a general tree, A node can have any number of children nodes but it can have only a single parent. The following image shows a tree, where the node A is the root node of the tree while the other nodes can be seen as the children of A. Root Node > evel Tree terminology Root Node: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one which doesn't have any parent Sub Tree: If the root node is not null, the tree T1, T2 and T3 is called sub-trees of the root node. Leaf Node: The node of tree, which doesn't have any child node, is called leaf node. Leaf node is the bottorn most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes. Path: The sequence of consecutive edges is called path. In the tree shown in the above image, path to the node E is A+ B = E. . Subhash Asst ProfGeethanjali College of Engineering and Technology 4 + Ancestor node: An ancestor of a node is any predecessor node on a path from root to that node. The root node doesn't have any ancestors. In the tree shown in the above image, the node F have the ancestors, B and A. + Degree: Degree of a node is equal to number of children, a node have. In the tree shown in the above image, the degree of nade B is 2. Degree of a leaf node is always 0 while in a complete binary tree, degree of each non-leaf node is equal to 2 + Level Number: Each node of the tree is assigned a level number in such a way that each node is present at one level higher than its parent. Root node of the tree is always present at level 0. Types of Tree The tree data structure can be classified into six different categories. Tree | | Binary Tree ein 0 Binary Expression | Tournament Search Tree Tree Tree General Tree Forests Binary Tree Binary tree is a data structure in which each node can have at most 2 children. The node present at the top most level is called the root node. A node with the 0 children is called leaf node. Binary Trees are used in the applications like expression evaluation and many more. Binary Search Tree Binary search tree is an ordered binary tree. All the elements in the left sub-tree are less than the root while elements present in the right sub-tree are greater than or equal to the root, node element. Binary search trees are used in most of the applications of computer science domain like searching, sorting, etc. D. Subhashini Asst ProfBinary Tree Binary Tree is a special type of generic tree in which, each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets. 1, Root of the node 2. left sub-tree which is also a binary tree. 3. Right binary sub-tree A binary Tree is shown in the following image. Root Node Binary Tree We can define binary tree as: + Finite (possibly empty) collection of elements. + Anonempty binary tree has a root element. + The remaining elements (if any) are partitioned into two binary trees. + These are called the left and right subtrees of the binary tree. Differences between A Tree & A Binary Tree + No node in a binary tree may have a degree more than 2, whereas there is no limiton the degree of a node in a tree. + Abinary tree may be empty; a tree cannot be empty. + The subtrees of a binary tree are ordered; those of a tree are not ordered.+ Above trees are different when viewed as binary trees. + Are the same when viewed as trees. Properties of Binary Trees 1. Maximum number of nodes * The maximum number of nodes on level i of a binary tree is 2', i >= 0. + The maximum number of nodes in a binary tree of depth k is 2* - 1, k > 2. Relation between number of leaf nodes and nodes of degree + For any nonempty binary tree, T, if no is the number of leaf nodes and nz the number of nodes of degree 2, then no = no+1, Types of Binary Tree Strictly Binary Tree In Strictly Binary Tree, every non-leaf node contain non-empty left and right sub-trees. In other words, the degree of every non-leaf node will always be 2, A strictly binary tree with nleaves, will have (2n - 1) nodes. A strictly binary tree is shown in the following figure. Strictly Binary Tree . SubhasComplete Binary Tree A Binary Tree is said to be a complete binary tree if all of the leaves are located at the samelevel |. A complete binary tree Is a binary tree that contains exactly 2! nodes at each level between level 0 and i. Root Node elo level level2 Complete Binary Tree ABDECEG In a complete binary tree with depth d, d>=1, = Total number of nodes = 2-1 + Total number of leaf nodes = 2+ + Total number of non-leaf nodes =Binary Tree representation There are two types of representation of a binary tree: Linked Representation In this representation, the binary tree is stored in the memory, in the form of a linked list where the number of nodes are stored at non-contiguous memory locations and linked together by inheriting parent child relationship like a tree. Every node contains three parts + pointer to the left child + data element + pointer to the right child struct Node { int data; Node *left; Node “right; h Each binary tree has a root pointer which points to the root node of the binary tree. In an ‘empty binary tree, the root pointer will point to null Consider the binary tree given in the figure below. yf” xi) 8 |x ec] | x10 |X xl e |X In the above figure, a tree is seen as the collection of nodes where each node contains three parts : left pointer, data element and right pointer. Left pointer stores the address of the left child while the right pointer stores the address of the right child. The leaf node contains null in its left and right pointers.Sequential Representation This is the simplest memory allocation technique to store the tree elements but it is an inefficient technique since it requires a lot of space to store the tree elements. A binary tree is shown in the following figure along with its memory allocation. ‘Sequential Representation of Binary Tree + In this representation, an array is used to store the tree elements. The root node of the tree will be present at the 1* index of the array. + If anode is stored at ith index then its left children will be stored at 2i location. + If anode is stored at ith index then its right children will be stored at 2i+1 location. * If the 1% index of the array i.e. tree[1] is 0, it means that the tree is empty. D. Subhashini Asst ProfBinary Tree ADT structure Binary_Tree (abbreviated BinTree) is objects: a finite set of nodes either empty or consisting of a root node, left Binary_Tree, and right Binary_Tree. functions: for all bt,bt1,bt2 € BinTree, item € element BinTree Create() Boolean isEmpty(b.) BinTree MakeBY(bt1, item, br2) BinTree Lchiid(bt) element Datatbi) BinTree Rehild(bt) creates an empty binary tree if (br == empty binary tree) return TRUE else return FALSE return a binary tree whose left subtree is brl, whose right subtree is br2. and whose root node contains the data item. if (sEmpty(bs)) return error else return the left subtree of br. if (isEmpty(b)) return error else return the data in the root node of br. if (IsEmpty(b1)) return error else return the right subtree of br. Abstract data type Binary TreeBinary Tree Traversal SN | Traversal | Description 1) Pre- Traverse the root first then traverse into the left sub-tree and order right sub-tree respectively. This procedure will be applied to each Traversal | sub-tree of the tree recursively. 2| In-order | Traverse the left sub-tree first, and then traverse the root and Traversal | the right sub-tree respectively. This procedure will be applied to each sub-tree of the tree recursively, 3| Post: Traverse the left sub-tree and then traverse the right sub-tree order and root respectively. This procedure will be applied to each sub- Traversal tree of the tree recursively. Pre-order traversal + Visit the root node ‘+ traverse the left sub-tree in pre-order + traverse the right sub-tree in pre-order ‘Sequel Representation of nay Tree . Subhashini Asst ProfAlgorithm o Step 1: Repeat Steps 2 to 4 while TREE != NULL o Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT)[END OF LOOP] o Step 5: END C Function void pre-order(struct treenode *tree) « ‘if(tree != NULL) « printf("6d",tree— root); pre-order(tree— left); pre-order(tree— right); > Example Traverse the following binary tree by using pre-order traversal jince, the traversal scheme, we are using is pre-order traversal, therefore, thefirst element to be printed is 18. + traverse the left sub-tree recursively. The root node of the left sub-tree is 211,print it and move to left. * Left is empty therefore print the right children and move to the right sub- tree ofthe root. + 20s the root of sub-tree therefore, print it and move to its left. Since left sub-tree is empty therefore move to the right and print the only element present there i.e. 190. . Subhashini Asst+ Therefore, the printing sequence will be 18, 211, 12, 20, 190. In-order traversal ‘© Traverse the left sub-tree in in-order + Visit the root + Traverse the right sub-tree in in-order Algorithm + Step 1: Repeat Steps 2 to 4 while TREE != NULL * Step 2: INORDER(TREE -> LEFT) = Step 3: Write TREE -> DATA * Step 4: INORDER(TREE -> RIGHT)[END OF LOOP] + Step 5: END C Function void in-order(struct treenode *tree) { if(tree != NULL) { in-order(tree— left); printf("%d" tree root); in-order(tree-> right); Example Traverse the following binary tree by using in-order traversal, Yo =< 2 a ; ) @) (@) D. Subhashini Asst Profprint the left most node of the left sub-tree i.e, 23. print the root of the left sub-tree i.e. 211 print the right child i.e, 89. print the root node of the tree i.e, 18. Then, move to the right sub-tree of the binary tree and print the left most node ie, 10. print the root of the right sub-tree i.e, 20. print the right child i.e, 32. hence, the printing sequence will be 23, 211, 89, 18, 10, 20, 32. Post-order traversal + Traverse the left sub-tree in post-order + Traverse the right sub-tree in post-order + visit the root Algorithm = Step 1: Repeat Steps 2 to 4 while TREE != NULL * Step 2: POSTORDER(TREE -> LEFT) + Step 3: POSTORDER(TREE -> RIGHT) © Step 4: Write TREE -> DATA[END OF LOOP] © Step 5: END C Function void post-order(struct treenode *tree) £ if(tree £ NULL) post-order(tree— left); post-order(tree— right); printf("%d",tree— root); }Example Traverse the following tree by using post-order traversal ‘+ Print the left child of the left sub-tree of binary tree i.e. 23. + print the right child of the left sub-tree of binary tree i.e. 89. + print the root node of the left sub-tree i.e, 211 + Now, before printing the root node, move to right sub-tree and print the left child ie. 10. + print 32 i.e. right child. + Print the root node 20. + Now, at the last, print the root of the tree i.e. 18. The printing sequence will be 23, 89, 214, 10, 32, 20, 18.Threaded Binary Trees If we look carefully at the linked representation of any binary tree, we notice that there are more null links than actual pointers. Specifically, there are n + 1 null links out of 2n total links. A. J. Perlis and C, Thornton have devised a clever way to make use of these null links. They replace the null links by pointers, called threads, to other nodes in the tree, To construct the threads we use the following rules (assume that ptr represents a node). + If ptr -> left-child is null, replace ptr -> left-child with a pointer to the node that would be visited before ptr in an inorder traversal. That is we replace the null link with a pointer to the inorder predecessor of ptr. + If ptr -> right-child is null, replace ptr -> right-child with a pointer to the node that would be visited after ptr in an inorder traversal. That is we replace the null link with a pointer to the inorder successor of ptr. Threaded wee The above figure shows the binary tree with its threads drawn as dotted lines. This tree has nine nodes and 10 null links that we have replaced by threads. If we traverse the tree In inorder, we visit the nodes in the order H, D, I, B, E, A, F, C, G. To see how the threads are created we will use node & as an example. Since E's left child is a null link, we replace it with a pointer to the node that comes before E, which is B. Similarly, since E’s right child is also null, we replace the null link with a pointer to the node that comes after E in an inorder traversal, which is ‘A. We create the remaining threads in a similar fashion. . Subhashini Asst ProfWhen we represent the tree in memory, we must be able to distinguish between threads and normal pointers. This is done by adding two additional fields to the node structure, left-thread and right-thread. Assume that ptr is an arbitrary node in a threaded tree. + If ptr -> leftthread = TRUE, then ptr -> leftchild contains a thread; otherwise it contains a pointer to the left child, + If ptr -> rightthread = TRUE, then ptr -> rightchild contains a thread; otherwise it contains a pointer to the right child. This node structure is given by the following C declarations: struct threadedNode int leftthread; threadedNode *leftchild; int data; threadedNode *rightchild; int rightthread; oa In the above figure two threads have been left dangling: one in the left child of H, the other in the right child of G. Obviously we do not want to have loose threads in our tree. Therefore, we assume that all threaded binary trees have @ head node, with the property An empty threaded tree always contains one node, as represented in the following Figure. left_thread left_child data right child right_thread TRUE : —_ . FALSE a ‘An empty threaded tree The complete memory representation of our example is shown in the below figure, + The variable root points to the head node of the tree. + the root -> leftchild points to the start of the first node of the actual tree. This is true for all threaded trees. Notice that we have handled the problem of the loose threads by having them point to the head node, root. . Subhashinife], +], [K; ‘Memory representation of a threaded tree . Subhas Sr Ast, ProfGeethanjali College of Enginecring and Technology 9 Heap Data Structures Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If a has child node B then key(a) 2 key(B) As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types For Input + 35 33 42 10 14 19 27 44 26 31 Min-Heap — Where the value of the root node is less than or equal to either of its children. Max-Heap — Where the value of the root node is greater than or equal to either of its children. Both trees are constructed using the same input and order of arrival. . Subhas Sr Ast, ProfGeethanjali College of Enginecring and Technology 20 structure MaxHeap is objects: a complete binary tree of n > 0 elements organized so that the value in each node is at least as large as those in its children functions: for all heap € MaxHeap, item € Element, n, max—size € integer MaxHeap Create(max_size) == create an empty heap that can hold a maximum of max_size elements. Boolean HeapFull(heap, n) = if (v== max-size) return TRUE else return FALSE if (!HeapFull(heap, n)) MaxHeap Insert(heap, item, n) insert item into heap and return the resulting heap else return error. Boolean HeapEmpty(heap,n) :: if (n>0) return TRUE else return FALSE Element Delete(heap, n) of the largest element is, the heap and if (‘HeapEmpty(heap, n)) return one instance remove it from the heap else return error. Abstract data type MaxHeap Max Heap Construction Algorithm We shall use the same example to demonstrate how a Max Heap is created, The procedure to create Min Heap is similar but we go for min values instead of max values. We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree. Step 1 - Create a new node at the end of heap Step 2 - Assign new value to the node. Step 3 - Compare the value of this child node with its parent.Step 4 - If value of parent is less than child, then swap them.Step 5 - Repeat step 3 4 4 until Heap property holds. Note — In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node. Example: Insert 17 into a heap with elements 19,12,16,1,4,7.Geethanjali College of Engineering and Technology 2 C2) Gs) Sod HS (is) Insert 17 G2) @ od Percolate up to maintain the heap property swap Max Heap Deletion Algorithm Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value. Step 1 - Remove root node. Step 2 ~ Move the last element of last level to root. Step 3 - Compare the value of this child node with its parent.Step 4 - If value of parent is less than child, then swap them.Step 5 - Repeat step 3 4 4 until Heap property holds. Example:Covert the following into heap. we | 4 [7] 1 [afi ‘The complete binary tree representation of above data is: . Subhas 1 Sr Ast, ProfGeethanjali College of Engineering and Technology Steps to convert above tree into heap: swap GS Te) é & © Heap Sort Procedure: ‘* The heapsort algorithm consists of two phases: build a heap from an arbitrary array use the heap to sort the data ‘+ To sort the elements in the decreasing order, use a min heap ‘+ To sort the elements in the increasing order, use a max heap Steps to sort above Heap: 12 19 swap Step 1: el d be ele) Step 2: Soret Subhashin Ast. ProfGeethanjali College of Engineering and Technology 23 Step 3: D. Subhashin, SrASst Prof cS deptGeethanjali College of Engineering and Technology 24 Step 7: D. Subhashin, SrASst Prof cS deptGeethanjali College of Engineering and Technology 28 Step 10: D. Subhashin, SrASst Prof cS deptGeethanjali College of Engineering and Technology Step 13: Mowe hela clement tothe ge - Step 14: Areay A oa 3] Gri |a8fs6) Array A Heap Sort Program #include void adjust(int a[10],int,int); void heapify(int a[10],int n); // creating a heap of n arbitrary elementsvoid heapsort(int a[10],int n); void main() { int a[10},n,i; printf(“Enter no. of elements"); scanf("%d",&n); printf("\n enter data to be sored for (i=1;i<=njit++) scanf("%d",&aLi]); heapsort(a,n); printf("sorted data:\n"); for ( ++) printf(" %d" ali; + . Subhash SrAsst. Prof CS DeptGeethanjali College of E ig and Technology 2 void heapsort(int a[10],int n) < int i,t; heapify(a,n); for (i=nji>dji--) adjust(a,1,i-1); + + void adjust(int a[10],int i,int 1) « // the complete binary trees with roots a[2*i] and a[2*i+1] are // combined with a[i] to form a single heap; int item; int j= 2* i; item while (j < if (G= ali) break; alj/2] = ali]; j= 247 + a[j/2] = item; + void heapify(int a[10],int n) £ inti; for (i=n/2;i>: adjust(a,i,n); +Categories of Sorting The techniques of sorting can be divided Into two categories. These are: Internal Sorting External Sorting Internal Sorting: If all the data that is to be sorted can be adjusted at a time in the main memory, the internal sorting method is being performed External Sorting: When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, then external sorting methods are performed. Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps. 1. If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A intotwo sub-array of equal number of elements. 2. Conquer means sort the two sub-arrays recursively using the merge sort. 3. Combine the sub-arrays to form a single final sorted array maintaining theordering of the array. The main idea behind merge sort is that, the short list takes less time to be sorted, Complexity Complexity Best case Average Case Worst Case Time Complexity O(n log n) O(n log n) O(n log n) ‘Space Complexity O(n) Example : Consider the following array of 7 elements. Sort the array by using merge sort. A= (10, 5, 2, 23, 45, 21, 7}Geethanjali College ome [oe ][el2) | of Engineering and Technology 29 ove [oo l= |? |= | I ome [eps] Pela] % : cmp $b pt Combine wo] fs] fe 2 | | as [=] ‘ NZ NZ J corauerant (Ts | | [2l#)] [als 7 ae Sco cogurant = ae | me nna soned it | Merge Sort Program #include void mergeSort(int[],int,int); void merge(int[],int,int,int); void main() t int n,a[10]; int i; printf("Enter no. of element: scanf("%d",&n); printf("\n enter data to be sored .. for (i=0;i index++; + while(j<=end) £ templ[index] = afj]; index++; itty + while(i<=mid) id+1,k,index = beg; (i; i= ied; = 5H; . Subhas Sr Ast, ProfGeothanjali College of Engineering and Technology 3 < templindex] = ali]; index++; itt; + k = beg; while(k void insertionsort(int[],int); int binarysearch(int[],int,int,int); Void main () < int n,a[10]; inti; printf("Enter no. of elements”: scanf("%d",&n); printf("\n enter data to be sored for (i=0;iand Technology int binarysearch(int a[], int item, int low, int high) £ int mid; if (high <= low) return (item > a[low]) ? (low + 1) : low; id = (low + high) / 2; if (item == a[mid]) return mid + 4; if (item > a[mid]) return binarysearch(a, item, mid + 4, high); return binarysearch(a, item, low, mid - 1); void insertionsort(int af], int n) £ int i, item, j, k, pos; Azi= pos) < alj + 1) = alii; = + alj + 1] = item;Geethanjali College of Engineering and Technology 3 Radix Sort Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys. Rather than comparing elements directly, Radix Sort distributes the elements into buckets based ‘on each digit’s value. By repeatedly sorting the elements by their significant digits, from the least significant to the most significant, Radix Sort achieves the final sorted order. Radix Sort Algorithm The key idea behind Radix Sort is to exploit the concept of place value. It assumes that sorting numbers digit by digit will eventually result in a fully sorted list. Radix Sort can be performed using different variations, such as Least Significant Digit (LSD) Radix Sort or Most Significant Digit (MSD) Radix Sort. 170 17) j2 jo2 45 9) soz 24 Pass 1* Pass 2" 75 80) 45 for for tsi So: me ae is ——- bce 802 2 75 24 Oo 2 s 0 66 6 02 Ans. Time Complexity: O(n*d), Here d =10 Auxiliary Space: O(n) Radix Sort Program // Program to implement Radix Sort #include int getmax(int a[], int n); void countsort(int af], int n, int exp); sort(int a[], int n); void main () < int n,a[10]; int i; pr scanf("%d",&n); printf("\n enter data to be sored . void ra tf("Enter no. of elements’Geethanjali College of En for (i mid Technology njit+) radixsort(a,n); printf(“printing the sorted elements"); for(i=O;i m) m= ali]; return m; + // A function to do counting sort of arr[] according to // the digit represented by exp. void countsort(int af], int n, int exp) £ int temp[10]; i, count[10] = {0 }; // Store count of occurrences in count[] for (i= 0; i < nj i++) count[(a[i] / exp) % 10]++; // Change count[i] so that count[i] now contains actual // position of this digit in temp[] for (i = 1; 1 < 10; i++) count[i] += count[i - 1]; // Build the temp array for (i= n- 1; 1 >= 0; i--) { temp[count[(a[i] / exp) % 10] - 1] = afi]; count[(afi] / exp) % 10]--; ProfGeethanjali Colle Engineering and Technology 36 // Copy the contents of temp to array a // a contains sorted numbers according to current digit for (i= 0; i 0; exp *= 10) countsort(a, n, exp); Subhash Asst Prof