CU-BCA-SEM-III-DATA STRUCTURES- Second Draft-converted

} 151 b)public void insertBegin(Node node) { head = node; node.setNext(head); size++; } c)public void insertBegin(Node node) { Node temp = head.getNext() node.setNext(temp); head = node; size++; } d)public void insertBegin(Node node) { Node temp = head.getNext() node.setNext(temp); node = head; size++; } 2. What is the functionality of the following piece of code? public int function(int data) { Node temp = head; int var = 0; while(temp != null) { if(temp.getData() == data) CU IDOL SELF LEARNING MATERIAL (SLM)

{ return var; } var = var+1; temp = temp.getNext(); } return Integer.MIN_VALUE; } a. Find and delete a given element in the list. b. Find and return the given element in the list. c. Find and return the position of the given element in the list. d. Find and insert a new element in the list. 3. Which of the following is false about a doubly linked list? a. We can navigate in both the directions. b. It requires more space than a singly linked list. c. The insertion and deletion of a node take a bit longer. d. Implementing a doubly linked list is easier than singly linked list. 4. What differentiates a circular linked list from a normal linked list? a. You cannot have the ‘next’ pointer point to null in a circular linked list. b. It is faster to traverse the circular linked list. c. You may or may not have the ‘next’ pointer point to null in a circular linked list. d. Head node is known in circular linked list. 5. Which of the following application makes use of a circular linked list? 152 a. Undo operation in a text editor b. Recursive function calls c. Allocating CPU to resources d. Implement Hash Tables CU IDOL SELF LEARNING MATERIAL (SLM)

Answer 1. (a) 2. (c) 3. (d) 4. (c) 5. (c) 11.9 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 153 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 12: TREE Structure 12.0 Learning Objective 12.1 Definition and Terminology 12.2 Memory Representation Using Linked List 12.3 Traversal (In-order, Pre-order, Post-order) 12.4 Summary 12.5 Keywords 12.6 Learning activity 12.7 Unit End Questions 12.8 References 12.0 LEARNING OBJECTIVE After studying this unit, Students will be able • Explain the basic concepts of trees. • Analyse the memory representation using linked list. • Describe the Traversal techniques. 12.1 DEFINITION AND TERMINOLOGY A tree may be a hierarchical arrangement defined as a set of nodes. Nodes represent value and nodes are connected by edges. A tree has the subsequent properties: 1. The tree has one node called root. The tree originates from this, and hence it doesn't have any parent. 2. Each node has one parent only but can have multiple children. 3. Each node is connected to its children via edge. 154 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 12.1: Tree Representation Terminology: In a tree data structure, we use the following terminology Root In a tree arrangement, the primary node is named as Root Node. Every tree must have a root node. we will say that the basis node is that the origin of the tree arrangement. In any tree, there must be just one root node. We never have multiple root nodes during a tree. Figure 12.2: Root Node Representation Edge In a tree arrangement, the connecting link between any two nodes is named as EDGE. during a tree with 'N' number of nodes there'll be a maximum of 'N-1' number of edges. Figure 12.3: Edge Node Representation Parent In a tree arrangement, the node which may be a predecessor of any node is named as PARENT NODE. In simple words, the node which features a branch from it to the other node is named a parent node. Parent node also can be defined as \"The node which has child / children\". 155 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 12.4: Parent Node Representation Child In a tree arrangement, the node which is descendant of any node is named as CHILD Node. In simple words, the node which features a link from its parent node is named as child node. In a tree, any parent node can have any number of kid nodes. Figure 12.5: Child Node Representation Siblings In a tree arrangement, nodes which belong to same Parent are called as SIBLINGS. In simple words, the nodes with an equivalent parent are called Sibling nodes. Figure 12.6: Sibling Node Representation Leaf In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words, a leaf is a node with no child. In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node with no child. In a tree, leaf node is also called as 'Terminal' node. 156 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 12.7: Leaf Node Representation Internal Nodes In a tree arrangement, the node which has at least one child is named as INTERNAL Node. In simple words, an indoor node may be a node with at least one child. during a tree arrangement, nodes aside from leaf nodes are called as Internal Nodes. the basis node is additionally said to be Internal Node if the tree has quite one node. Internal nodes also are called as 'Non-Terminal' nodes. Figure 12.8: Internal Node Representation Degree In a tree arrangement, the entire number of youngsters of a node is named as DEGREE of that Node. In simple words, the Degree of a node is total number of youngsters it’s. the very best degree of a node among all the nodes during a tree is named as 'Degree of Tree' Figure 12.9: Degree Representation 157 CU IDOL SELF LEARNING MATERIAL (SLM)

