DSA Unit 3 2024 PDF

Data structures and their applications Unit - III Compiled by M S Anand Department of Computer Science Data Structures and their applications Introduction Text Book(s): 1. "Data Structures using C / C++", Langsum Yedidyah, Moshe J Augenstein, Aaron M Tenenbaum Pearson...

Data structures and their applications Unit - III Compiled by M S Anand Department of Computer Science Data Structures and their applications Introduction Text Book(s): 1. "Data Structures using C / C++", Langsum Yedidyah, Moshe J Augenstein, Aaron M Tenenbaum Pearson Education Inc, 2nd edition, 2015. Reference Book(s): 1. "Data Structures and Program Design in C", Robert Kruse, Bruce Leung, C.L Tondo, Shashi Mogalla, Pearson, 2nd Edition, 2019 31/10/2024 Data structures and their applications Binary Search Tree (BST) Binary Search Tree is a node-based binary tree data structure. which has the following properties: 1. The left subtree of a node contains only nodes with keys lesser than the node’s key. 2. The right subtree of a node contains only nodes with keys greater than the node’s key. 3. The left and right subtree each must also be a binary search tree. There must be no duplicate nodes. These properties of BST provide an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search a given key. 31/10/2024 Data structures and their applications BST – An example. 31/10/2024 Data structures and their applications BST – Another example. The binary tree on the right isn't a binary search tree because the right subtree of node 3 contains a value smaller than it. 31/10/2024 Data structures and their applications Operations on BST Three basic operations can be performed on a binary search tree :. Search Operation In Search, we have to find a specific element in the data structure. This searching operation becomes simpler in binary search trees because here elements are stored in sorted order. Algorithm for searching an element in a binary tree is as follows: 1. Compare the element to be searched with the root node of the tree. 2. If the value of the element to be searched is equal to the value of the root node, return the root node. 3. If the value does not match, check whether the value is less than the root element or not if it is then traverse the left subtree. 4. If larger than the root element, traverse the right subtree. 5. If the element is not found in the whole tree, return NULL. 31/10/2024 Data structures and their applications Operations on BST. We are searching for item 20. Step 1 31/10/2024 Data structures and their applications Operations on BST Step 2. 31/10/2024 Data structures and their applications Operations on BST Step 3. 31/10/2024 Data structures and their applications Operations on BST … Insert Operation. Inserting an element in a binary search tree is always done at the leaf node. To perform insertion in a binary search tree, we start our search operation from the root node, if the element to be inserted is less than the root value or the root node, then we search for an empty location in the left subtree, else, we search for the empty location in the right subtree. Algorithm for inserting an element in a binary tree is as follows: if node == NULL 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 31/10/2024 Data structures and their applications Operations on BST … Insert Operation. are trying to insert an item having a value of 65: we 31/10/2024 Data structures and their applications Operations on BST …. 31/10/2024 Data structures and their applications Operations in BST … Deletion Operation. the deletion operation, we have to delete a node from the binary In search tree in a way that does not violate its properties. Deletion can occur in three possible cases: Node to be deleted is the leaf node This is the simplest case of deleting a node in a binary search tree. Here, we will replace the leaf node with NULL and free the allocated space. We can understand the deletion operation in a binary search tree with the help of an example where we are trying to delete the node having a value of 90 31/10/2024 Data structures and their applications Operations in BST …. 31/10/2024 Data structures and their applications Operations in BST … Node to be deleted has a single child node. this case, we will replace the target node with its child and then delete In that replaced child node. This means that the child node will now contain the value to be deleted. So, we will just replace the child node with NULL and free up the allocated space. In the below example, we have to delete a node having a value of 79, and this node to be deleted has only one child, so it will be replaced with its child 55. 31/10/2024 Data structures and their applications Operations in BST … Node to be deleted has both the sub trees. The general algorithm is: to delete N, if it has two subtrees, replace the value in N with the largest value in its left subtree and then delete the node with the largest value from its left subtree. Note: The largest value in the left subtree will never have two subtrees. Why? Because if it's the largest value, it cannot have a right subtree. Can we achieve the same result using the right subtree? There is nothing special about the left subtree. We could do the same thing with the right subtree: just use the smallest value in the right subtree. 31/10/2024 Data structures and their applications Program to implement BST … 31/10/2024 Data structures and their applications Program to implement BST … Sample implementation is: BST_Implement.c BST_Implement.h BST_main.c 31/10/2024 Data structures and their applications Explanation of the program The search function checks if(root==NULL || root->data==x) which. means if the root is NULL then the element is not in the tree and if the root is equal to the target value x then the element is found. Otherwise, we implement else if(x > root->data), i.e. if the target element is greater than the root node data, we will search in the right subtree using search(root->right_child, x).Else, in the left subtree using search(root->left_child, x). In the insert function, if we have to insert a new node to the right child of a node X, we will first create a new node that is returned by insert(root->right_child, x) and then make the right child of X equal to that root->right_child = insert(root->right_child, x). Thus, after searching if we reach a null node, then we just insert a new node there using if(root==NULL) → return new_node(x). 31/10/2024 Data structures and their applications Explanation of the program … In the delete function, if the node to be deleted has no children we. if(root->left_child==NULL && root->right_child==NULL) which do will simply delete the node and free up the allocated space. While, if the node has only one child, we check if(root- >left_child==NULL) which means that only the right child exists and we have to delete this node and have to point its parent to its child, so we are storing its child into a temporary variable using temp = root->right_child and then deleting the node. If the node has two children, we find the minimum element of the right subtree using find_minimum(root->right_child). Now, we replace the data of the node to be deleted with the data of this node using root->data = temp->data. And then delete the node found by the minimum function using delete(root->right_child, temp->data). 31/10/2024 Data structures and their applications BST using Arrays …. 31/10/2024 Data structures and their applications BST using Arrays We will use array representation to make a binary tree in C and. then implement inorder, preorder, and postorder traversals. Let us consider the array given below and try to draw a tree from it: In the above image \0 represents NULL, like for node B both the right child and left child are NULL which implies B is a leaf node. A sample implementation is: BST using Arrays.c 31/10/2024 Data structures and their applications BST using Linked List. We will implement the tree shown in the above diagram, using linked lists. Sample implementation: BST_using_llists.c 31/10/2024 Data structures and their applications Expression Trees Expression trees are binary trees that are used to express various. expressions like infix, postfix, and prefix expressions. The internal nodes of this expression tree consist of operators like +, -, \*,/,^, etc. And the external nodes(leaf nodes) of the Expression tree contain the operands, on which operations are performed. The leaves of an Expression tree always contain the operands that can be of any data type like character, integer, double, etc. 31/10/2024 Data structures and their applications Expression Tree – An example. An expression tree for the following expression: a + (b * c) + d * (e + f) 31/10/2024 Data structures and their applications Expression Tree - Construction Construction of an Expression Tree A. stack is used to build an expression tree. For each character, we cycle through the input expressions and do the following. 1. If a character is an operand, create a one node tree and add the pointer to the stack. 2. If a character is an operator, form a new tree, pop two pointers (two one node trees) from the stack and make them the children of the new tree you have just created its children and push the new tree onto the stack.. Finally, the stack’s lone element will be the root of an expression tree. 31/10/2024 Data structures and their applications Expression Tree – Construction … We will build an expression corresponding to the following. expression: ab+c* Step1 : The first two symbols are operands, for which we generate a one-node tree and push the references onto the stack 31/10/2024 Data structures and their applications Expression Trees – Construction … Step 2: Next, read a’+’ symbol to pop two pointers to the tree, form a. new tree, and push a pointer to it onto the stack. Step 3: In the next stage ‘c’ is read, we build a single node tree and store a pointer to it on the stack. 31/10/2024 Data structures and their applications Expression Trees – Construction … Step 4 : Finally, we read the last symbol ‘*’, pop two tree pointers, and. build a new tree with a ‘*’ as root, and a pointer to the final tree remains on the stack. Sample implementation ExpTreeMain.c ExpTree.c ExpTree.h 31/10/2024 Data structures and their applications Binary Tree traversal - Iteration Predecessor and Successor. first greater value (with respect to a node) seen is The successor and the last smaller value seen is predecessor. Sample program: MorrisTraversal.c 31/10/2024 Data structures and their applications Binary Tree traversal - Iteration Algorithm. first greater value (with respect to a node) seen is The successor and the last smaller value seen is predecessor. 1. Initialize current as root 2. While current is not NULL If the current does not have left child a) Print current’s data b) Go to the right, i.e., current = current->right Else a) Find rightmost node in current left subtree OR node whose right child == current. If we found right child == current a) Update the right child as NULL of that node whose right child is current b) Print current’s data c) Go to the right, i.e. current = current->right Else a) Make current as the right child of that rightmost node we found; and b) Go to this left child, i.e., current = current->left. 31/10/2024 Data structures and their applications Threaded Binary Tree A binary tree is a data structure where every node can have up to. children. two There are different ways of traversing through the tree, one of them is in-order traversal. In inorder traversal, you visit the nodes “in order”, which means if the binary tree were a binary search tree, an inorder traversal would give us the elements in an increasing order However, to perform this traversal, we need to make use of recursion or use a stack to mimic the recursion. A Threaded Binary Tree lets us perform inorder traversal without the use of recursion or stack. 31/10/2024 Data structures and their applications Threaded Binary Tree What Is a Threaded Binary Tree?. a threaded binary tree, either of the NULL pointers of leaf nodes is In made to point to their successor or predecessor nodes What is the need for a Threaded Binary Tree? In a regular tree, the space complexity for insertion/ deletion can range from logarithmic to linear time. We get log time in a balanced binary tree and linear time is the worst case in an unbalanced tree. In applications where we have a constraint of space, or even when there is a use case of storing large trees in memory, we might need to save up on the extra space invested in the recursion depth. A threaded binary tree is advantageous in such scenarios where space usage is critical. 31/10/2024 Data structures and their applications Threaded Binary Tree …. In the figure above, there are many nodes present that hold a NULL value in their Left or Right child pointer. We can use the space occupied by these NULL values in order to store some kind of valuable information. One feasible way to use this space is to have a special pointer pointing to the nodes higher in the Tree (i.e., Ancestors). These special pointers are known as Threads, and the Binary Tree consisting of such pointers is known as the Threaded Binary Tree. 31/10/2024 Data structures and their applications Threaded Binary Tree … A Threaded Binary Tree is one of the variants of a normal Binary. Tree that assists faster tree traversal and doesn't need a Stack or Recursion. It reduces memory wastage by making the null pointers of a leaf node point to the in-order successor or in-order predecessor. A Threaded Binary Tree is a Binary Tree where all left child pointers which are NULL are made to point to their in-order predecessor, and all right child pointers which are NULL are made to point to their in- order successor. Moreover, the leftmost and the rightmost child pointers of a Treaded Binary Tree always point to null as their in-order predecessor and successor do not exist. 31/10/2024 Data structures and their applications Threaded Binary Tree …. The primary objective of creating such a structure is to make the in-order and pre-order traversal of the binary tree faster without any help of additional data structures (like an auxiliary stack) or memory for its traversal. 31/10/2024 Data structures and their applications Threaded Binary Tree … There are two types of Threaded Binary Trees:. Single Threaded Binary Tree 1. 2. Double Threaded Binary Tree Single Threaded Binary Tree The Single Threaded Binary Tree is a Threaded Binary Tee where only the right NULL pointers are made in to point to the in-order successor. If we use the left child to keep track of predecessors, it is called Left Threaded Binary Tree. If the right child pointer is used to keep track of the successor it is called Right Threaded Binary Tree. Structure of a Node in Single Threaded Binary Trees: The structure of a node in a Binary Threaded Tree is pretty much identical to that of a Binary Tree; with a few adjustments. In Threaded Binary Trees, we use additional Boolean variables in the node structure. We will only use a variable representing the right thread for the Single Threaded Binary Trees. 31/10/2024 Data structures and their applications Threaded Binary Tree … struct Node {. int data_value; struct Node* left_node; struct Node* right_node; bool right_thread; }; What Is the Significance of a Bool Variable in a Structure? Consider a single threaded binary tree. Any node in the binary tree can have its right pointer either to a child or the next successor node (which might not be the child node). Hence, we need a boolean variable that tells us whether the right pointer is pointing to a child or the next successor node 31/10/2024 Data structures and their applications Threaded Binary Tree … Single Threaded Binary Tree:. 31/10/2024 Data structures and their applications Threaded Binary Tree … Double Threaded Binary Tree. Double Threaded Binary Tree is a Threaded Binary Tree where The the left, as well as the right NULL pointers, are made to point the in- order predecessor and in-order successor, respectively. Structure of a Node in Double Threaded Binary Trees: struct Node { int data_value; struct Node* left_node; struct Node* right_node; bool left_thread; bool right_thread; }; 31/10/2024 Data structures and their applications Threaded Binary Tree … Double Threaded Binary Tree. 31/10/2024 Data structures and their applications Threaded Binary Tree … Advantages of the Threaded Binary Tree. the traversal operation is much faster than that of the Non-Threaded Binary Tree, 1. as the non-recursive implementation is possible with a Threaded Binary Tree which can execute faster and does not require the infliction of stack management. 2. we can efficiently determine the predecessor and successor nodes beginning from any node. with the help of threads instead of using a stack mechanism in the Threaded Binary Tree. 3. one can access any node from another. Threads are generally more upward, whereas the links are downward. Therefore, one can move in their direction in a threaded tree, and its nodes are circularly linked. This is impossible in Non- Threaded Binary Tree because we can only move in a downward direction beginning from the root. 4. it reduces memory waste. Whenever the left/right pointer of a normal Binary Tree is NULL, memory is wasted. However, one can overcome this problem with the help of the Threaded Binary Tree by storing its in-order predecessor/successor. 5. One can also perform a backward traversal using a Double-Threaded Binary Tree. 6. In-order Traversal in a Threaded Binary Tree is fast because we get the next node in O(1) time than a normal Binary Tree that takes O(height). However, the operations like insertion and deletions operations take more time in the case of a Threaded Binary Tree. 31/10/2024 Data structures and their applications Threaded Binary Tree … Disadvantages. 1. The main disadvantage of a Threaded Binary Tree is its complicated insertion and deletion operations. These operations become more time-consuming, and their process is highly complex by storing the in-order predecessor/successor for the node with a null left/right pointer. 2. Additional memory is used in the form of the variables defined for the left and right threads in order to distinguish between a thread from an ordinary link. (But there are more effective methods to differentiate between a thread and an ordinary link.) 31/10/2024 Data structures and their applications Threaded Binary Tree … In order traversal using threads. 1. We go to the left most node 1 2. Node 1 has boolean rightThread as true, hence next we visit its inOrder successor node 2 3. Node 2 has a right child, so we visit Node 3 next 4. Node 3 does not have a right child, ie the rightThread boolean is true, so we visit Node 4 next 5. Node 4 has a right child so we visit Node 5 and finish traversal 31/10/2024 Data structures and their applications Threaded Binary Tree implementation // Representation of a binary threaded tree. struct Node { struct Node *left, *right; int info; // true if left pointer points to predecessor in Inorder Traversal boolean lthread; // true if right pointer points to successor in Inorder Traversal boolean rthread; }; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert Let tmp be the newly inserted node. There can be three cases. during insertion: Case 1: Insertion in empty tree Both left and right pointers of tmp will be set to NULL and new node becomes the root. root = tmp; tmp -> left = NULL; tmp -> right = NULL; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert Case 2: When new node inserted as the left child. After inserting the node at its proper place, we have to make its left and right threads point to inorder predecessor and successor respectively. So, the left and right threads of the new node will be- tmp -> left = par ->left; tmp -> right = par; Before insertion, the left pointer of parent (par) was a thread, but after insertion it will be a link pointing to the new node. par -> lthread = false; par -> left = temp; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert An example. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert After insertion of 13. Predecessor of 14 becomes the predecessor of 13, so left thread of 13 points to 10. Successor of 13 is 14, so right thread of 13 points to left child which is 14. Left pointer of 14 is not a thread now, it points to left child which is 13. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert Case. 3: When new node is inserted as the right child The parent of tmp is its inorder predecessor. The node which was inorder successor of the parent is now the inorder successor of this node tmp. So the left and right threads of the new node will be- tmp -> left = par; tmp -> right = par -> right; Before insertion, the right pointer of parent was a thread, but after insertion it will be a link pointing to the new node. par -> rthread = false; par -> right = tmp; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert Insert 15. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Insert After insertion of 15. Successor of 14 becomes the successor of 15, so right thread of 15 points to 16 Predecessor of 15 is 14, so left thread of 15 points to 14. Right pointer of 14 is not a thread now, it points to right child which is 15. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete Case A: Leaf Node need to be deleted. In BST, for deleting a leaf Node the left or right pointer of parent was set to NULL. Here instead of setting the pointer to NULL it is made a thread. If the leaf Node to be deleted is left child of its parent, then after deletion, left pointer of parent should become a thread pointing to its predecessor of the parent Node after deletion. par -> lthread = true; par -> left = ptr -> left; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete. If the leaf Node to be deleted is right child of its parent, then after deletion, right pointer of parent should become a thread pointing to its successor. The Node which was inorder successor of the leaf Node before deletion will become the inorder successor of the parent Node after deletion. par -> rthread = true; par -> right = ptr -> right; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete Case B: Node to be deleted has only one child. After deleting the Node as in a BST, the inorder successor and inorder predecessor of the Node are found out. s = inSucc(ptr); p = inPred(ptr); If Node to be deleted has left subtree, then after deletion right thread of its predecessor should point to its successor. p->right = s; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete. Before deletion, 15 is predecessor and 20 is successor of 16. After deletion of 16, the Node 20 becomes the successor of 15, so right thread of 15 will point to 20. If Node to be deleted has right subtree, then after deletion left thread of its successor should point to its predecessor. s->left = p; 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete. Before deletion of 30, 25 is predecessor and 34 is successor of 30. After deletion of 30, the Node 25 becomes the predecessor of 34, so left thread of 34 will point to 25. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation - Delete Case C: Node to be deleted has two children. We find inorder successor of Node ptr (Node to be deleted) and then copy the information of this successor into Node ptr. After this, inorder successor Node is deleted using either Case A or Case B. 31/10/2024 Data structures and their applications Threaded Binary Tree implementation Sample implementation. ThreadBSTMain.c ThreadBST.c ThreadBST.h 31/10/2024 Data structures and their applications Heap What is Heap Data Structure?.A heap is a binary tree-based data structure that follows the heap property. In a heap, the value of each node is compared to the values of its children in a specific way. We are talking of an almost complete binary tree. i.e.,All the levels are filled except the last level and at the last level all nodes are aligned as much to the left as possible. Max-Heap: The value of each node is greater than or equal to the values of its children, ensuring that the root node contains the maximum value. As you move down the tree, the values decrease. For every node i, (except root) Arr [Parent of i] >= Arr [i] (Every node has a value more than its descendents) Min-Heap: The value of each node is less than or equal to the values of its children, ensuring that the root node contains the minimum value. As you move down the tree, the values increase. Arr [Parent of i]