fundamental of data structures.pdf

Introduction to Data Structure Introduction to Data Structure  Computer is an electronic machine which is used for data processing and manipulation.  When programmer collects such type of data for processing, he would require...

Introduction to Data Structure Introduction to Data Structure  Computer is an electronic machine which is used for data processing and manipulation.  When programmer collects such type of data for processing, he would require to store all of them in computer’s main memory.  In order to make computer work we need to know o Representation of data in computer. o Accessing of data. o How to solve problem step by step.  For doing this task we use data structure. What is Data Structure?  Data structure is a representation of the logical relationship existing between individual elements of data.  Data Structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.  We can also define data structure as a mathematical or logical model of a particular organization of data items.  The representation of particular data structure in the main memory of a computer is called as storage structure.  The storage structure representation in auxiliary memory is called as file structure.  It is defined as the way of storing and manipulating data in organized form so that it can be used efficiently.  Data Structure mainly specifies the following four things o Organization of Data o Accessing methods o Degree of associativity o Processing alternatives for information  Algorithm + Data Structure = Program  Data structure study covers the following points o Amount of memory require to store. o Amount of time require to process. o Representation of data in memory. o Operations performed on that data. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 1  Introduction to Data Structure Classification of Data Structure DATA STRUCTURE PRIMITIVE NON PRIMITIVE INTEGER FLOATING CHARACTER POINTER ARRAY LIST FILE POINT LINEAR LIST NON LINEAR LIST STACK QUEUE GRAPH TREE Data Structures are normally classified into two broad categories 1. Primitive Data Structure 2. Non-primitive data Structure Data types A particular kind of data item, as defined by the values it can take, the programming language used, or the operations that can be performed on it. Primitive Data Structure  Primitive data structures are basic structures and are directly operated upon by machine instructions.  Primitive data structures have different representations on different computers.  Integers, floats, character and pointers are examples of primitive data structures.  These data types are available in most programming languages as built in type. o Integer: It is a data type which allows all values without fraction part. We can use it for whole numbers. o Float: It is a data type which use for storing fractional numbers. o Character: It is a data type which is used for character values. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 2  Introduction to Data Structure Pointer: A variable that holds memory address of another variable are called pointer. Non primitive Data Type  These are more sophisticated data structures.  These are derived from primitive data structures.  The non-primitive data structures emphasize on structuring of a group of homogeneous or heterogeneous data items.  Examples of Non-primitive data type are Array, List, and File etc.  A Non-primitive data type is further divided into Linear and Non-Linear data structure o Array: An array is a fixed-size sequenced collection of elements of the same data type. o List: An ordered set containing variable number of elements is called as Lists. o File: A file is a collection of logically related information. It can be viewed as a large list of records consisting of various fields. Linear data structures  A data structure is said to be Linear, if its elements are connected in linear fashion by means of logically or in sequence memory locations.  There are two ways to represent a linear data structure in memory, o Static memory allocation o Dynamic memory allocation  The possible operations on the linear data structure are: Traversal, Insertion, Deletion, Searching, Sorting and Merging.  Examples of Linear Data Structure are Stack and Queue.  Stack: Stack is a data structure in which insertion and deletion operations are performed at one end only. o The insertion operation is referred to as ‘PUSH’ and deletion operation is referred to as ‘POP’ operation. o Stack is also called as Last in First out (LIFO) data structure.  Queue: The data structure which permits the insertion at one end and Deletion at another end, known as Queue. o End at which deletion is occurs is known as FRONT end and another end at which insertion occurs is known as REAR end. o Queue is also called as First in First out (FIFO) data structure. Nonlinear data structures  Nonlinear data structures are those data structure in which data items are not arranged in a sequence.  Examples of Non-linear Data Structure are Tree and Graph.  Tree: A tree can be defined as finite set of data items (nodes) in which data items are arranged in branches and sub branches according to requirement. o Trees represent the hierarchical relationship between various elements. o Tree consist of nodes connected by edge, the node represented by circle and edge lives connecting to circle. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 3  Introduction to Data Structure  Graph: Graph is a collection of nodes (Information) and connecting edges (Logical relation) between nodes. o A tree can be viewed as restricted graph. o Graphs have many types:  Un-directed Graph  Directed Graph  Mixed Graph  Multi Graph  Simple Graph  Null Graph  Weighted Graph Difference between Linear and Non Linear Data Structure Linear Data Structure Non-Linear Data Structure Every item is related to its previous and next time. Every item is attached with many other items. Data is arranged in linear sequence. Data is not arranged in sequence. Data items can be traversed in a single run. Data cannot be traversed in a single run. Eg. Array, Stacks, linked list, queue. Eg. tree, graph. Implementation is easy. Implementation is difficult. Operation on Data Structures Design of efficient data structure must take operations to be performed on the data structures into account. The most commonly used operations on data structure are broadly categorized into following types 1. Create The create operation results in reserving memory for program elements. This can be done by declaration statement. Creation of data structure may take place either during compile-time or run-time. malloc() function of C language is used for creation. 2. Destroy Destroy operation destroys memory space allocated for specified data structure. free() function of C language is used to destroy data structure. 3. Selection Selection operation deals with accessing a particular data within a data structure. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 4  Introduction to Data Structure 4. Updation It updates or modifies the data in the data structure. 5. Searching It finds the presence of desired data item in the list of data items, it may also find the locations of all elements that satisfy certain conditions. 6. Sorting Sorting is a process of arranging all data items in a data structure in a particular order, say for example, either in ascending order or in descending order. 7. Merging Merging is a process of combining the data items of two different sorted list into a single sorted list. 8. Splitting Splitting is a process of partitioning single list to multiple list. 9. Traversal Traversal is a process of visiting each and every node of a list in systematic manner. Time and space analysis of algorithms Algorithm  An essential aspect to data structures is algorithms.  Data structures are implemented using algorithms.  An algorithm is a procedure that you can write as a C function or program, or any other language.  An algorithm states explicitly how the data will be manipulated. Algorithm Efficiency  Some algorithms are more efficient than others. We would prefer to choose an efficient algorithm, so it would be nice to have metrics for comparing algorithm efficiency.  The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the amount of data the algorithm must process.  Usually there are natural units for the domain and range of this function. There are two main complexity measures of the efficiency of an algorithm  Time complexity Time Complexity is a function describing the amount of time an algorithm takes in terms of the amount of input to the algorithm. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 5  Introduction to Data Structure "Time" can mean the number of memory accesses performed, the number of comparisons between integers, the number of times some inner loop is executed, or some other natural unit related to the amount of real time the algorithm will take.  Space complexity Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm. We often speak of "extra" memory needed, not counting the memory needed to store the input itself. Again, we use natural (but fixed-length) units to measure this. We can use bytes, but it's easier to use, say, number of integers used, number of fixed-sized structures, etc. In the end, the function we come up with will be independent of the actual number of bytes needed to represent the unit. Space complexity is sometimes ignored because the space used is minimal and/or obvious, but sometimes it becomes as important an issue as time. Worst Case Analysis In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched is not present in the array. When x is not present, the search () functions compares it with all the elements of array [] one by one. Therefore, the worst case time complexity of linear search would be. Average Case Analysis In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed. So we sum all the cases and divide the sum by (n+1). Best Case Analysis In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in worst case is constant (not dependent on n). So time complexity in the best case would be. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 6  Linear Data Structure Explain Array in detail One Dimensional Array  Simplest data structure that makes use of computed address to locate its elements is the one- dimensional array or vector; number of memory locations is sequentially allocated to the vector.  A vector size is fixed and therefore requires a fixed number of memory locations.  Vector A with subscript lower bound of “one” is represented as below…. L0  L0 is the address of the first word allocated to the first element of vector A.  C words are allocated for each element or node  The address of Ai is given equation Loc (Ai) = L0 + C (i-1) L0 + (i-1)C A [i]  Let’s consider the more general case of representing a vector A whose lower bound for it’s subscript is given by some variable b. The location of Ai is then given by Loc (Ai) = L0 + C (i-b)  Two Dimensional Array  Two dimensional arrays are also called table or matrix, two dimensional arrays have two subscripts  Two dimensional array in which elements are stored column by column is called as column major matrix  Two dimensional array in which elements are stored row by row is called as row major matrix  First subscript denotes number of rows and second subscript denotes the number of columns  Two dimensional array consisting of two rows and four columns as above Fig is stored sequentially by columns : A [ 1, 1 ], A [ 2 , 1 ], A [ 1 , 2 ], A [ 2 , 2 ], A [ 1 , 3 ], A [ 2 , 3 ], A [ 1, 4 ], A [ 2, 4 ]  The address of element A [ i , j ] can be obtained by expression Loc (A [ i , j ]) = L0 + (j-1)*2 + i-1  In general for two dimensional array consisting of n rows and m columns the address element A [ i , j ] is given by Loc (A [ i , j ]) = L0 + (j-1)*n + (i – 1)  In row major matrix, array can be generalized to arbitrary lower and upper bound in its subscripts, assume that b1 ≤ I ≤ u1 and b2 ≤ j ≤u2 b1, b2 b1, u2 [1,1][1,2] [1,3] [ 1 ,m ] col 1 col 2 col 3 col 4 [2,1][2,2] [2,3] [2m] row 1 [ 1 , 1 ] [1,2] [1,3] [1,4] row 2 [ 2 , 1 ] [2,2] [2,3] [2,4] [n,1][n,2] [n,3] [n,m] u1, b2 Row major matrix Column major matrix No of Columns = m = u2 – b2 + 1  For row major matrix : Loc (A [ i , j ]) = L0 + ( i – b1 ) *(u2-b2+1) + (j-b2) Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 1  Linear Data Structure Applications of Array 1. Symbol Manipulation (matrix representation of polynomial equation) 2. Sparse Matrix Symbol Manipulation using Array  We can use array for different kind of operations in polynomial equation such as addition, subtraction, division, differentiation etc…  We are interested in finding suitable representation for polynomial so that different operations like addition, subtraction etc… can be performed in efficient manner  Array can be used to represent Polynomial equation  Matrix Representation of Polynomial equation Y Y2 Y3 Y4 X XY X Y2 X Y3 X Y4 2 2 2 2 2 3 X X Y X Y X Y X2 Y4 X3 X3 Y X3 Y2 X3 Y3 X3 Y4 4 X X4 Y X4 Y2 X4 Y3 X4 Y4 e.g. 2x2+5xy+Y2 e.g. x2+3xy+Y2+Y-X is represented in matrix form as below is represented in matrix form as below Y Y2 Y3 Y4 Y Y2 Y3 Y4 0 0 1 0 0 0 0 1 0 0 X 0 5 0 0 0 X -1 3 0 0 0 2 2 X 2 0 0 0 0 X 1 0 0 0 0 X3 0 0 0 0 0 X3 0 0 0 0 0 4 4 X 0 0 0 0 0 X 0 0 0 0 0  Once we have algorithm for converting the polynomial equation to an array representation and another algorithm for converting array to polynomial equation, then different operations in array (matrix) will be corresponding operations of polynomial equation What is sparse matrix? Explain  An mXn matrix is said to be sparse if “many” of its elements are zero.  A matrix that is not sparse is called a dense matrix.  We can device a simple representation scheme whose space requirement equals the size of the non- zero elements. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 2  Linear Data Structure  Example:- o The non-zero entries of a sparse matrix may be mapped into a linear list in row-major order. o For example the non-zero entries of 4X8 matrix of below fig.(a) in row major order are 2, 1, 6, 7, 3, 9, 8, 4, 5 0 0 0 2 0 0 1 0 0 6 0 0 7 0 0 3 0 0 0 9 0 8 0 0 0 4 5 0 0 0 0 0 Fig (a) 4 x 8 matrix Terms 0 1 2 3 4 5 6 7 8 Row 1 1 2 2 2 3 3 4 4 Column 4 7 2 5 8 4 6 2 3 Value 2 1 6 7 3 9 8 4 5 Fig (b) Linear Representation of above matrix  To construct matrix structure we need to record (a) Original row and columns of each non zero entries (b) No of rows and columns in the matrix  So each element of the array into which the sparse matrix is mapped need to have three fields: row, column and value  A corresponding amount of time is saved creating the linear list representation over initialization of two dimension array. 0 0 6 0 9 0 0 A= 2 0 0 7 8 0 4 10 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 5  Here from 6X7=42 elements, only 10 are non zero. A[1,3]=6, A[1,5]=9, A[2,1]=2, A[2,4]=7, A[2,5]=8, A[2,7]=4, A[3,1]=10, A[4,3]=12, A[6,4]=3, A[6,7]=5.  One basic method for storing such a sparse matrix is to store non-zero elements in one dimensional array and to identify each array elements with row and column indices fig (c). ROW COLUMN A 1 1 3 6 2 1 5 9 Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 3  Linear Data Structure 3 2 1 2 4 2 4 7 5 2 5 8 6 2 7 4 7 3 1 10 8 4 3 12 9 6 4 3 10 6 7 5 Fig (c ) COLUMN A 1 3 6 ROW 2 5 9 1 1 3 1 2 2 3 4 4 7 3 7 5 5 8 4 8 6 7 4 5 0 7 1 10 6 9 8 3 12 9 4 3 10 7 5 ROW NO First Column for row no COLUMN NO Fig(d)  A more efficient representation in terms of storage requirement and access time to the row of the matrix is shown in fid (d). The row vector changed so that its ith element is the index to the first of the column indices for the element in row I of the matrix. Linked Representation of Sparse matrix Typical node to represent non-zero element is Row Column Value Pointer To Number Number Next Node 1 3 6 1 5 9 2 1 2 2 4 7 2 5 8 2 7 4 3 1 10 4 3 12 6 4 3 6 7 5 NULL Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 4  Linear Data Structure Write algorithms for Stack Operations – PUSH, POP, PEEP  A linear list which allows insertion and deletion of an element at one end only is called stack.  The insertion operation is called as PUSH and deletion operation as POP.  The most and least accessible elements in stack are known as top and bottom of the stack respectively.  Since insertion and deletion operations are performed at one end of a stack, the elements can only be removed in the opposite orders from that in which they were added to the stack; such a linear list is referred to as a LIFO (last in first out) list.  A pointer TOP keeps track of the top element in the stack. Initially, when the stack is empty, TOP has a value of “one” and so on.  Each time a new element is inserted in the stack, the pointer is incremented by “one” before, the element is placed on the stack. The pointer is decremented by “one” each time a deletion is made from the stack. Applications of Stack  Recursion  Keeping track of function calls  Evaluation of expressions  Reversing characters  Servicing hardware interrupts  Solving combinatorial problems using backtracking. Procedure : PUSH (S, TOP, X)  This procedure inserts an element x to the top of a stack which is represented by a vector S containing N elements with a pointer TOP denoting the top element in the stack. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 5  Linear Data Structure 1. [Check for stack overflow] If TOP ≥ N Then write (‘STACK OVERFLOW’) Return 2. [Increment TOP] TOP ←TOP + 1 3. [Insert Element] S[TOP] ←X 4. [Finished] Return Function : POP (S, TOP)  This function removes the top element from a stack which is represented by a vector S and returns this element. TOP is a pointer to the top element of the stack. 1. [Check for underflow of stack] If TOP = 0 Then Write (‘STACK UNDERFLOW ON POP’) Take action in response to underflow Return 2. [Decrement Pointer] TOP ← TOP – 1 3. [Return former top element of stack] Return (S[TOP + 1]) Function : PEEP (S, TOP, I)  This function returns the value of the ith element from the TOP of the stack which is represented by a vector S containing N elements. The element is not deleted by this function. 1. [Check for stack Underflow] If TOP - I +1 ≤ 0 Then Write (‘STACK UNDERFLOW ON PEEP’) Take action in response to Underflow Exit 2. [Return Ith element from top of the stack Return (S[TOP – I + 1]) Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 6  Linear Data Structure Write an algorithm to change the ith value of stack to value X PROCEDURE : CHANGE (S, TOP, X, I)  This procedure changes the value of the Ith element from the top of the stack to the value containing in X. Stack is represented by a vector S containing N elements. 1. [Check for stack Underflow] If TOP – I + 1 ≤ 0 Then Write (‘STACK UNDERFLOW ON CHANGE’) Return 2. [Change Ith element from top of the stack] S[TOP – I + 1] ← X 3. [Finished] Return Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 7  Linear Data Structure Write an algorithm which will check that the given string belongs to following grammar or not. L={wcwR | w Є {a,b}*}(Where wR is the reverse of w) Algorithm : RECOGNIZE  Given an input string named STRING on the alphabet {a, b, c} which contains a blank in its rightmost character position and function NEXTCHAR which returns the next symbol in STRING, this algorithm determines whether the contents of STRING belong to the above language. The vector S represents the stack, and TOP is a pointer to the top element of the stack. 1. [Initialize stack by placing a letter ‘c’ on the top] TOP ← 1 S [TOP] ← ‘c’ 2. [Get and stack symbols either ‘c’ or blank is encountered] NEXT ← NEXTCHAR (STRING) Repeat while NEXT ≠ ‘c’ If NEXT = ‘ ‘ Then Write (‘Invalid String’) Exit Else Call PUSH (S, TOP, NEXT) NEXT ← NEXTCHAR (STRING) 3. [Scan characters following ‘c’; Compare them to the characters on stack] Repeat While S [TOP] ≠ ‘c’ NEXT ← NEXTCHAR (STRING) X ← POP (S, TOP) If NEXT ≠ X Then Write (‘INVALID STRING’) Exit 4. [Next symbol must be blank] If NEXT ≠ ‘ ‘ Then Write (‘VALID STRING’) Else Write (‘INVALID STRING’) 5. [Finished] Exit Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 8  Linear Data Structure Write an algorithm for push, pop and empty operations on stack. Using above functions write an algorithm to determine if an input character string is of the form aibi where i>=1 i.e. no of a should be equal to no of b Algorithm RECOGNIZE  Given an input string named STRING on alphabet ‘a’ and ‘b’ which contain blank (‘ ‘) on right most character function NEXTCHAR which returns the next symbol from STRING. This algorithm determines if an input string is of form aibi where i>1 i.e no of ‘a’ should be equal to no of ‘b’. the vector S represent the stack and TOP is the pointer to the top element of stack. Counter is a counter B for ‘b’ occurrence. 1. [Initialize stack and counter] TOP  0 COUNTER_B  0 2. [Get and stack character ‘a’ from whole string and count the occurrence of ‘b’ ] NEXT  NEXTCHAR(STRING) Repeat while NEXT != ‘ ‘ IF NEXT = ‘a’ Then PUSH (S,TOP,NEXT) Else COUNTER_B  COUNTER_B+1 NEXT NEXTCHAR(STRING) 3. [Pop the stack until empty and decrement the COUNTER_B] Repeat while TOP != 0 POP (S,TOP) COUNTER_B COUNTER_B-1 4. [Check for grammar] If COUNTER_B != 0 Then write (‘INVALID STRING’) Else write (‘VALID STRING’) What is recursion? Write a C program for GCD using recursion.  A procedure that contains a procedure call to itself or a procedure call to second procedure which eventually causes the first procedure to be called is known as recursive procedure.  There are two important conditions that must be satisfied by any recursive procedure a. Each time a procedure calls itself it must be nearer in some sense to a solution b. There must be a decision criterion for stopping the process or computation  There are two types of recursion o Primitive Recursion: this is recursive defined function. E.g. Factorial function o Non-Primitive Recursion: this is recursive use of procedure. E.g. Find GCD of given two nunbers Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 9  Linear Data Structure C program for GCD using recursion #include int Find_GCD(int, int); void main() { int n1, n2, gcd; scanf(“%d %d”,&n1, &n2); gcd = Find_GCD(n1, &n2); printf(“GCD of %d and %d is %d”, n1, n2, gcd); } int Find_GCD(int m, int n) { int gcdVal; if(n>m) { gcdVal = Find_GCD(n,m); } else if(n==0) { gcdVal = m; } else { gcdVal = Find_GCD(n, m%n); } return(gcdVal); } Write an algorithm to find factorial of given no using recursion Algorithm: FACTORIAL Given integer N, this algorithm computes factorial of N. Stack A is used to store an activation record associated with each recursive call. Each activation record contains the current value of N and the current return address RET_ADDE. TEMP_REC is also a record which contains two variables PARAM & ADDRESS.TOP is a pointer to the top element of stack A. Initially return address is set to the main calling address. PARAM is set to initial value N. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 10  Linear Data Structure 1. [Save N and return Address] CALL PUSH (A, TOP, TEMP_REC) 2. [Is the base criterion found?] If N=0 then FACTORIAL 1 GO TO Step 4 Else PARAM N-1 ADDRESS Step 3 GO TO Step 1 3. [Calculate N!] FACTORIAL N * FACTORIAL 4. [Restore previous N and return address] TEMP_RECPOP(A,TOP) (i.e. PARAMN, ADDRESSRET_ADDR) GO TO ADDRESS Give difference between recursion and iteration Iteration Recursion In iteration, a problem is converted into a train of Recursion is like piling all of those steps on top of steps that are finished one at a time, one after each other and then quashing them all into the another solution. With iteration, each step clearly leads onto the In recursion, each step replicates itself at a smaller next, like stepping stones across a river scale, so that all of them combined together eventually solve the problem. Any iterative problem is solved recursively Not all recursive problem can solved by iteration It does not use Stack It uses Stack Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 11  Linear Data Structure Write an algorithm to convert infix expression to postfix expression. Symbol Input precedence Stack precedence Rank function R function F function G +, - 1 2 -1 *, / 3 4 -1 ^ 6 5 -1 Variables 7 8 1 ( 9 0 - ) 0 - - Algorithm : REVPOL  Given an input string INFIX containing an infix expression which has been padded on the right with ‘)’ and whose symbol have precedence value given by above table, a vector S used as a stack and a NEXTCHAR which when invoked returns the next character of its argument. This algorithm converts INFIX into reverse polish and places the result in the string POLISH. The integer variable TOP denotes the top of the stack. Algorithm PUSH and POP are used for stack manipulation. The integer variable RANK accumulates the rank of expression. Finally the string variable TEMP is used for temporary storage purpose. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 12  Linear Data Structure 1. [Initialize stack] TOP  1 S[TOP]  ‘(‘ 2. [Initialize output string and rank count ] POLISH  ‘ ‘ RANK  0 3. [Get first input symbol] NEXTNEXTCHAR (INFIX) 4. [Translate the infix expression ] Repeat thru step 7 while NEXT != ‘ ‘ 5. [Remove symbols with greater precedence from stack] IF TOP < 1 Then write (‘INVALID’) EXIT Repeat while G (S[TOP]) > F(NEXT) TEMP  POP (S, TOP) POLISH  POLISH O TEMP RANK  RANK + R(TEMP) IF RANK = N Then write (‘OVERFLOW’) Return 2. [Increment REAR pointer] RR+1 3. [Insert element ] Q[R]  Y 4. [Is front pointer properly set] IF F=0 Then F  1 Return Function: QDELETE_FRONT (Q, F, R)  Given F and R pointers to the front and rear elements of a queue respectively. Queue Q consisting of N elements. This function deleted and element from front end of the Queue. 1. [Underflow] IF F= 0 Then write (‘UNDERFLOW’) Return(0) (0 denotes an empty Queue) 2. [Decrement element] Y  Q[F] 3. [Queue empty?] IF F=R Then F R 0 Else F F+1 (increment front pointer) 4. [Return element] Return (Y) Then F  1 Return Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 24  Linear Data Structure Write algorithms of basic primitive operations for Circular Queue Procedure: CQINSERT (F, R, Q, N, Y)  Given F and R pointers to the front and rear elements of a circular queue respectively. Circular queue Q consisting of N elements. This procedure inserts Y at rear end of Circular queue. 1. [Reset Rear Pointer] If R=N Then R← 1 Else R←R+1 2. [Overflow] If F=R Then Write (‘Overflow’) Return 3. [Insert element] Q[R] ← Y 4. [Is front pointer properly set?] If F=0 Then F ← 1 Return Function CQDELETE (F, R, Q, N)  Given F and R pointers to the front and rear elements of a Circular queue respectively. Circular Queue Q consisting of N elements. This function deleted and element from front end of the Circular Queue. Y is temporary pointer variable. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 25  Linear Data Structure 1. [Underflow?] If F = 0 Then Write (‘UNDERFLOW’) Return (0) 2. [Delete Element] Y ← Q[F] 3. [Queue Empty?] If F=R Then F ← R ← 0 Return (Y) 4. [Increment front pointer] If F=N Then F ← 1 Else F←F+1 Return (Y) Write algorithms of basic primitive operations for DQueue Procedure DQINSERT_FRONT (Q, F, R, N,Y)  Given F and R pointers to the front and rear elements of a queue, a queue consisting of N elements and an element Y, this procedure inserts Y at the front of the queue. 1. [Overflow] IF F=0 Then write (‘EMPTY’) Return IF F=1 Then write (‘OVERFLOW’) Return 2. [Decrement front pointer] F  F-1 3. [Insert element ] Q[F]  Y Return Procedure DQDELETE_REAR (Q, F, R)  Given F and R pointers to the front and rear elements of a queue. And a queue Q to which they correspond, this function deletes and returns the last element from the front end of a queue. And Y is temporary variable. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 26  Linear Data Structure 1. [Underflow] IF R= 0 Then write (‘UNDERFLOW’) Return(0) 2. [Delete element] Y  Q[R] 3. [Queue empty?] IF R=F Then R F 0 Else R R-1 (decrement front pointer) 4. [Return element] Return (Y) Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 27  Linear Data Structure PROCEDURE DQUEUE_DISPLAY (F,R,Q)  Given F and Rare pointers to the front and rear elements of a queue, a queue consist of N elements. This procedure display Queue contents 1. [Check for empty] IF F >= R Then write (‘QUEUE IS EMPTY’) Return 2. [Display content] FOR (I=FRONT; I= MAXSIZE) printf("Stack is Overflow"); else stack[++top] = val; } int pop() { int a; if(top>=0) { a=stack[top]; top–-; return a; } else { printf("Stack is Underflow, Stack is empty, nothing to POP!"); return -1; } } Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 24  Linked List Implement PUSH and POP using Linked List #include #include struct node { int info; struct node *link; } *top; void push(int val) { struct node *p; p = (struct node*)malloc(sizeof(struct node)); p  info = val; p  link = top; top = p; return; } int pop() { int val; if(top!=NULL) { val = top  info; top=top link; return val; } else { printf("Stack Underflow"); return -1; } } 9. Write the implementation procedure of basic primitive operations of the Queue using: (i) Linear array (ii) linked list Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 25  Linked List Implement Enqueue(Insert)and Dequeue(Delete)using Linear Array # include # define MAXSIZE 100 int queue[MAXSIZE], front = -1, rear = -1; void enqueue(int val) { if(rear >= MAXSIZE) { printf("Queue is overflow") ; return ; } rear++; queue [rear] = val; if(front == -1) { front++; } } int dequeue() { int data; if(front == -1) { printf("Queue is underflow") ; return -1; } data = queue [front]; if(front == rear) { front = rear = -1; } else { front++; } return data; } Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 26  Linked List Implement Enqueue(Insert)and Dequeue(Delete)using Linked List #include #include struct node { int info; struct node *link; } *front, *rear; void enqueue(int val) { struct node *p; p = (struct node*)malloc(sizeof(struct node)); p  info = val; p  link = NULL; if (rear == NULL || front == NULL) { front = p; } else { rear  link = p; rear = p; } } int dequeue() { struct node *p; int val; if (front == NULL || rear == NULL) { printf("Under Flow"); exit(0); } else { p = front; val = p  info; front = front  link; free(p); } return (val); } Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 27  Linked List 10. Write an algorithm to implement ascending priority queue using singular linear linked list which has insert() function such that queue remains ordered list. Also implement remove() function struct node { int priority; int info; struct node *link; }*front = NULL; remove() { struct node *tmp; if(front == NULL) printf("Queue Underflow\n"); else { tmp = front; printf("Deleted item is %d\n",tmp->info); front = front->link; free(tmp); } } Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 28  Linked List insert() { struct node *tmp,*q; int added_item,item_priority; tmp = (struct node *)malloc(sizeof(struct node)); printf("Input the item value to be added in the queue : "); scanf("%d",&added_item); printf("Enter its priority : "); scanf("%d",&item_priority); tmp->info = added_item; tmp->priority = item_priority; if( front == NULL || item_priority < front->priority ) { tmp->link = front; front = tmp; } else { q = front; while( q->link != NULL && q->link->priority link; } tmp->link = q->link; q->link = tmp; } } Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 29  Linked List display() { struct node *ptr; ptr = front; if(front == NULL) printf("Queue is empty\n"); else { printf("Queue is :\n"); printf("Priority Item\n"); while(ptr != NULL) { printf("%5d %5d\n",ptr->priority,ptr->info); ptr = ptr->link; } } } Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 30  Nonlinear Data Structure (Graph & Tree) 1. Discuss following 1. Graph  A graph G consist of a non-empty set V called the set of nodes (points, vertices) of the graph, a set E which is the set of edges and a mapping from the set of edges E to a set of pairs of elements of V.  It is also convenient to write a graph as G=(V,E).  Notice that definition of graph implies that to every edge of a graph G, we can associate a pair of nodes of the graph. If an edge X Є E is thus associated with a pair of nodes (u,v) where u, v Є V then we says that edge x connect u and v. 2. Adjacent Nodes  Any two nodes which are connected by an edge in a graph are called adjacent node. 3. Directed & Undirected Edge  In a graph G=(V,E) an edge which is directed from one end to another end is called a directed edge, while the edge which has no specific direction is called undirected edge. 4. Directed graph (Digraph)  A graph in which every edge is directed is called directed graph or digraph. 5. Undirected graph  A graph in which every edge is undirected is called undirected graph. 6. Mixed Graph  If some of the edges are directed and some are undirected in graph then the graph is called mixed graph. 7. Loop (Sling)  An edge of a graph which joins a node to itself is called a loop (sling). 8. Parallel Edges  In some directed as well as undirected graphs, we may have certain pairs of nodes joined by more than one edges, such edges are called Parallel edges. 9. Multigraph  Any graph which contains some parallel edges is called multigraph. 10. Weighted Graph  A graph in which weights are assigned to every edge is called weighted graph. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 1  Nonlinear Data Structure (Graph & Tree) 11. Isolated Node  In a graph a node which is not adjacent to any other node is called isolated node. 12. Null Graph  A graph containing only isolated nodes are called null graph. In other words set of edges in null graph is empty. 13. Path of Graph  Let G=(V, E) be a simple digraph such that the terminal node of any edge in the sequence is the initial node of the edge, if any appearing next in the sequence defined as path of the graph. 14. Length of Path  The number of edges appearing in the sequence of the path is called length of path. 15. Degree of vertex  The no of edges which have V as their terminal node is call as indegree of node V  The no of edges which have V as their initial node is call as outdegree of node V  Sum of indegree and outdegree of node V is called its Total Degree or Degree of vertex. 16. Simple Path (Edge Simple)  A path in a diagraph in which the edges are distinct is called simple path or edge simple. 17. Elementary Path (Node Simple)  A path in which all the nodes through which it traverses are distinct is called elementary path. 18. Cycle (Circuit)  A path which originates and ends in the same node is called cycle (circuit). 19. Directed Tree  A directed tree is an acyclic digraph which has one node called its root with in degree 0, while all other nodes have in degree 1.  Every directed tree must have at least one node.  An isolated node is also a directed tree. 20. Terminal Node (Leaf Node)  In a directed tree, any node which has out degree 0 is called terminal node or leaf node. 21. Level of Node  The level of any node is the length of its path from the root. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 2  Nonlinear Data Structure (Graph & Tree) 22. Ordered Tree  In a directed tree an ordering of the nodes at each level is prescribed then such a tree is called ordered tree. 23. Forest  If we delete the root and its edges connecting the nodes at level 1, we obtain a set of disjoint tree. A set of disjoint tree is a forest. 24. M-ary Tree  If in a directed tree the out degree of every node is less than or equal to m then tree is called an m-ary tree. 25. Full or Complete M-ary Tree  If the out degree of each and every node is exactly equal to m or 0 and their number of nodes at level i is m(i-1) then the tree is called a full or complete m-ary tree. 26. Positional M-ary Tree  If we consider m-ary trees in which the m children of any node are assumed to have m distinct positions, if such positions are taken into account, then tree is called positional m- ary tree. 27. Height of the tree  The height of a tree is the length of the path from the root to the deepest node in the tree. 28. Binary tree  If in a directed tree the out degree of every node is less than or equal to 2 then tree is called binary tree. 29. Strictly binary tree  A strictly binary tree (sometimes proper binary tree or 2-tree or full binary tree) is a tree in which every node other than the leaves has two children. 30. Complete binary tree  If the out degree of each and every node is exactly equal to 2 or 0 and their number of nodes at level i is 2(i-1) then the tree is called a full or complete binary tree. 31. Sibling  Siblings are nodes that share the same parent node. 32. Binary search tree  A binary search tree is a binary tree in which each node possessed a key that satisfy the following conditions Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 3  Nonlinear Data Structure (Graph & Tree) 1. All key (if any) in the left sub tree of the root precedes the key in the root. 2. The key in the root precedes all key (if any) in the right sub tree. 3. The left and right sub tree sub trees of the root are again search trees. 33. Height Balanced Binary tree (AVL Tree)  A tree is called AVL (height balance binary tree), if each node possesses one of the following properties 1. A node is called left heavy if the longest path in its left sub tree is one longer then the longest path of its right sub tree. 2. A node is called right heavy if the longest path in the right sub tree is one longer than path in its left sub tree. 3. A node is called balanced, if the longest path in both the right and left sub tree are equal. 2. Explain the Preorder, Inorder and Postorder traversal techniques of the binary tree with suitable example.  The most common operations performed on tree structure is that of traversal. This is a procedure by which each node in the tree is processed exactly once in a systematic manner.  There are three ways of traversing a binary tree. 1. Preorder Traversal 2. Inorder Traversal 3. Postorder Traversal A Preorder traversal : A B C D E F G Inorder traversal : C B A E F D G B D Postorder traversal : C B F E G D A Converse Preorder traversal : A D G E F B C C E G Converse Inorder traversal : G D F E A B C Converse Postorder traversal : G F E D C B A Fig. 1.1 F Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 4  Nonlinear Data Structure (Graph & Tree) Preorder  Preorder traversal of a binary tree is defined as follow o Process the root node o Traverse the left subtree in preorder o Traverse the right subtree in preorder  If particular subtree is empty (i.e., node has no left or right descendant) the traversal is performed by doing nothing, In other words, a null subtree is considered to be fully traversed when it is encountered.  The preorder traversal of a tree (Fig. 1.1) is given by A B C D E F G Inorder  The Inorder traversal of a binary tree is given by following steps, o Traverse the left subtree in Inorder o Process the root node o Traverse the right subtree in Inorder  The Inorder traversal of a tree (Fig. 1.1) is given by C B A E F D G Postorder  The postorder traversal is given by o Traverse the left subtree in postorder o Traverse the right subtree in postorder o Process the root node  The Postorder traversal of a tree (Fig. 1.1) is given by C B F E G D A Converse …  If we interchange left and right words in the preceding definitions, we obtain three new traversal orders which are called o Converse Preorder (A D G E F B C) o Converse Inorder (G D F E A B C) o Converse Postorder (G F E D C B A) 3. Write the algorithm of Preorder, Inorder and Postorder traversal techniques of the binary tree. Procedure : RPREORDER(T)  Given a binary tree whose root node address is given by pointer variable T and whose node structure is same as described below. This procedure traverses the tree in preorder, in a recursive manner. Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 5  Nonlinear Data Structure (Graph & Tree) LPTR DATA RPTR 1. [Check for empty Tree] If T = NULL then write (‘Empty Tree’) return else write (DATA(T)) 2. [Process the Left Subtree] If LPTR (T) ≠ NULL then RPREORDER (LPTR (T)) 3. [Process the Right Subtree] If RPTR (T) ≠ NULL then RPREORDER (RPTR (T)) 4. [Finished] return Procedure : RINORDER(T)  Given a binary tree whose root node address is given by pointer variable T and whose node structure is same as described below. This procedure traverses the tree in inorder, in a recursive manner. 1. [Check for empty Tree] If T = NULL then write (‘Empty Tree’) return 2. [Process the Left Subtree] If LPTR (T) ≠ NULL then RINORDER (LPTR (T)) 3. [Process the root node] write (DATA(T)) 4. [Process the Right Subtree] If RPTR (T) ≠ NULL then RINORDER (RPTR (T)) 5. [Finished] return Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 6  Nonlinear Data Structure (Graph & Tree) Procedure : RPOSTORDER(T)  Given a binary tree whose root node address is given by pointer variable T and whose node structure is same as described below. This procedure traverses the tree in postorder, in a recursive manner. 1. [Check for empty Tree] If T = NULL then write (‘Empty Tree’) return 2. [Process the Left Subtree] If LPTR (T) ≠ NULL then RPOSTORDER (LPTR (T)) 3. [Process the Right Subtree] If RPTR (T) ≠ NULL then RPOSTORDER (RPTR (T)) 4. [Process the root node] write (DATA(T)) 5. [Finished] return 4. Give traversal order of following tree into Inorder, Preorder and Postorder. 1 Inorder: 2 1 4 5 3 Preorder: 1 2 3 4 5 Post order: 2 5 4 3 1 2 3 4 5 Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 7  Nonlinear Data Structure (Graph & Tree) 5. Construct a tree for the given Inorder and Postorder traversals Inorder :DGBAHEICF Postorder : G D B H I E F C A A D G B H E I C F A B C D G H E I F A B C D E F G H I Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 8  Nonlinear Data Structure (Graph & Tree) Postorder : C B E H G I F D A Inorder :BCAEDGHFI A B C E D G H F I A B D C E G H F I A B D C E F G H I A B D C E F G I H Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 9  Nonlinear Data Structure (Graph & Tree) 6. Construct a tree for the given Inorder and Preorder traversals Preorder : G B Q A C K F P D E R H Inorder : Q B K C F A G P E D H R G Q B K C F A P E D H R G B P Q K C F A D E R H G B P Q A D E R H K C F G B P Q A D C E R K F H Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 10  Nonlinear Data Structure (Graph & Tree) 7. Create a binary search tree for the following data : 50 ,25 ,75, 22,40,60,80,90,15,30 50 25 75 22 40 80 60 15 30 90 8. Construct binary search tree for the following data and find its Inorder, Preorder and Postorder traversal 10,3,15,22,6,45,65,23,78,34,5 10 3 15 6 22 5 45 23 65 34 78 Preorder : 10, 3, 6, 5, 15, 22, 45, 23, 34, 65, 78 Inorder : 3, 5, 6, 10, 15, 22, 23, 34, 45, 65, 78 Postorder : 5, 6, 3, 34, 23, 78, 65, 45, 22, 15, 10 Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 11  Nonlinear Data Structure (Graph & Tree) 9. Write a short note on threaded binary tree  The wasted NULL links in the binary tree storage representation can be replaced by threads.  A binary tree is threaded according to particular traversal order. e.g.: Threads for the inorder traversals of tree are pointers to its higher nodes, for this traversal order. o If left link of node P is null, then this link is replaced by the address of its predecessor. o If right link of node P is null, then it is replaced by the address of its successor  Because the left or right link of a node can denote either structural link or a thread, we must somehow be able to distinguish them.  Method 1:- Represent thread a –ve address.  Method 2:- To have a separate Boolean flag for each of left and right pointers, node structure for this is given below, LPTR LTHREAD Data RTHREAD RPTR Alternate node for threaded binary tree.  LTHREAD = true = Denotes leaf thread link  LTHREAD = false = Denotes leaf structural link  RTHREAD = true = Denotes right threaded link  RTHREAD = false = Denotes right structural link  Head node is simply another node which serves as the predecessor and successor of first and last tree nodes. Tree is attached to the left branch of the head node Head Advantages  Inorder traversal is faster than unthreaded version as stack is not required.  Effectively determines the predecessor and successor for inorder traversal, for unthreaded tree this task is more difficult.  A stack is required to provide upward pointing information in tree which threading provides.  It is possible to generate successor or predecessor of any node without having over head of stack with the help of threading. Disadvantages  Threaded trees are unable to share common subtrees Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 12  Nonlinear Data Structure (Graph & Tree)  If –ve addressing is not permitted in programming language, two additional fields are required.  Insertion into and deletion from threaded binary tree are more time consuming because both thread and structural link must be maintained. A B D E G C F Binary Tree Inorder Traversal C B A E F D G Fully In-threaded binary tree of given binary tree HEAD A B D C E G F Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 13  Nonlinear Data Structure (Graph & Tree) 10. Draw a right in threaded binary tree for the given tree Right In-threaded binary tree of given binary tree HEAD A B E C D F H G Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 14  Nonlinear Data Structure (Graph & Tree) 11. What is the meaning of height balanced tree? How rebalancing is done in height balanced tree. A tree is called AVL (height balance binary tree), if each node possesses one of the following properties 1. A node is called left heavy if the longest path in its left sub tree is one longer then the longest path of its right sub tree. 2. A node is called right heavy if the longest path in the right sub tree is one longer than path in its left sub tree. 3. A node is called balanced, if the longest path in both the right and left sub tree are equal. If tree becomes unbalanced by inserting any node, then based on position of insertion, we need to rotate the unbalanced node. Rotation is the process to make tree balanced 1) Insertion into Left sub-tree of nodes Left child – Single Right Rotation 2) Insertion into Right sub-tree of node’s Left child – Left Right Rotation 3) Insertion into Left sub-tree of node’s Right child – Right Left Rotation 4) Insertion into Right sub-tree of node’s Right child – Single Left Rotation 1) Insertion into Left sub-tree of nodes Left child – Single Right Rotation If node becomes unbalanced after insertion of new node at Left sub-tree of nodes Left child, then we need to perform Single Right Rotation for unbalanced node. Right Rotation a. Detach leaf child’s right sub-tree b. Consider leaf child to be the new parent c. Attach old parent onto right of new parent d. Attach old leaf child’s old right sub-tree as leaf sub-tree of new right child Critical Node J K Right J K Z X Rotation X Y N Y Z N Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 15  Nonlinear Data Structure (Graph & Tree) Critical Node 13 7 Steps of 13 7 15 Right 5 Rotation 5 10 3 10 15 3 7 7 5 13 5 13 3 10 15 3 10 15 2) Insertion into Right sub-tree of node’s Left child – Left Right Rotation If node becomes unbalanced after insertion of new node at Right sub-tree of node’s Left child, then we need to perform Left Right Rotation for unbalanced node. Leaf rotation of leaf child followed by right rotation of parent J J Y Y Z K J K Z Left Right Rotation of K Rotation of J X Y K n Z n X n X 3) Insertion into Left sub-tree of node’s Right child – Right Left Rotation If node becomes unbalanced after insertion of new node at Left sub-tree of node’s Right child, then we need to perform Right Left Rotation for unbalanced node. Single right rotation of right child followed by left rotation of parent Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 16  Nonlinear Data Structure (Graph & Tree) Unbalanced node X X Y T1 Right T1 Y Left Z Rotation of Z Rotation of X X Z T2 Y T4 Z T1 T2 T3 T4 T3 T4 T2 T3 4) Insertion into Right sub-tree of node’s Right child – Single Left Rotation If node becomes unbalanced after insertion of new node at Right sub-tree of nodes Right child, then we need to perform Single Left Rotation for unbalanced node. Left Rotation a. Detach right child’s leaf sub-tree b. Consider right child to be new parent c. Attach old parent onto left of new parent d. Attach old right child’s old left sub-tree as right sub-tree of new left child Unbalanced node X Y T1 Y Leaf T3 Rotation of X X T2 T3 T1 T2 n n Example 50 Unbalanced node 70 70 40 70 50 80 50 80 90 60 80 40 90 40 60 90 60 Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 17  Nonlinear Data Structure (Graph & Tree) 12. Construct AVL Search tree by inserting following elements in order of their occurrence 6, 5, 4, 3, 2, 1 1 2 3 4 Insert 6 Insert : 5 Insert : 4 Insert : 3 Right 6 6 6 5 5 F F Rotate 6 F F F : 5 : 5 : 4 i i 6 4 6 \ F \ F \ : n n F : F D : D 4 : D \ a a : 3 \ : F \ F F \ F D l l \ : D \ S D S : D S F M D M 6\ 5 \ F D \ F \ F \ S a a F S S D D D D Insert : 2F D Insert : S1 \ t S F \ t S F \ F 5 F \ F 5 D e e \ S D 5 \ D S F S D S F F r Righ S D F Fr t \ D F F 3F i 6\ F F 3 i S 6 i i F D S 6F i S : i n FD S i : n F F a Rotate 4 a S F F n FS n 2 F \ n a4 :F F n 2 \ a4 i : l F 3S i al :F a : i D a l: \S i a : D l: n \ F i n lF l M l \ M :F \i l 1 \ n FRight \ DF n F \ a D : n a M: n M aD M D aD l F \ 2 \i D M : D a SRotate 5 Fi a S a Dn l a\ Fa \ a tF a F tF M S D : a \ Fl Sn l \ l Fa M tD Sl eS a \ F \ t D S M D3t eS \a M t S D M Sl a eF \M D e F \ a FF e r\ Dl a e \ F r\ t D S a \M t rS Da F r S D2t Si r iD FM t r D S iD e F \ t a e i\ Ft 5 aF r S D S D i \ F: e Fni aF Sa e i F F e Ft r aD Se : \ a D S\r i a a lS Ft r a S i lS i F F r Se i lF Fr 1 \ D l F: FDi n4l l FF i6e i l F n FF a i S i a FS : D :i l n F F Fr i F S i Fa aMF :i nFr a F i a a i l :F na \ F S : F nSl l\a : \n a:i l : n l \n F a i l F \i D D \ SD F na al \ i a\F M t a l\a F \ a M D a : l n F : Dn lF Assignment: F \ i al D n l D: aFeD Fl MDl : D l a Fl \ M a : \ Fa S D lF n Construct M:  Define F a height S F binary MF\ of tther F SM atree. Define \ F M balanced height t SM tree D awithl its advantages. a height Sl \ binary F\ tree) \ a M: D a\ balanced S l aSD treee\i S (AVL a tS: for the S a datae42,06,54,62,88,50,22,32,12,33 D following \a F t M D F \M D theF AVLDsearch S tree\ by inserting \the following elements a\ tD  Construct \ M tF ra \ D t e F t r D t S e inathe order ofltheir occurrence. 64, Da 1, F tD S eF 44, D 26, F 13, 110,S 98, iF D85 FF rD S D e i Fe \ r t M t aS e i l e S eF \ F rS S i a F t rn\ aF F Sr iF \ F r a Sr D i e \ rS D Se i\ F n t S e D lF: S Fi i aJadeja aS | 2130702 D S i l Fi F a r Fr Prof. Pradyumansinh i (9879461848) a – Data Structure D e i\ F 18aD i F r al F F\ F ia lF\ F F a F ia S l i F aD S i lF n n l r i ia l MS : Di n l FiD S i l : n l F F a S lF F na FS a M i n a FaF \F n aF :nF F n F \ aF i : l F i al :F l l a al a FS a : i D : \aS i a : D l: n \ l  Nonlinear Data Structure (Graph & Tree) 13. What are the advantages of Multiway search tree in disc access? Construct B tree of order 5 for the following data 1,6,7,2,11,5,10,13,12,20,16,24,3,4,18,19,14,25 1 2 3 4 5 Insert: 1 Insert: 6 Insert: 7 Insert: 2 Insert: 11 6 1 1, 6 1, 6, 7 1, 2, 6, 7 1, 2, 6, 7, 11 Overflow 1, 2 7, 11