Level In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a tree each step from top to bottom is called as a Level and the Level count starts with '0' and incremented by one at each level (Step). Figure 12.10: Level Representation Height In a tree arrangement, the entire number of edges from leaf node to a specific node within the longest path is named as HEIGHT of that Node. In a tree, height of the basis node is claimed to be height of the tree. In a tree, height of all leaf nodes is '0'. Figure 12.11: Height Representation Depth In a tree arrangement, the entire number of edges from root node to a specific node is named as DEPTH of that Node. In a tree, the entire number of edges from root node to a leaf node within the longest path is claimed to be Depth of the tree. In simple words, the very best depth of any leaf node during a tree is claimed to be depth of that tree. In a tree, depth of the basis node is '0'. 158 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 12.12: Depth Representation Path In a tree arrangement, the sequence of Nodes and Edges from one node to a different node is named as PATH between that two Nodes. Length of a Path is total number of nodes therein path. In below example the trail A - B - E - J has length 4. Figure 12.13: Path Representation Sub Tree In a tree arrangement, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node. Figure 12.14: Sub Tree Representation 159 CU IDOL SELF LEARNING MATERIAL (SLM)

12.2 MEMORY REPRESENTATION USING LINKED LIST TREE: The tree data structure is often created by creating the nodes dynamically with the assistance of the pointers. The tree within the memory is often represented as shown below: The below figure 12.14 shows the representation of the tree arrangement within the memory. within the above structure, the node contains three fields. The second field stores the data; the primary field stores the address of the left child, and therefore the third field stores the address of the proper child. Figure 12.15: Tree List Representation Structure of a node: struct Node { int data; struct Node *Left; struct Node *Right; } Types of Trees: Trees are majorly divided into 4 different types considering their representations, functions and accessing. They are: 1. Binary Tree 2. Binary Search Tree 3. AVL Tree 160 CU IDOL SELF LEARNING MATERIAL (SLM)

4. B-Tree Binary Trees: Binary Tree is a special data structure used for data storage purposes. A binary tree features a special condition that every node can have a maximum of two children. A binary tree has the advantages of both an ordered array and a linked list as search is as quick as during a sorted array and insertion or deletion operation are as fast as in linked list. Figure 12.16: Binary Tree Representation Types of Binary Tree: Full Binary Tree A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children. It is also known as a proper binary tree. Figure 12.17: Full Binary Tree Representation 161 CU IDOL SELF LEARNING MATERIAL (SLM)

Perfect Binary Tree A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level. Figure 12.18: Perfect Binary Tree Representation All the internal nodes have a degree of 2. Recursively, a perfect binary tree can be defined as: • If a single node has no children, it is a perfect binary tree of height h = 0, • If a node has h > 0, it is a perfect binary tree if both of its subtrees are of height h - 1 and are non-overlapping. Complete Binary Tree A complete binary tree is just like a full binary tree, but with two major differences • Every level must be completely filled • All the leaf elements must lean towards the left. • The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree. 162 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 12.19: Complete Binary Tree Representation Degenerate or Pathological Tree: A degenerate or pathological tree is the tree having a single child either left or right. Figure 12.20: Pathological Tree Representation Skewed Binary Tree: A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left- skewed binary tree and right-skewed binary tree. Figure 12.21: Skewed Binary Tree Representation 163 Balanced Binary Tree: CU IDOL SELF LEARNING MATERIAL (SLM)

It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1. Following are the conditions for a height-balanced binary tree: ▪ Difference between the left and the right subtree for any node is not more than one ▪ The left subtree is balanced ▪ The right subtree is balanced Figure 12.22: Balanced Binary Tree Representation Binary Search Tree: Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers. • It is called a binary tree because each tree node has a maximum of two children. • It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. The properties that separate a binary search tree from a regular binary tree is • All nodes of left subtree are less than the root node • All nodes of right subtree are more than the root node • Both subtrees of each node are also BSTs i.e. they have the above two properties 164 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 12.23: Binary Search Tree Representation The binary tree on the right isn't a binary search tree because the right subtree of the node \"3\" contains a value smaller than it. 12.3 TRAVERSAL (IN-ORDER, PRE-ORDER, POST-ORDER) Traversal may be a process to go to all the nodes of a tree and should print their values too. Because, all nodes are connected via edges (links) we always start from the basis (head) node. You might, as an example, want to feature all the values within the tree or find the most important one. For of these operations, you'll got to visit each node of the tree. That is, we cannot randomly access a node during a tree. There are 3 ways which we use to traverse a tree 1. In-order Traversal 2. Pre-order Traversal 3. Post-order Traversal Figure 12.24: Tree Representation Let's think about how we can read the elements of the tree in the image shown above. 165 CU IDOL SELF LEARNING MATERIAL (SLM)

