Data Structures Notes PDF - B.Tech (CSE)

Data Structures B.Tech (CSE) Notes Prepared By:  Topperworld.in Unit-1 Basic Concepts: Introduction to Data Structures: A data structure is a way of...

Data Structures B.Tech (CSE) Notes Prepared By:  Topperworld.in Unit-1 Basic Concepts: Introduction to Data Structures: A data structure is a way of storing data in a computer so that it can be used efficiently and it will allow the most efficient algorithm to be used. The choice of the data structure begins from the choice of an abstract data type (ADT). A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structure introduction refers to a scheme for organizing data, or in other words it is an arrangement of data in computer's memory in such a way that it could make the data quickly available to the processor for required calculations. A data structure should be seen as a logical concept that must address two fundamental concerns. 1. First, how the data will be stored, and 2. Second, what operations will be performed on it. As data structure is a scheme for data organization so the functional definition of a data structure should be independent of its implementation. The functional definition of a data structure is known as ADT (Abstract Data Type) which is independent of implementation. The way in which the data is organized affects the performance of a program for different tasks. Computer programmers decide which data structures to use based on the nature of the data and the processes that need to be performed on that data. Some of the more commonly used data structures include lists, arrays, stacks, queues, heaps, trees, and graphs. Classification of Data Structures: Data structures can be classified as Simple data structure Compound data structure Linear data structure Non linear data structure [Fig 1.1 Classification of Data Structures] Simple Data Structure: 1  Topperworld.in Simple data structure can be constructed with the help of primitive data structure. A primitive data structure used to represent the standard data types of any one of the computer languages. Variables, arrays, pointers, structures, unions, etc. are examples of primitive data structures. Compound Data structure: Compound data structure can be constructed with the help of any one of the primitive data structure and it is having a specific functionality. It can be designed by user. It can be classified as Linear data structure Non-linear data structure Linear Data Structure: Linear data structures can be constructed as a continuous arrangement of data elements in the memory. It can be constructed by using array data type. In the linear Data Structures the relationship of adjacency is maintained between the data elements. Operations applied on linear data structure: The following list of operations applied on linear data structures 1. Add an element 2. Delete an element 3. Traverse 4. Sort the list of elements 5. Search for a data element For example Stack, Queue, Tables, List, and Linked Lists. Non-linear Data Structure: Non-linear data structure can be constructed as a collection of randomly distributed set of data item joined together by using a special pointer (tag). In non-linear Data structure the relationship of adjacency is not maintained between the data items. Operations applied on non-linear data structures: The following list of operations applied on non-linear data structures. 1. Add elements 2. Delete elements 3. Display the elements 4. Sort the list of elements 5. Search for a data element For example Tree, Decision tree, Graph and Forest Abstract Data Type: An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the data and the operations that are allowed without regard to how they will be implemented. This means that we are concerned only with what data is representing and not with how it will eventually be constructed. By providing this level of abstraction, we are creating an encapsulation around the data. The idea is that by encapsulating the details of the implementation, we are hiding them from the user’s view. This is called information hiding. The implementation of an abstract data type, often referred to as a data structure, will require that we provide a physical view of the data using some collection of programming constructs and primitive data types. 2  Topperworld.in [Fig. 1.2: Abstract Data Type (ADT)] Real life applications of different data structures with exmaples: Stack Data Structure to Reverse a String: A stack is a linear data structure, "linear" meaning the elements are placed one after the other. An element can be accessed only after accessing the previous elements. A stack is a data structure that uses LIFO (Last In First Out) order. We can visualize a stack like a pile of plates placed on top of each other. Each plate below the topmost plate cannot be directly accessed until the plates above are removed. Plates can be added and removed from the top only. Each plate is an element and the pile is the stack. In the programming terms, each plate is a variable and the pile is a data structure. WHY A PROGRAMMER NEED STACK REPRESENTATION? 3  Topperworld.in You might be wondering why a programmer needs to learn how to put a plate on a pile and take the plete out from the pile.Let’s understand it. You are assigned a task of reversing a string. How would you do it? Start selecting a character from the string and copy it into the new location one by one. 4  Topperworld.in Now, let us copy these items from the top into the original location. 5  Topperworld.in 6  Topperworld.in we have successfully reversed a string using the property of stack (the new memory). Inserting and removing was only allowed from the top. This way stack is used in programming. Queue Data Structure while Boarding a Bus: A Queue is also a linear data structure in which the elements are arranged based on FIFO (First In First Out) rule. It is like the passengers standing in a queue to board a bus. The person who first gets into the queue is the one who first gets on the bus. The new passengers can join the queue from the back whereas passengers get on the bus from the front. 7  Topperworld.in Why do we need a Queue representation? You may ask where a queue is used on a computer. Assume that you are in your office and there is a network of five computers. You have connected all these computers to a single printer. Suppose an employee wants to print his documents and sends a command to the printer through his computer. The printer receives the commands and starts printing the documents. At the same time, another employee sends commands to the printer. The printer puts the second command to the queue. The second command is executed only after the execution of the first command. This follows the FIFO rule. Graph Data Structure in Social Media and Google Map: A Graph is a network of interconnected items. Each item is known as a node and the connection between them is known as the edge. You probably use social media like Facebook, LinkedIn, Instagram, and so on. Social media is a great example of a graph being used. Social media uses graphs to store information about each user. Here, every user is a node just like in Graph. And, if one user, let's call him Jack, becomes friends with another user, Rose, then there exists an edge (connection) between Jack and Rose. Likewise, the more we are connected with people, the nodes and edges of the graph keep on increasing. 8  Topperworld.in Similarly, Google Map is another example where Graphs are used. In the case of the Google Map, every location is considered as nodes, and roads between locations are considered as edges. And, when one has to move from one location to another, the Google Map uses various Graph-based algorithms to find the shortest path. We will discuss this later in this blog. Application of Linked Lists: A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: 9  Topperworld.in Some of its applications are: 1. Web pages can be accessed using the previous and the next URL links which are linked using a linked list. 2. The music players also use the same technique to switch between music. 3. To keep the track of turns in a multi-player game, a circular linked list is used. 4. Escalators — Circular linked List. Application of Tree: Trees are hierarchical structures having a single root node. 1. The decision-based algorithm is used in machine learning which works upon the algorithm of the tree. 2. Databases also use tree data structures for indexing. 3. Domain Name Server(DNS) also uses tree structures. 4. BST used in computer Graphics Applications of Arrays: An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number. 10  Topperworld.in Some other applications of the arrays are: 1. Arrangement of the leader-board of a game can be done simply through arrays to store the score and arrange them in descending order to clearly make out the rank of each player in the game. 2. A simple question Paper is an array of numbered questions with each of them assigned some marks. 3. 2D arrays, commonly known as, matrices, are used in image processing. 4. It is also used in speech processing, in which each speech signal is an array. ARRAY: Array in C programming language is a collection of fixed size data belongings to the same data type. An array is a data structure which can store a number of variables of same data type in sequence. These similar elements could be of type int, float, double, char etc. Properties of array in C: An array is a collection of same data types. The size of array must be a constant integral value. All elements of array are stored in the contiguous memory locations. Single elements in an array can be accessed by the name of the array and an integer enclosed in square bracket called subscript/index variable like student. Array is a random access data structure. you can access any element of array in just one statement. The first element in an array is at index 0, whereas the last element is at index (size_of_array – 1). Advantage of Array : Less amount of code :Less code is used to access the data Easy access of elements :By using the for loop, we can retrieve the elements of an array easily. Easy for sorting :To sort the elements of the array, we need a few lines of code only. Random Access :We can access any element randomly using the array. Disadvantage of Array : Fixed Size : We can not exceed the the limit size of array after it’s decleration. 11  Topperworld.in Declaration of Array : We can declare an array in the c language in the below given way. data_type array_name[array_size]; Now, let us see the example to declare the array. int marks; Here, int is the data_type, marks are the array_name, and 6 is the array_size. Initialization of Array : We declare normal variables in c in the following ways : int x; x = 0; or int x = 0; In the case of an array, simply list the array values in set notation { }. Some valid array declarations are shown below. int num = {2, 4, 6, 8, 10, 12}; char letters = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}; float numbers = {9.04, 14.02, 7.3}; 12  Topperworld.in Array in C Example: #include int main(){ int i=0; int marks;//declaration of array marks=10;//initialization of array marks=30; marks=40; marks=65; marks=55; marks=50; //traversal of array for(i=0;i middle item, then search for the target value in the second half of the list. In binary search as the list is ordered, so we can eliminate half of the values in the list in each iteration. Consider an example, suppose we want to search 10 in a sorted array of elements, then we first determine the middle element of the array. As the middle item contains 18, which is greater than the target value 10, so can discard the second half of the list and repeat the process to first half of the array. This process is repeated until the desired target item is located in the list. If the item is found then it returns True, otherwise False. Searching for 10 in a sorted array using Binary Search Source Code: array =[1,2,3,4,5,6,7,8,9] def binary_search(searchfor,array): lowerbound=0 upperbound=len(array)-1 found=False while found==False and lowerbound 1. (15428) ( 1 4 5 2 8 ), Swap since 5 > 4 (14528) ( 1 4 2 5 8 ), Swap since 5 > 2 (14258) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: (14258) (14258) (14258) ( 1 2 4 5 8 ), Swap since 4 > 2 (12458) (12458) (12458) (12458) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: (12458) (12458) (12458) (12458) (12458) (12458) 30  Topperworld.in (12458) ( 1 2 4 5 8 ) Time Complexity: The efficiency of Bubble sort algorithm is independent of number of data items in the array and its initial arrangement. If an array containing n data items, then the outer loop executes n-1 times as the algorithm requires n-1 passes. In the first pass, the inner loop is executed n-1 times; in the second pass, n-2 times; in the third pass, n-3 times and so on. The total number of iterations resulting in a run time of O(n2). Worst Case Performance O(n2) Best Case Performance O(n2) Average Case Performance O(n2) Selection Sort: Selection sort algorithm is one of the simplest sorting algorithm, which sorts the elements in an array by finding the minimum element in each pass from unsorted part and keeps it in the beginning. This sorting technique improves over bubble sort by making only one exchange in each pass. This sorting technique maintains two sub arrays, one sub array which is already sorted and the other one which is unsorted. In each iteration the minimum element (ascending order) is picked from unsorted array and moved to sorted sub array.. Selection Sort Algorithm: Source Code: # Python program for implementation of Selection # Sort import sys A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)): 31  Topperworld.in # Find the minimum element in remaining # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx] > A[j]: min_idx = j # Swap the found minimum element with # the first element A[i], A[min_idx] = A[min_idx], A[i] # Driver code to test above print ("Sorted array") for i in range(len(A)): print("%d" %A[i]) Output: Enter array size:6 Enter the elements:96 94 81 56 76 45 The elements after sorting are: 45 56 76 81 94 96 Step-by-step example: Here is an example of this sort algorithm sorting five elements: 64 25 12 22 11 11 25 12 22 64 11 12 25 22 64 11 12 22 25 64 11 12 22 25 64 Time Complexity: Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) +... + 2 + 1 = n(n − 1) / 2 O(n2) comparisons. Each of these scans requires one swap for n − 1 elements (the final element is already in place). Worst Case Performance O(n2) Best Case Performance O(n2) Average Case Performance O(n2) 32  Topperworld.in Insertion Sort: An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm. It builds the sorted sequence one number at a time. This is a suitable sorting technique in playing card games. Insertion sort provides several advantages: Simple implementation Efficient for (quite) small data sets Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n) Stable; i.e., does not change the relative order of elements with equal keys In-place; i.e., only requires a constant amount O(1) of additional memory space Online; i.e., can sort a list as it receives it Source Code: # Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] 33  Topperworld.in # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j >=0 and key < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) print ("Sorted array is:") for i in range(len(arr)): print ("%d" %arr[i]) Step-by-step example: Suppose, you want to sort elements in ascending as in above figure. Then, 34  Topperworld.in 1. The second element of an array is compared with the elements that appear before it (only first element in this case). If the second element is smaller than first element, second element is inserted in the position of first element. After first step, first two elements of an array will be sorted. 2. The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it is inserted in the position of first element. If third element is larger than first element but, smaller than second element, it is inserted in the position of second element. If third element is larger than both the elements, it is kept in the position as it is. After second step, first three elements of an array will be sorted. 3. Similarly, the fourth element of an array is compared with the elements that appear before it (first, second and third element) and the same procedure is applied and that element is inserted in the proper position. After third step, first four elements of an array will be sorted. If there are n elements to be sorted. Then, this procedure is repeated n-1 times to get sorted list of array. Time Complexity: Worst Case Performance O(n2) Best Case Performance(nearly) O(n) Average Case Performance O(n2) Output: Enter no of elements:5 Enter elements:1 65 0 32 66 Elements after sorting: 0 1 32 65 66 Quick Sort : Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sublists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists. The steps are: 1. Pick an element, called a pivot, from the list. 2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. 3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values. The base case of the recursion is lists of size zero or one, which never need to be sorted. Quick sort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quick sort is often faster in practice than other O(n log n) algorithms. It works by first of 35  Topperworld.in all by partitioning the array around a pivot value and then dealing with the 2 smaller partitions separately. Partitioning is the most complex part of quick sort. The simplest thing is to use the first value in the array, a[l] (or a as l = 0 to begin with) as the pivot. After the partitioning, all values to the left of the pivot are pivot. The same procedure for the two remaining sub lists is repeated and so on recursively until we have the entire list sorted. Advantages: One of the fastest algorithms on average. Does not need additional memory (the sorting takes place in the array - this is called in-place processing). Disadvantages: The worst-case complexity is O(N2) Source Code: # Python program for implementation of Quicksort Sort # This function takes last element as pivot, places # the pivot element at its correct position in sorted # array, and places all smaller (smaller than pivot) # to left of pivot and all greater elements to right # of pivot def partition(arr,low,high): i = ( low-1 ) # index of smaller element pivot = arr[high] # pivot for j in range(low , high): # If current element is smaller than or # equal to pivot if arr[j] Array to be sorted, # low --> Starting index, # high --> Ending index # Function to do Quick sort def quickSort(arr,low,high): if low < high: 36  Topperworld.in # pi is partitioning index, arr[p] is now # at right place pi = partition(arr,low,high) # Separately sort elements before # partition and after partition quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) # Driver code to test above arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr,0,n- 1) print ("Sorted array is:") for i in range(n): print ("%d" %arr[i]) Step-by-step example: 1 2 3 4 5 6 7 8 9 10 11 12 13 Remarks 38 08 16 06 79 57 24 56 02 58 04 70 45 Pivot 08 16 06 Up 57 24 56 02 58 Dn 70 45 Swap up and down Pivot 08 16 06 04 57 24 56 02 58 79 70 45 Pivot 08 16 06 04 Up 24 56 Dn 58 79 70 45 Swap up and down Pivot 08 16 06 04 02 24 56 57 58 79 70 45 Pivot 08 16 06 04 02 Dn Up 57 58 79 70 45 Swap pivot and down 24 08 16 06 04 02 38 56 57 58 79 70 45 Pivot 08 16 06 04 Dn Up 56 57 58 79 70 45 Swap pivot and down (02 08 16 06 04 24) 38 (56 57 58 79 70 45) Pivot 08 16 06 04 Up dn Pivot Up 06 Dn Swap up and down Pivot 04 06 16 Pivot 04 Dn Up Swap pivot 37  Topperworld.in and down 06 04 08 Pivot Dn Up Swap pivot and down 04 06 (02 04 06 08 16 24 38) (56 57 58 79 70 45) Pivot Up 58 79 70 Dn Swap up and down Pivot 45 58 79 70 57 Pivot Dn Up 79 70 57 Swap pivot and down (45) 56 (58 79 70 57) Pivot Up 70 Dn Swap up and down Pivot 57 70 79 Pivot Dn Up 79 Swap down and pivot (57) 58 (70 79) Pivot Up Swap pivot and down Dn 02 04 06 08 16 24 38 45 56 57 58 70 79 The array is sorted Time Complexity: Worst Case Performance O(n2) Best Case Performance(nearly) O(n log2 n) Average Case Performance O(n log2 n) Merge Sort: Merge sort is based on Divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two 38  Topperworld.in unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is already sorted. The two lists of size 1 are then merged. Merge Sort Procedure: This is a divide and conquer algorithm. This works as follows : 1. Divide the input which we have to sort into two parts in the middle. Call it the left part and right part. 2. Sort each of them separately. Note that here sort does not mean to sort it using some other method. We use the same function recursively. 3. Then merge the two sorted parts. Input the total number of elements that are there in an array (number_of_elements). Input the array (array[number_of_elements]). Then call the function MergeSort() to sort the input array. MergeSort() function sorts the array in the range [left,right] i.e. from index left to index right inclusive. Merge() function merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right]. After merging output the sorted array. MergeSort() function: It takes the array, left-most and right-most index of the array to be sorted as arguments. Middle index (mid) of the array is calculated as (left + right)/2. Check if (left (greater) than the key in its parent node 4. Duplicate node keys are not allowed. Inserting a node A naïve algorithm for inserting a node into a BST is that, we start from the root node, if the node to insert is less than the root, we go to left child, and otherwise we go to the right child of the root. We continue this process (each node is a root for some sub tree) until we find a null pointer (or leaf node) where we cannot go any further. We then insert the node as a left or right child of the leaf node based on node is less or greater than the leaf node. We note that a new node is always inserted as a leaf node. A recursive algorithm for inserting a node into a BST is as follows. Assume we insert a node N to tree T. if the tree is empty, the we return new node N as the tree. Otherwise, the problem of inserting is reduced to inserting the node N to left of right sub trees of T, depending on N is less or greater than T. A definition is as follows. Insert(N, T) = N if T is empty = insert(N, T.left) if N < T = insert(N, T.right) if N > T Searching for a node Searching for a node is similar to inserting a node. We start from root, and then go left or right until we find (or not find the node). A recursive definition of search is as follows. If the node is equal to root, then we return true. If the root is null, then we return false. Otherwise we recursively solve the problem for T.left or T.right, depending on N < T or N > T. A recursive definition is as follows. Search should return a true or false, depending on the node is found or not. Search(N, T) = false if T is empty 117  Topperworld.in = true if T = N = search(N, T.left) if N < T = search(N, T.right) if N > T Deleting a node A BST is a connected structure. That is, all nodes in a tree are connected to some other node. For example, each node has a parent, unless node is the root. Therefore deleting a node could affect all sub trees of that node. For example, deleting node 5 from the tree could result in losing sub trees that are rooted at 1 and 9. Hence we need to be careful about deleting nodes from a tree. The best way to deal with deletion seems to be considering special cases. What if the node to delete is a leaf node? What if the node is a node with just one child? What if the node is an internal node (with two children). The latter case is the hardest to resolve. But we will find a way to handle this situation as well. Case 1 : The node to delete is a leaf node This is a very easy case. Just delete the node 46. We are done Case 2 : The node to delete is a node with one child. This is also not too bad. If the node to be deleted is a left child of the parent, then we connect the left pointer of the parent (of the deleted node) to the single child. Otherwise if the node to be deleted is a right child of the parent, then we connect the right pointer of the parent (of the deleted node) to single child. 118  Topperworld.in Case 3: The node to delete is a node with two children This is a difficult case as we need to deal with two sub trees. But we find an easy way to handle it. First we find a replacement node (from leaf node or nodes with one child) for the node to be deleted. We need to do this while maintaining the BST order property. Then we swap leaf node or node with one child with the node to be deleted (swap the data) and delete the leaf node or node with one child (case 1 or case 2) Next problem is finding a replacement leaf node for the node to be deleted. We can easily find this as follows. If the node to be deleted is N, the find the largest node in the left sub tree of N or the smallest node in the right sub tree of N. These are two candidates that can replace the node to be deleted without losing the order property. For example, consider the following tree and suppose we need to delete the root 38. Then we find the largest node in the left sub tree (15) or smallest node in the right sub tree (45) and replace the root with that node and then delete that node. The following set of images demonstrates this process. Let’s see when we delete 13 from that tree. 119  Topperworld.in 120  Topperworld.in Balanced Search Trees: A self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. The red–black tree, which is a type of self-balancing binary search tree, was called symmetric binary B-tree. Self-balancing binary search trees can be used in a natural way to construct and maintain ordered lists, such as priority queues. They can also be used for associative arrays; key-value pairs are simply inserted with an ordering based on the key alone. In this capacity, self-balancing BSTs have a number of advantages and disadvantages over their main competitor, hash tables. One advantage of self-balancing BSTs is that they allow fast (indeed, asymptotically optimal) enumeration of the items in key order, which hash tables do not provide. One disadvantage is that their lookup algorithms get more complicated when there may be multiple items with the same key. Self-balancing BSTs have better worst-case lookup performance than hash tables (O(log n) compared to O(n)), but have worse average-case performance (O(log n) compared to O(1)). Self-balancing BSTs can be used to implement any algorithm that requires mutable ordered lists, to achieve optimal worst-case asymptotic performance. For example, if binary tree sort is implemented with a self-balanced BST, we have a very simple-to-describe yet asymptotically optimal O(n log n) sorting algorithm. Similarly, many algorithms in computational geometry exploit variations on self-balancing BSTs to solve problems such as the line segment intersection problem and the point location problem efficiently. (For average-case performance, however, self- balanced BSTs may be less efficient than other solutions. Binary tree sort, in particular, is likely to be slower than merge sort, quicksort, or heapsort, because of the tree-balancing overhead as well as cache access patterns.) Self-balancing BSTs are flexible data structures, in that it's easy to extend them to efficiently record additional information or perform new operations. For example, one can record the number of nodes in each subtree having a certain property, allowing one to count the number of nodes in a certain key range with that property in O(log n) time. These extensions can be used, for example, to optimize database queries or other list-processing algorithms. AVL Trees: An AVL tree is another balanced binary search tree. Named after their inventors, AdelsonVelskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time. Definition of an AVL tree: An AVL tree is a binary search tree which has the following properties: 1. The sub-trees of every node differ in height by at most one. 2. Every sub-tree is an AVL tree. 121  Topperworld.in Balance requirement for an AVL tree: the left and right sub-trees differ by at most 1 in height. For example, here are some trees: Yes this is an AVL tree. Examination shows that each left sub-tree has a height 1 greater than each right sub-tree. No this is not an AVL tree. Sub-tree with root 8 has height 4 and sub-tree with root 18 has height 2. 122  Topperworld.in An AVL tree implements the Map abstract data type just like a regular binary search tree, the only difference is in how the tree performs. To implement our AVL tree we need to keep track of a balance factor for each node in the tree. We do this by looking at the heights of the left and right subtrees for each node. More formally, we define the balance factor for a node as the difference between the height of the left subtree and the height of the right subtree. balanceFactor=height(leftSubTree)−height(rightSubTree) Using the definition for balance factor given above we say that a subtree is left-heavy if the balance factor is greater than zero. If the balance factor is less than zero then the subtree is right heavy. If the balance factor is zero then the tree is perfectly in balance. For purposes of implementing an AVL tree, and gaining the benefit of having a balanced tree we will define a tree to be in balance if the balance factor is -1, 0, or 1. Once the balance factor of a node in a tree is outside this range we will need to have a procedure to bring the tree back into balance. Figure shows an example of an unbalanced, right-heavy tree and the balance factors of each node. Properties of AVL Trees AVL trees are identical to standard binary search trees except that for every node in an AVL tree, the height of the left and right subtrees can differ by at most 1 (Weiss, 1993, p:108). AVL trees are HB-k trees (height balanced trees of order k) of order HB-1. The following is the height differential formula: When storing an AVL tree, a field must be added to each node with one of three values: 1, 0, or - 1. A value of 1 in this field means that the left subtree has a height one more than the right subtree. A value of -1 denotes the opposite. A value of 0 indicates that the heights of both subtrees are the same. Updates of AVL trees require up to rotations, whereas updating red-black trees can be done 123  Topperworld.in using only one or two rotations (up to color changes). For this reason, they (AVL trees) are considered a bit obsolete by some. Sparse AVL trees Sparse AVL trees are defined as AVL trees of height h with the fewest possible nodes. Figure 3 shows sparse AVL trees of heights 0, 1, 2, and 3. Figure Structure of an AVL tree Introduction to M-Way Search Trees: A multiway tree is a tree that can have more than two children. A multiway tree of order m (or an m-way tree) is one in which a tree can have m children. As with the other trees that have been studied, the nodes in an m-way tree will be made up of key fields, in this case m-1 key fields, and pointers to children. Multiday tree of order 5 To make the processing of m-way trees easier some type of order will be imposed on the keys within each node, resulting in a multiway search tree of order m (or an m-way search tree). By definition an m-way search tree is a m-way tree in which: Each node has m children and m-1 key fields The keys in each node are in ascending order. 124  Topperworld.in The keys in the first i children are smaller than the ith key The keys in the last m-i children are larger than the ith key 4-way search tree M-way search trees give the same advantages to m-way trees that binary search trees gave to binary trees - they provide fast information retrieval and update. However, they also have the same problems that binary search trees had - they can become unbalanced, which means that the construction of the tree becomes of vital importance. B Trees: An extension of a multiway search tree of order m is a B-tree of order m. This type of tree will be used when the data to be accessed/stored is located on secondary storage devices because they allow for large amounts of data to be stored in a node. A B-tree of order m is a multiway search tree in which: 1. The root has at least two subtrees unless it is the only node in the tree. 2. Each nonroot and each nonleaf node have at most m nonempty children and at least m/2 nonempty children. 3. The number of keys in each nonroot and each nonleaf node is one less than the number of its nonempty children. 4. All leaves are on the same level. These restrictions make B-trees always at least half full, have few levels, and remain perfectly balanced. Searching a B-tree An algorithm for finding a key in B-tree is simple. Start at the root and determine which pointer to follow based on a comparison between the search value and key fields in the root node. Follow the appropriate pointer to a child node. Examine the key fields in the child node and continue to follow 125  Topperworld.in the appropriate pointers until the search value is found or a leaf node is reached that doesn't contain the desired search value. Insertion into a B-tree The condition that all leaves must be on the same level forces a characteristic behavior of Btrees, namely that B-trees are not allowed to grow at the their leaves; instead they are forced to grow at the root. When inserting into a B-tree, a value is inserted directly into a leaf. This leads to three common situations that can occur: 1. A key is placed into a leaf that still has room. 2. The leaf in which a key is to be placed is full. 3. The root of the B-tree is full. Case 1: A key is placed into a leaf that still has room This is the easiest of the cases to solve because the value is simply inserted into the correct sorted position in the leaf node. Inserting the number 7 results in: Case 2: The leaf in which a key is to be placed is full In this case, the leaf node where the value should be inserted is split in two, resulting in a new leaf node. Half of the keys will be moved from the full leaf to the new leaf. The new leaf is then incorporated into the B-tree. The new leaf is incorporated by moving the middle value to the parent and a pointer to the new leaf is also added to the parent. This process is continues up the tree until all of the values have "found" a location. 126  Topperworld.in Insert 6 into the following B-tree: results in a split of the first leaf node: The new node needs to be incorporated into the tree - this is accomplished by taking the middle value and inserting it in the parent: Case 3: The root of the B-tree is full The upward movement of values from case 2 means that it's possible that a value could move up to the root of the B-tree. If the root is full, the same basic process from case 2 will be applied and a new root will be created. This type of split results in 2 new nodes being added to the B-tree. Inserting 13 into the following tree: 127  Topperworld.in Results in: The 15 needs to be moved to the root node but it is full. This means that the root needs to be divided: The 15 is inserted into the parent, which means that it becomes the new root node: Deleting from a B-tree As usual, this is the hardest of the processes to apply. The deletion process will basically be a reversal of the insertion process - rather than splitting nodes, it's possible that nodes will be merged 128  Topperworld.in so that B-tree properties, namely the requirement that a node must be at least half full, can be maintained. There are two main cases to be considered: 1. Deletion from a leaf 2. Deletion from a non-leaf Case 1: Deletion from a leaf 1a) If the leaf is at least half full after deleting the desired value, the remaining larger values are moved to "fill the gap". Deleting 6 from the following tree: results in: 1b) If the leaf is less than half full after deleting the desired value (known as underflow), two things could happen: Deleting 7 from the tree above results in: 129  Topperworld.in 1b-1) If there is a left or right sibling with the number of keys exceeding the minimum requirement, all of the keys from the leaf and sibling will be redistributed between them by moving the separator key from the parent to the leaf and moving the middle key from the node and the sibling combined to the parent. Now delete 8 from the tree: 1b-2) If the number of keys in the sibling does not exceed the minimum requirement, then the leaf and sibling are merged by putting the keys from the leaf, the sibling, and the separator from the parent into the leaf. The sibling node is discarded and the keys in the parent are moved to "fill the gap". It's possible that this will cause the parent to underflow. If that is the case, treat the parent as a leaf and continue repeating step 1b-2 until the minimum requirement is met or the root of the tree is reached. Special Case for 1b-2: When merging nodes, if the parent is the root with only one key, the keys from the node, the sibling, and the only key of the root are placed into a node and this will become the new root for the B-tree. Both the sibling and the old root will be discarded. 130  Topperworld.in Case 2: Deletion from a non-leaf This case can lead to problems with tree reorganization but it will be solved in a manner similar to deletion from a binary search tree. The key to be deleted will be replaced by its immediate predecessor (or successor) and then the predecessor (or successor) will be deleted since it can only be found in a leaf node. Deleting 16 from the tree above results in: The "gap" is filled in with the immediate predecessor: 131  Topperworld.in and then the immediate predecessor is deleted: If the immediate successor had been chosen as the replacement: Deleting the successor results in: The vales in the left sibling are combined with the separator key (18) and the remaining values. They are divided between the 2 nodes: 132  Topperworld.in and then the middle value is moved to the parent: Hashing and Collision: Hashing is the technique used for performing almost constant time search in case of insertion, deletion and find operation. Taking a very simple example of it, an array with its index as key is the example of hash table. So each index (key) can be used for accessing the value in a constant search time. This mapping key must be simple to compute and must helping in identifying the associated value. Function which helps us in generating such kind of key-value mapping is known as Hash Function. In a hashing system the keys are stored in an array which is called the Hash Table. A perfectly implemented hash table would always promise an average insert/delete/retrieval time of O(1). Hashing Function: A function which employs some algorithm to computes the key K for all the data elements in the set U, such that the key K which is of a fixed size. The same key K can be used to map data to a hash table and all the operations like insertion, deletion and searching should be possible. The values returned by a hash function are also referred to as hash values, hash codes, hash sums, or hashes. 133  Topperworld.in Hash Collision: A situation when the resultant hashes for two or more data elements in the data set U, maps to the same location in the has table, is called a hash collision. In such a situation two or more data elements would qualify to be stored / mapped to the same location in the hash table. Hash collision resolution techniques: Open Hashing (Separate chaining): Open Hashing, is a technique in which the data is not directly stored at the hash key index (k) of the Hash table. Rather the data at the key index (k) in the hash table is a pointer to the head of the data structure where the data is actually stored. In the most simple and common implementations the data structure adopted for storing the element is a linked-list. n this technique when a data needs to be searched, it might become necessary (worst case) to traverse all the nodes in the linked list to retrieve the data. Note that the order in which the data is stored in each of these linked lists (or other data structures) is completely based on implementation requirements. Some of the popular criteria are insertion order, frequency of access etc. Closed hashing (open Addressing) In this technique a hash table with pre-identified size is considered. All items are stored in the hash table itself. In addition to the data, each hash bucket also maintains the three states: EMPTY, OCCUPIED, DELETED. While inserting, if a collision occurs, alternative cells are tried until an empty bucket is found. For which one of the following technique is adopted. 134  Topperworld.in 1. Liner Probing 2. Quadratic probing 3. Double hashing (in short in case of collision another hashing function is used with the key value as an input to identify where in the open addressing scheme the data should actually be stored.) A comparative analysis of Closed Hashing vs Open Hashing Open Addressing Closed Addressing All elements would be Additional Data structure stored in the Hash table needs to be used to itself. No additional data accommodate collision structure is needed. data. Simple and effective In cases of collisions, a approach to collision unique hash key must be resolution. Key may or may obtained. not be unique. Determining size of the Performance deterioration hash table, adequate enough of closed addressing much for storing all the data is slower as compared to difficult. Open addressing. State needs be maintained No state data needs to be for the data (additional maintained (easier to work) maintain) Uses space efficiently Expensive on space Applications of Hashing: A hash function maps a variable length input string to fixed length output string -- its hash value, or hash for short. If the input is longer than the output, then some inputs must map to the same output -- a hash collision. Comparing the hash values for two inputs can give us one of two answers: the inputs are definitely not the same, or there is a possibility that they are the same. Hashing as we know it is used for performance improvement, error checking, and authentication. One example of a performance improvement is the common hash table, which uses a hash function to index into the correct bucket in the hash table, followed by comparing each element in the bucket to find a match. In error checking, hashes (checksums, message digests, etc.) are used to detect errors caused by either hardware or software. Examples are TCP checksums, ECC memory, and MD5 checksums on downloaded files. In this case, the hash provides additional assurance that the data we received is correct. Finally, hashes are used to authenticate messages. In this case, we are trying to protect the original input from tampering, and we select a hash that is strong enough to make malicious attack infeasible or unprofitable. Construct a message authentication code (MAC) Digital signature Make commitments, but reveal message later Timestamping 135  Topperworld.in Key updating: key is hashed at specific intervals resulting in new key 136