Starting from top, Left to right 1 -> 12 -> 5 -> 6 -> 9 Starting from bottom, Left to right 5 -> 6 -> 12 -> 9 -> 1 Although this process is somewhat easy, it doesn't respect the hierarchy of the tree, only the depth of the nodes. Instead, we use traversal methods that take into account the basic structure of a tree Figure 12.25: Node Representation In order traversal: • First, visit all the nodes in the left subtree • Then the root node • Visit all the nodes in the right subtree Algorithm: begin procedure Inorder(Root) if(Root == NULL) return; end if inorder(Root->Left) display(Root->data) inorder(Root->Right) end procedure Example: 166 void printInorder(struct node* node) CU IDOL SELF LEARNING MATERIAL (SLM)

{ 167 if (node == NULL) return; /* first recur on Left child */ printInorder(node->Left); /* then print the data of node */ printf(\"%d \", node->data); /* now recur on Right child */ printInorder(node->Right); } Preorder traversal: • Visit root node • Visit all the nodes in the Left subtree • Visit all the nodes in the Right subtree Algorithm: begin procedure preorder(Root) if(Root == NULL) return; end if display(Root->data) preorder(Root->Left) preorder(Root->Right) end procedure Example: void printPreorder(struct node* node) { if (node == NULL) CU IDOL SELF LEARNING MATERIAL (SLM)

return; 168 /* first print data of node */ printf(\"%d \", node->data); /* then recur on Left sutree */ printPreorder(node->Left); /* now recur on Right subtree */ printPreorder(node->Right); } Postorder traversal: • Visit all the nodes in the Left subtree • Visit all the nodes in the Right subtree • Visit the root node Algorithm: begin procedure postorder(Root) if(Root == NULL) return; end if postorder(Root->Left) postorder(Root->Right) display(Root->data) end procedure Example: void printPostorder(struct node* node) { if (node == NULL) return; // first recur on Left subtree CU IDOL SELF LEARNING MATERIAL (SLM)

printPostorder(node->Left); // then recur on Right subtree printPostorder(node->Right); // now deal with the node printf(\"%d \", node->data); } Now, let us see a practical example experiencing how different traversals on a same Tree differs. Figure 12.26: Tree Traversal 12.4 SUMMARY • A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges. Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically. • Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. • Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. You might, for instance, want to add all the values in the tree or find the largest one. For all these operations, you will need to visit each node of the tree. That is, we 169 CU IDOL SELF LEARNING MATERIAL (SLM)

cannot randomly access a node in a tree. There are three ways which we use to traverse a tree − 1. In-order Traversal 2. Pre-order Traversal 3. Post-order Traversal 12.5 KEYWORDS • Path − Path refers to the sequence of nodes along the edges of a tree. • Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. • Parent − Any node except the root node has one edge upward to a node called parent. • Child − The node below a given node connected by its edge downward is called its child node. • Leaf − The node which does not have any child node is called the leaf node. • Subtree − Subtree represents the descendants of a node. • Visiting − Visiting refers to checking the value of a node when control is on the node. • Traversing − Traversing means passing through nodes in a specific order. • Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on. • Keys − Key represents a value of a node based on which a search operation is to be carried out for a node. • Insert − Inserts an element in a tree/create a tree. • Search − Searches an element in a tree. • Preorder Traversal − Traverses a tree in a pre-order manner. • Inorder Traversal − Traverses a tree in an in-order manner. • Postorder Traversal − Traverses a tree in a post-order manner. 12.6 LEARNING ACTIVITY 1. Show that via AVL single rotations, any binary search tree T1 can be transformed into another search tree T2 (with the same keys). ___________________________________________________________________________ ____________________________________________________________________ 170 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Write a procedure to traverse a tree stored with child/sibling links. ___________________________________________________________________________ ____________________________________________________________________ 12.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define complete binary tree. 2. What is root, branch, siblings and degree of a tree 3. Write the pre-order, in-order, post-order traversal for the tree 4. What is an BST – binary search tree? 5. Define tree. List the tree traversal techniques Long Questions 1. Explain various tree traversal algorithms with implementation. 2. Write a non-recursive and recursive algorithm for in order tree traversal 3. Write down an algorithm to find the max and smallest element in a tree structure 4. Explain in details about tree terminology 5. Write an algorithm to declare nodes of a tree structure and list the tree traversal B. Multiple choice Questions 1. In preorder traversal of a binary tree the second step is ____________ a. traverse the right subtree b. traverse the left subtree c. traverse right subtree and visit the root d. visit the root 171 CU IDOL SELF LEARNING MATERIAL (SLM)

2. From the following code identify the which traversal of a binary tree is this __________ //if node has left child order(node.left) //if node has right child order(node.right) visit(node) a. Inorder traversal b. preorder traversal c. postorder traversal d. Euler tour traversal 3. From the following code identify the which traversal of a binary tree is this __________ function traversal(node) { //Input:root node of the tree //Output:None visitLeft(node) //if node has left child traversal(node.left) visit_Below(node) //if node has right child traversal(node.right) visitRight(node) } a. Inorder traversal b. Euler Tour traversal c. Post-order traversal d. Pre-order Traversal 172 CU IDOL SELF LEARNING MATERIAL (SLM)

4. For the tree below, write the in-order traversal. a. 6, 2, 5, 7, 11, 2, 5, 9, 4 b. 6, 5, 2, 11, 7, 4, 9, 5, 2 c. 2, 7, 2, 6, 5, 11, 5, 9, 4 d. 2, 7, 6, 5, 11, 2, 9, 5, 4 5. For the tree below, write the level-order traversal. a. 6, 2, 5, 7, 11, 2, 5, 9, 4 173 b. 6, 5, 2, 11, 7, 4, 9, 5, 2 c. 2, 7, 2, 6, 5, 11, 5, 9, 4 d. 2, 7, 6, 5, 11, 2, 9, 5, 4 Answer 1. (b) 2. (c) 3. (b) 4. (a) 5. (b) 12.8 REFERENCES CU IDOL SELF LEARNING MATERIAL (SLM)

Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 174 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 13: BINARY SEARCH TREE Structure 13.0 Learning Objective 13.1 Introduction and Its Operations 13.2 Heap and Heap Sort 13.3 AVL Tree 13.4 B-Tree and Its Operations 13.5 Summary 13.6 Keywords 13.7 Learning activity 13.8 Unit End Questions 13.9 References 13.0 LEARNING OBJECTIVE After studying this unit, Students will be able • Describe how to declare structures to be used in binary trees. • Analyse the basic operations and applications of a binary search tree. • Outline and implement, what a heap is when referring to a tree structure. • Describe the concept in AVL trees, what the definition of AVL property is and demonstrate the ability to identify diagrams of trees as to whether they have the AVL property. • Define the operations of AVL trees such as search, insertion & deletion. Discuss with diagrams, the algorithms for a single left rotation, single right rotation, double left rotation, and double right rotation in AVL trees. 13.1 INTRODUCTION AND ITS OPERATIONS The binary search tree is an advanced algorithm used for analyzing the node, its left and right branches, which are modelled in a tree structure and returning the value. The BST is devised on the architecture of a basic binary search algorithm; hence it enables faster lookups, insertions, and removals of nodes. This makes the program fast and accurate. The properties that separate a binary search tree from a daily binary tree is 175 CU IDOL SELF LEARNING MATERIAL (SLM)

1. All nodes of the left subtree are but the basis node 2. All nodes of the proper subtree are quite the basis node 3. Both subtrees of every node also are BSTs i.e. they need the above two properties Figure 13.1: Binary Tree Representation BST Node: struct Node { int data; struct node *LeftChild; struct node *RightChild; }; Basic Operations on BST: Following are the basic operations of a tree Insert − Inserts an element in a tree. Search − Searches an element in a tree. Pre-order Traversal − Traverses a tree in a pre-order manner. In-order Traversal − Traverses a tree in an in-order manner. Post-order Traversal − Traverses a tree in a post-order manner. Insert: Whenever a component is to be inserted, first locate its proper location. Start searching from the basis node, then if the info is a smaller amount than the key value, look for the empty location within the left subtree and insert the info. Otherwise, look for the empty location within the right subtree and insert the info. Algorithm: begin procedure Insert(Root , data) If Node == NULL 176 CU IDOL SELF LEARNING MATERIAL (SLM)

return createNode(data) if (data < Node->data) Node->left = insert(Node->left, data); else if (data > Node->data) Node->right = insert(Node->right, data); return Node; end procedure Example Program: struct Node* Insert(struct Node* Root, int key) { if (Root == NULL) { return newNode(key); } if (key < Root->key) { Root->Left= Insert(Root->Left, key); } else if (key > Root->key) { Root->Right = Insert(Root->Right, key); } return Node; } 177 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 13.2: Binary Tree Insertion Search Operation: Whenever a component is to be searched, start searching from the basis node. Then if the info is a smaller amount than the key value, look for the element within the left subtree. Otherwise, look for the element within the right subtree. Follow an equivalent algorithm for every node. In a normal binary tree, if we'd like to look for a component, we'd like to traverse the whole tree (in the worst case). But in BST, we will optimize this by using its properties to our advantage. The basic idea is sort of simple really. Let’s assume we'd like to look for value item during a BST. once we compare it with the basis of the tree, we are left with three cases → item == root.data: We terminate the search because the item is found item > root.data: We just check the proper subtree because all the values within the left subtree are lesser than root.data item < root.data: Now we just check the left subtree as all values within the right subtree are greater than root.data We keep it up recursing during this manner and this decreases our search time complexity up to an excellent extent as we just got to check out one subtree and reject the opposite subtree saving us the difficulty of comparing a batch of values. Follow the Steps to realize BST Search Our objective is to return True if a node exists with the worth adequate to the item, else return False. 178 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Check if the root is NULL, return False if it is NULL. 179 2. Else, Compare root.data with item 3. item == root.data: return True 4. item > root.data: recurse for right subtree 5. item < root.data: recurse for left subtree Algorithm: begin procedure search(Root, item) if ( Root == NULL ) return False; if ( item == Root.data ) print(item); else if ( item > Root.data ) return search(Root.right, item); else if ( item < Root.data ) return search(Root.left, item); begin procedure Example Program: struct node* search(int data){ struct node *current = Root; printf(\"Visiting elements: \"); while(current->data != data){ if(current != NULL) { printf(\"%d \",current->data); //go to left tree CU IDOL SELF LEARNING MATERIAL (SLM)

if(current->data > data){ current = current->leftChild; } //else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; } Applications of BST: BSTs are used for a lot of applications due to its ordered structure. • BSTs are used for indexing and multi-level indexing. • They are also helpful to implement various searching algorithms. • It is helpful in maintaining a sorted stream of data. • TreeMap and TreeSet data structures are internally implemented using self-balancing BSTs 13.2 HEAP AND HEAP SORT A heap is a complete binary tree, and the binary tree is a tree in which the node can have utmost two children. Before knowing more about the heap data structure, we should know about the complete binary tree. There are two types of the heap: • Min Heap 180 CU IDOL SELF LEARNING MATERIAL (SLM)

• Max heap Min Heap: The key present at any node must be smaller than the keys present at both of its children. The smallest key is at the root node. Figure 13.3: Min Heap Representation Max Heap: The key present at any node must be greater than the keys present at both of its children. The largest key is at the root node. Figure 13.4: Max Heap Representation Heap Operations: • heapify: rearranges the elements in the heap to maintain the heap property. • insert: adds an item to a heap while maintaining its heap property. • delete: removes an item in a heap. 181 CU IDOL SELF LEARNING MATERIAL (SLM)

• extract: returns the value of an item and then deletes it from the heap. • isEmpty: boolean, returns true if boolean is empty and false if it has a node. • size: returns the size of the heap. • getMax(): returns the maximum value in a heap Implementation of a Heap: Let us implement a min-heap using an array. Let’s put the min-heap in the image above into an array: Figure 13.5: Heap Array Representation If we are looking at the i-th index in an array: • It’s parent is at the floor (i-1)/2 index. • It’s left child is at 2 * i + 1 index. • It’s right child is at 2 *i + 2 index. In complete binary trees, each level is filled up before another level is added and the levels are filled from left to right. Insertion To insert a node: • Add the node to the bottom of the tree. • Look at the parent node. If the parent is greater than the node, swap them. • Continue comparing and swapping to allow the node to bubble up until it finds a parent node that is smaller than it. 182 CU IDOL SELF LEARNING MATERIAL (SLM)

The height of a tree is log(n). Therefore, the worst case scenario is that the newly added node is smaller than every single parent node, causing us to traverse all the way to the top of the tree. This will cost us O(log(n)) time. Deletion (Removing the smallest element) Because our min-heap has the smallest element at the root node, we know exactly where it is in our array. Accessing this element takes O(1) time. If we want to delete the element, we must shift the entire tree upwards to fill the root node’s place. To do this: • Take the bottom level’s right most node (the last element in the array) and move it to top, replacing the deleted node. • Compare the new root to its children. If it is larger than either child, swap the item with the smaller of the two children. • Continue comparing and swapping, bubbling down the node until it is smaller than both of its children. Heap Sort: • Since the tree satisfies Max-Heap property, then the largest item is stored at the root node. • Swap: Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place. • Remove: Reduce the size of the heap by 1. • Heapify: Heapify the root element again so that we have the highest element at root. • The process is repeated until all the items of the list are sorted. Example: 12, 6,10,5,1,9 183 CU IDOL SELF LEARNING MATERIAL (SLM)

184 CU IDOL SELF LEARNING MATERIAL (SLM)

185 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 13.6 Heap Sort Example Program: #include <stdio.h> // Function to swap the position of two elements void swap(int *First, int *Second) { int temp = *First; *First = *Second; *Second = temp; } void heapify(int arr[], int n, int i) { // Find largest among root, left child and right child int Largest = i; int Left = 2 * i + 1; int Right = 2 * i + 2; if (Left < n && arr[Left] > arr[Largest]) Largest = Left; if (Right < n && arr[Right] > arr[Largest]) Largest = Right; // Swap and continue heapifying if root is not Largest 186 CU IDOL SELF LEARNING MATERIAL (SLM)

if (Largest != i) { swap(&arr[i], &arr[Largest]); heapify(arr, n, Largest); } } // Main function to do heap sort void heapSort(int arr[], int n) { // Build max heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i >= 0; i--) { swap(&arr[0], &arr[i]); // Heapify root element to get highest element at root again heapify(arr, i, 0); } } // Print an array 187 void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) printf(\"%d \", arr[i]); printf(\"\\n\"); } int main() { int arr[] = {1, 12, 9, 5, 6, 10}; int n = sizeof(arr) / sizeof(arr[0]); CU IDOL SELF LEARNING MATERIAL (SLM)

heapSort(arr, n); printf(\"Sorted array is \\n\"); printArray(arr, n); } Applications of Heap: • Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nlogn). • Priority Queue: It uses binary heap to efficient implement operations insert(), delete(), extract_max(), update() in O(logn) time. • Graph Algorithms: Some of the Graph Algorithms also use heaps to reduce its time complexity like Dijkstra’s Algorithm and Minimum Spanning Tree. • K-way merge: A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream. • Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or Largest) element in an array. 13.3 AVL TREE The AVL tree may be a binary search tree with a height balance. that's to mention, an AVL tree may be a binary search tree that's also balanced. If the peak difference between the left and right subtrees of a node within the tree is either -1, 0 or +1, the binary tree is claimed to be balanced. In other words, a binary tree is claimed to be balanced if the peak of left and right children of each node differs by either -1, 0 or +1. In an AVL tree, every node maintains an additional information referred to as balance factor. Balance factor of a node is that the difference between the heights of the left and right subtrees of that node. The balance factor of a node is calculated either height of left subtree - height of right subtree (OR) height of right subtree - height of left subtree. 188 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 13.7 AVL Rotations Single Left Rotation (LL Rotation): In LL Rotation, every node moves one position to left from the current position. To understand LL Rotation Figure 13.8 AVL Single Left Rotations Single Right Rotation (RR Rotation): In RR Rotation, every node moves one position to right from the current position. To understand RR Rotation. 189 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 13.9 AVL Single Right Rotations Left Right Rotation (LR Rotation): The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR Rotation, at first, every node moves one position to the left and one position to right from the current position. Figure 13.10 AVL Left Right Rotations Right Left Rotation (RL Rotation): The RL Rotation is sequence of single right rotation followed by single left rotation. In RL Rotation, initially every node moves one position to right and one position to left from the present position. 190 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 13.11 AVL Right Left Rotations Node Representation: Struct AVLTree { int data; struct AVLTree *Left, *Right; int Height; }; Operations on an AVL Tree: The following operations are performed on AVL tree. 1. Search 2. Insertion 3. Deletion Insertion operation: struct AVLTree *Insert(struct AVLTree *r,int data) { if(r==NULL) { struct AVLTree *n; n = (struct AVLTree *)malloc(sizeof(struct AVLTree)); n->data = data; r = n; r->Left = r->Right = NULL; r->Height = 1; return r; } else{ if(data < r->data) r->Left = Insert(r->Left,data); else 191 CU IDOL SELF LEARNING MATERIAL (SLM)

r->Right = Insert(r->Right,data); } r->Height = calheight(r); if(bf(r)==2 && bf(r->Left)==1){ r = llrotation(r); } else if(bf(r)==-2 && bf(r->Right)==-1){ r = rrrotation(r); } else if(bf(r)==-2 && bf(r->Right)==1){ r = rlrotation(r); } else if(bf(r)==2 && bf(r->Left)==-1){ r = lrrotation(r); } return r; } Deletion: In deletion also, we delete the node to be deleted within the same way as we do with a traditional binary search tree. then, we fix the unbalance of any ancestor node with suitable rotations. the sole thing is that unlike insertion, it'd be possible that the unbalance propagates above the tree in deletion which makes us rebalance the ancestor nodes. Let's check out some samples of deletion then the rationale for an equivalent are going to be clear. In AVL tree, there are often three cases of deletion - the node to be deleted has no child, the node to be deleted has one child or the node to be deleted has 2 children. within the third case when the node has 2 children, we replace the content of the nodes with its successor and it reduces to the deletion of the node with either one child or none. After the deletion procedure, the heights of ancestor nodes will decrease and this might cause unbalance within the tree. Example Program: struct Node *deleteNode(struct AVLTree *root, int key) { 192 CU IDOL SELF LEARNING MATERIAL (SLM)

// Find the node and delete it if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if ((root->left == NULL) || (root->right == NULL)) { struct AVLTree *temp = root->left ? root->left : root- >right; if (temp == NULL) { temp = root; root = NULL; } else *root = *temp; free(temp); } else { struct AVLTree *temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } } if (root == NULL) return root; 193 CU IDOL SELF LEARNING MATERIAL (SLM)

// Update the balance factor of each node and // balance the tree root->height = 1 + max(height(root->left), height(root->right)); int balance = getBalance(root); if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } 13.4 B-TREE AND ITS OPERATIONS B Tree may be a specialized m-way tree which will be widely used for access. A B-Tree of order m can have at the most m-1 keys and m children during all one amongst one in every of\"> one among the most reason of using B tree is its capability to store sizable number of keys in a single node and enormous key values by keeping the peak of the tree relatively small. A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties. 1. Every node in a B-Tree contains at most m children. 194 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children. 3. The root nodes must have at least 2 nodes. 4. All leaf nodes must be at the same level. Figure 13.12 B-Tree Representation Operations on a B-Tree: The following operations are performed on a B-Tree 1. Search 2. Insertion 3. Deletion Search: Searching a B-tree is far like searching a binary search tree, except that rather than making a binary, or \"two-way,\" branching decision at each node, we make a multiway branching decision consistent with the amount of the node's children. More precisely, at each internal node x, we make an (n[x] + 1)-way branching decision. B-TREE-SEARCH may be a straightforward generalization of the TREE-SEARCH procedure defined for binary search trees. B-TREE-SEARCH takes as input a pointer to the basis node x of a subtree and a key k to be looked for therein subtree. The top-level call is thus of the shape B-TREE- SEARCH(root[T], k). If k is within the B-tree, B-TREE-SEARCH returns the ordered pair (y,i) consisting of a node y and an index i such keyi[y] = k. Otherwise, the worth NULL is returned. Algorithm: Procedure B-TREE-SEARCH(x, k) i1 while i n[x] and k keyi[x] do i i + 1 195 CU IDOL SELF LEARNING MATERIAL (SLM)

if i n[x] and k = keyi[x] then return (x, i) if leaf [x] then return NIL else DISK-READ(ci[x]) return B-TREE-SEARCH(ci[x], k) end procedure Insertion: Inserting a key k into a B-tree T of height h is completed during a single pass down the tree, requiring O(h) disk accesses. The CPU time required is O(th) = O(t logt n). The B-TREE- INSERT procedure uses B-TREE-SPLIT-CHILD to ensure that the recursion never descends to a full node. Insertion Operation: 1. If the tree is empty, allocate a root node and insert the key. 2. Update the allowed number of keys in the node. 3. Search the appropriate node for insertion. 4. If the node is full, follow the steps below. 5. Insert the elements in increasing order. 6. Now, there are elements greater than its limit. So, split at the median. 7. Push the median key upwards and make the left keys as a left child and the right keys as a right child. 8. If the node is not full, follow the steps below. 9. Insert the node in increasing order. Algorithm: Procedure BreeInsertion(T, k) r root[T] if n[r] = 2t - 1 s = AllocateNode() root[T] = s leaf[s] = FALSE n[s] <- 0 196 CU IDOL SELF LEARNING MATERIAL (SLM)

c1[s] <- r 197 BtreeSplitChild(s, 1, r) BtreeInsertNonFull(s, k) else BtreeInsertNonFull(r, k) BtreeInsertNonFull(x, k) i = n[x] if leaf[x] while i ≥ 1 and k < keyi[x] keyi+1 [x] = keyi[x] i=i-1 keyi+1[x] = k n[x] = n[x] + 1 else while i ≥ 1 and k < keyi[x] i=i-1 i=i+1 if n[ci[x]] == 2t - 1 BtreeSplitChild(x, i, ci[x]) if k &rt; keyi[x] i=i+1 BtreeInsertNonFull(ci[x], k) BtreeSplitChild(x, i) BtreeSplitChild(x, i, y) z = AllocateNode() leaf[z] = leaf[y] n[z] = t - 1 for j = 1 to t - 1 keyj[z] = keyj+t[y] if not leaf [y] for j = 1 to t cj[z] = cj + t[y] CU IDOL SELF LEARNING MATERIAL (SLM)

n[y] = t - 1 for j = n[x] + 1 to i + 1 cj+1[x] = cj[x] ci+1[x] = z for j = n[x] to i keyj+1[x] = keyj[x] keyi[x] = keyt[y] n[x] = n[x] + 1 end procedure Deletion: Assume that procedure B-TREE-DELETE is asked to delete the key k from the subtree rooted at x. This procedure is structured to ensure that whenever B-TREE-DELETE is named recursively on a node x, the amount of keys in x is a minimum of the minimum degree t. Note that this condition requires another key than the minimum required by the standard B-tree conditions, in order that sometimes a key may need to be moved into a toddler node before recursion descends thereto child. This strengthened condition allows us to delete a key from the tree in one downward pass without having to \"back up\" (with one exception, which we'll explain). the subsequent specification for deletion from a B-tree should be interpreted with the understanding that if it ever happens that the basis node x becomes an indoor node having no keys, then x is deleted and x's only child c1[x] becomes the new root of the tree, decreasing the peak of the tree by one and preserving the property that the basis of the tree contains a minimum of one key (unless the tree is empty). 1. If the key k is in node x and x is a leaf, delete the key k from x. 2. If the key k is in node x and x is an internal node, do the following. ▪ If the kid y that precedes k in node x has a minimum of t keys, then find the predecessor k' of k within the subtree rooted at y. Recursively delete k', and replace k by k' in x. (Finding k' and deleting it are often performed during a single downward pass.) ▪ Symmetrically, if the kid z that follows k in node x has a minimum of t keys, then find the successor k' of k within the subtree rooted at z. Recursively delete k', and replace k by k' in x. (Finding k' and deleting it are often performed during a single downward pass.) 198 CU IDOL SELF LEARNING MATERIAL (SLM)

▪ Otherwise, if both y and z have only t- 1 keys, merge k and every one of z into y, in order that x loses both k and therefore the pointer to z, and y now contains 2t - 1 keys. Then, free z and recursively delete k from y. Figure 13.13 B-Tree leaf Node Deletion 3. If the key k is not present in internal node x, determine the root ci[x] of the appropriate subtree that must contain k, if k is in the tree at all. If ci[x] has only t - 1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then, finish by recursing on the appropriate child of x. a. If ci[x] has only t - 1 keys but has a sibling with t keys, give ci[x] an extra key by moving a key from x down into ci[x], moving a key from ci[x]'s immediate left or right sibling up into x, and moving the appropriate child from the sibling into ci[x]. 199 CU IDOL SELF LEARNING MATERIAL (SLM)

b. If ci[x] and all of ci[x]'s siblings have t - 1 keys, merge ci with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node. Figure 13.14 B-Tree Key Deletion Since most of the keys during a B-tree are within the leaves, we may expect that in practice, deletion operations are most frequently wont to delete keys from leaves. The B-TREE- DELETE procedure then acts in one downward undergo the tree, without having to copy. When deleting a key in an indoor node, however, the procedure makes a downward undergo the tree but may need to return to the node from which the key was deleted to exchange the key with its predecessor or successor. 13.5 SUMMARY • Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers. • It is called a binary tree because each tree node has a maximum of two children. • It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. • The properties that separate a binary search tree from a regular binary tree is • All nodes of left subtree are less than the root node • All nodes of right subtree are more than the root node • The AVL tree is a binary search tree with a height balance binary search tree. If the height difference between the left and right subtrees of a node in the tree is either -1, 0 or +1, the binary tree is said to be balanced 200 CU IDOL SELF LEARNING MATERIAL (SLM)