Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Chapter 1 Introduction Overview (Data Structures, ADTs, and Algorithms) Data Element Domain x ADT < Organization Data Structure TunchoHt Programm Inmplementation “Algorithm Restricted Access Linear < Simple Unrestricted Access Data Element Organization Compound Tree Non-linear’ < Graph “Access Function Modification Function Why data structures? Ultimate goal of data structures is to write efficient programs. In order to do that, one needs to organize the data in such a way that it can be accessed and manipulated efficiently, Data structure A data structure is used for the storage of data in computer so that data can be used efficiently. For the organization of mathematical and logical concepts data structure provides a methodology. With the proper selection of data structure you can also get efficient algorithm. With very few resources like memory space and time critical operations can be carried out with a well designed data structure. The major use of data structure is its implementation in the programming language Moreover, there are different kinds of data structures and they have different uses, Some data structures are used for specialized tasks like B-trees are used for the implementation of databases and networks of machines use routing tables. ‘A data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of theLecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT data structure often begins from the choice of an abstract data type. A well-designed data structure allows a vatiety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented by a programming language as data types and the references and operations they provide “Collection of data elements organized in a specified manner and a set of functions to store, retrieve and manipulate the individual data elements.” ‘he way of representing data internally in the memory is called data structure” Or “A data structure is a way of store data in a computer so that it can be used efficiently” A data structure is a specialized format for organizing and storing data, General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ‘ways. In computer programming, a data structure may be selected or designed to store data for the yurpose of working on it with various algorithms. Mathematcial ba Data Model = hype => Structures Informal bseudo Program ILanguage nC om [Algorithm — | ——> program | => java of The Problem Solving Process in Computer Science We use data structure because without it, the use and storage of data would be impossible. Whenever ‘you view or process data on a computer system, there is always a data structure behind what you are doing. Different types of data structures are used for varying kinds of data - for instance, word documents will have a different data structure than spreadsheets, Data structures act as. the fundamental foundations of all computer software processes. © Data structures have a number of great advantages, including those listed below: © Data structures allow information to be securely stored on a computer system. Most data structures require only a small proportion of a computer's memory capacity. Storing data is convenient and allows it to be accessed at any time, It is also impossible to lose the information, as you might if it was on paper. © Data structures provide you with the capacity to use and process your data on a software if you wished to log your work hours and produce a report, you could 2Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT do soon a computer through an automated process. This process would make wide use of data structures, © Data structures make all processes involving them very quick. © On the other hand, data structures do have some disadvantages © To alter data structures, you must be a very advanced IT technician with a vast experience base. Its almost impossible to change most data structures. © If you have a problem relating to data structures, it is highly unlikely you will be able to solve it without the expertise of a professional. Example: Suppose you are hired (o create a database of names with all company's management and employees. You can make a list. You can also make a tree. ead Aaron Manager Charles ve George Employee Jack Employee Janet ve John President Types of data structure In all, it can be seen that data structures are highly beneficial, not least because they allow the most basic pieces of computer software to function correctly. Without data structures, we would not have the modern computer of today.Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Data Structures ———— ‘Simple Data Structures | [ Compound Data Strudure ————, Linear Data Structures | [Non-Linear Data Strucutes| ‘Stack Tree Queue Graph Lists Data structures can be classified as © Simple data structure © Compound data structure © Linear data structure © Non linear data structure Simple Data Structure: 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: Collection of nodes which are logically adjacent in which logical adjacency i pointers maintained byLecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Or 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 Add an element Delete an element Tray Sort the list of elements Search for a data element By applying one or more functionalities to create different types of data structures 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. Add elements: Delete elements Display the elements Sort the list of elements Search for a data element By applying one or more functionalities and different ways of joining randomly distributed data items to create different types of data structures. For example Tree, Decision tree, Graph and Forest Some DefinitionsLecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT ‘We provide below informal definitions of a few important, common notions that we will frequently use in this lecture notes. Algorithm A finite sequence of instructions, each of which have a clear meaning and can be executed with a finite amount of effort in finite time is called algorithm. Whatever the input values, an algorithm will definitely terminate after executing a finite number of instructions, Data Type Data type of a variable is the set of values that the variable may assume. Basic data types in C: int char float double Abstraction The first thing that we need to consider when writing programs is the problem. However, the problems that we asked to solve in real life are often nebulous or complicated. Thus we need to distill such as system down to its most fundamental parts and describe these parts in a simple, precise language. This process is called abstraction. Through abstraction, we can generate a model of the problem, which defines an abstract view of the problem, Normally, the model includes the data that are affected and the operations that are required to access or modify. As an example, consider a program that manages the student records. The head of the Bronco Direct, comes to you and asks you to create a program which allows administering the students in a class. Well, this is too vague a problem, We need to think about, for example, what student information is needed for the record? What tasks should be allowed? There are many properties we could think of about a student, such as name, DOB, SSN, ID, major, email, mailing address, transcripts, hair colot, hobbies, ete, Not all these properties are necessary to solve the problem. To keep it simple, we assume that a student's record includes the following fields: (1) the student's name and (2) ID. The three simplest operations performed by this program include (1) adding a new student to the class, (2) searching the class for a student, given some information of the student, and (3) deleting a student who has dropped the class. These three operations can be furthermore defined as below: * ADD (stu_record): This operation adds the given student record to the collection of student records. * SEARCH (stu_record_id): This operation searches the collection of student records for the student whose ID has been given. © DELETE (stu_record_id): This operation deletes the student record with the given ID from the collection.Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Now, we have modeled the problem in its most abstract form: listing the types of data we are interested in and the operations that we would like to perform on the data. We have not discussed anything about how these student records will be stored in memory and how these operations will be implemented. This kind of abstraction defines an abstract data type (ADT) Abstract Data Type (AD An ADT isa set of elements with a collection of well defined operations. © The operations can take as operands not only instances of the ADT but other types of operands or instances of other ADTs. © Similarly results need not be instances of the ADT ¢ Atleast one operand or the result is of the ADT type in question, An ADT is a mathematical mode! of a data structure that specifies the type of data stored, the operations supported on them, and the types of parameters of the operations. An ADT specifies what each operation does, but not how it does it, Typically, an ADT can be implemented using one of many different data structures. A useful first step in deciding what data structure to use in a program is to specify an ADT for the program, In general, the steps of building ADT to data structures are: Understand and clarify the nature of the target information unit. Identify and determine which data objects and operations to include in the models. Express this property somewhat formally so that it can be understood and communicate well. Translate this formal specification into proper language. In C++, this becomes a .h file. In Java, this is called "user interface”. BeRS Upon finalized specification, write necessary implementation. This includes storage scheme and operational detail. Operational detail is expressed as separate functions (methods Object-oriented languages such as C++ and Java provide explicit support for expressing ADTs by means of classes. Examples of ADTs include list, stack, queue, set, tree, graph, etc. Data Structures: An implementation of an ADT is a translation into statements of a programming language, ¢ the declarations that define a variable to be of that ADT type © the operations defined on the ADT (using procedures of the programming language) ‘An ADT implementation chooses a data structure to represent the ADT. Each data structure is built up from the basic data types of the underlying programming language using the available data structuring facilities, such as attays, records (structures in C), pointers, files, sets, etc.Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Example: A Queue" is an ADT which can be defined as a sequence of elements with operations such as null (Q), empty (Q), enqueue(x, Q), and dequeue (Q). This can be implemented using data structures such as array singly linked list doubly linked list circular array Chapter 2 STACK Stacks are the subclass of lists that permits the insertion and deletion operation to be performed at only one end. They are LIFO (last in first out) list. An example of a stack is a railway system for shunting cars in this system, the last railway car to be placed on the stack is the first to leave, Operation on stacks A pointer TOP keeps track of the top element in the stack. Initially when the stack is empty, TOP has a value of zero and when the stack contains a single element; 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 in the stack. The pointer is decremented by one each time a deletion is made from the stack. PUSH Operation This is the insertion operation. when the value is entered itis inserted into an array. © In this algorithm, stack S is being used which can store maximum n element. The stack element are S [0], S [1]... $ [n-1] © Top keeps track of top of the stack. An item ‘VAL! is added to the stack provided it is already not full ie. TOP land top of stack is 8 1 PUSH 1 8 7 la 1 PUSH 4 3 7 POP 4 1 "4" is removed and top|8 lof stack is 1 7 POP 1 8 "1" is removed and top| of stack is 8Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Program to implement stack using array #include ifinclude #include class stack { int stk(5]; int top; publie: stack() { top=-1; } void push(int x) { if(top> 4) { cout <<"stack over flow"; return; cout <<"inserted" =0; cout <> ch; switch(ch) { case 1: cout <<"enter the element"; cin >> ch; st.push(ch); break; case 2: st.pop(); break; case 3: st.display();break; case 4: exit(0); } } return (0); } Infix transformation to Postfix This process uses a stack as well. We have to hold information that's expressed inside parenthes while scanning to find the closing ')). We also have to hold information on operations that are of lower precedence on the stack. The algorithm is: Infix Expression: Any expression in the standard form like "2*3-4/5" is an Infix (Inorder) expression, Postfix Expression: The Postfix (Postorder) form of the above expression is "23*45/." Infix to Postfix Conversion:Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT © Scan the Infix string from left to right. © Initialize an empty stack. If the scanned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty push the character topStack, © If the scanned character is an Operator and the stack is not empty. compare the precedence of the character with the element on top of the stack (topStack). IftopStack has higher precedence over the scanned character, pop the stack else push the scanned character tostack. Repeat this step as long asstackis not empty and topStack has precedence over the character. © Repeat this step till all the characters are scanned. © Ifthe current input token is ‘(, push it onto the stack © If the current input token is '), pop off all operators and append them to the output string until a'('is popped; discard the '(. Ifthe end of the input string is found, pop all operators and append them to the output string ¢ Retum the Postfix string Example: Let us see how the above algorithm will be implemented using an example. Infix String: atb*e-d Initi is ‘a ally the Stack is empty and our Postfix string has no characters. Now, the first character scanned ".'a! is added to the Postfix string. The next character scanned is ''. It being an operator, it is pushed to the stack, | Postfix String + Stack Next character scanned is 'b' which will be placed in the Postfix string. Next character is *' which is an operator. Now, the top element of the stack is '#" which has lower precedence than *', so will be pi ushed to the stack, 14Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT x | Postfix St + ostfix String Stack The next character is 'e' which is placed in the Postfix string, Next character scanned is‘, The topmost character in the stack is "*' which has a higher precedence than "’. Thus *' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to. So pop the ‘H from the stack and add it to the Postfix string. The '~' will be pushed to the stack. abc¥+ Postfix String Stack Next character is’d’ which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be: abc*¥ +d Postfix String Stack End result * Infix String : atb*e-d Postfix String: abe*+d- Postfix Evaluation Infix Expression: 15Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Any expression in the standard form like "2*3-4/5" is an Infix (Inorder) expression, Postfix Expression: The Postfix (Postorder) form of the above expression is "23*45/-" Postfix Evaluation: In normal algebra we use the infix notation like a+b*c, The corresponding postfix notation is abe*+. The algorithm for the conversion is as follows: © Sean the Postfix string from left to right, © Initialize an empty stack. © If the scanned character is an operand, add it to the stack. If the scanned character is an operator, there will be at least two operands in the stack. © If the scanned character is an Operator, then we store the top most clement of the stack (topStack) in a variable temp. Pop the stack. Now evaluate topStack (Operator) temp. Let the result of this operation be retVal. Pop the stack and Push retVal into the stack co Repeat this step till all the characters are scanned. After all characters are scanned, we will have only one element in the stack, Return topStack. Example: Let us see how the above algorithm will be implemented using an example. Postfix String: 123*+4- Initially the Stack is empty. Now, the first three characters scanned are 1, 2 and 3, which are operands. Thus they will be pushed into the stack in that order. Expression 3 2 Co 1 Stack ‘Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the stack and perform the "*" operation with the two operands. The second operand will be the first element that is popped. 16Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT 2*3: I Expression Stack The value of the expression (2*3) that has been evaluated (6) is pushed into the stack. 6 Co) I Expression Stack ‘Next character scanned is "+", which is an operator. Thus, we pop the top two elements from the stack and perform the "+" operation with the two operands. The second operand will be the first element that is popped. 14+6=7 Expression Stack The value of the expression (1+6) that has been evaluated (7) is pushed into the stack. 7 Expression Stack ‘Next charaeter scanned is "4", which is added to the stack. 7Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT 4 Co 7 Expression Stack Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the stack and perform the "-" operation with the two operands. The second operand will be the first element that is popped. Expression Stack The value of the expression (7-4) that has been evaluated (3) is pushed into the stack. 3 Expression Stack Now, since all the characters are scanned, the remaining element in the stack (there will be only one element in the stack) will be returned. End result: Postfix String : 123*+4- Result: 3 Abstract data types vs Data structures Before starting that, we need to be clear about the logical and implementation level of data. Let us take an example of a simple built-in data type integer. At the logic level, we application programmers know only about what are the operations an integer data type can perform, ie. Addition, subtraction etc., But we are no way aware of how the data type is actually implemented. At the implementation level, it is about how the data type integer is implemented in the machine 18Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT level, i.e., it could either of binary-coded decimal, unsigned binary, sign-and-magnitude binary, One's complement and Two's complement notation, ‘Now, for the understanding the ADT and data structure, we need to assume a higher level abstraction where we have the built-in types at the implementation level. To put it simple, ADT is a logical description and data structure is concrete. ADT is the logical picture of the data and the operations to manipulate the component elements of the data. Data structure is the actual representation of the data during the implementation and the algorithms to manipulate the data elements, ADT is in the logical level and data structure is in the implementation level ‘As you can see, ADT is implementation independent. For example, it only describes what a data type List consists (data) and what are the operations it can perform, but it has no information about how the List is actually implemented. Whereas data structure is implementation dependent, as in the same example, it is about how the List implemented i.c., using array or linked list. Ultimately, data structure is how we implement the data in an abstract data type, 19Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Chapter 3 Queue Queue is the concept used in data structures. It is also referred to the linear data structure as the object or item can be added in one terminal and the item can be retrieved from the other end. Item, which is added to one end, is called as REAR and the item that is retrieved from the other end is. called as FRONT. Queue is used in array as well as in linked list of the computer programs mainly used by the programmers. Queue follows the concept of FIFO (First-In-First-Out). It means that the items, which are enters first will be accessed or retrieved first. Best Example The best example to represent the queue is the print jobs. Consider the systems are connected in the network with the common print using the print share methodology. So, whenever the users give their documents for printing, the jobs will be stored in a queue and the job which first enters the print queue will be printed first, which compiles the concept of queue FIFO. Queue Operations The following are operations performed by queue in data structures ‘© Enqueue (Add operation) © Dequeue (Remove operation) Enqueue This operation is used to add an item to the queue at the rear end. So, the head of the queue will be now occupied with an item currently added in the queue. Head count will be incremented by one after addition of each item until the queue reaches the tail point. This operation will be performed at the rear end of the queue. Dequeue 20Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT This operation is used to remove an item from the queue at the front end. Now the tail count will be decremented by one each time when an item is removed from the queue until the queue reaches the head point. This operation will be performed at the front end of the queue. Let us now consider the following example of using the operation Enqueue and Dequeue. A queue of an array A [3] is initialized and now the size of the queue is 3 which represents the queue can hold a maximum of 3 items. The enqueue operation is used to add an item to the queue. Enqueue (3) — This will add an item called 3 to the queue in the front end. (rear count will be incremented by 1) Again we are adding another item to the queue Enqueue (5) ~ This will add an item called 5 to the queue (rear count will be incremented by 1) Again we are adding the last item to the queue Enqueue (8) ~ This will add an item called 8 to the queue (Now the queue has reached its maximum count and hence no more addition of an item is possible in the queue) ‘Now dequeue operation is performed to remove an item from the queue. Dequeue () ~ This will remove the item that has been added first in the queue, ice, the item called 3 by following the concept of FIFO. Now the queue consists of the remaining items 5 and & in which the object 5 will be in the front end. The dequeue operation continues until the queue is reaching its last element. Queue Applications In the computer environment, the below areas where the queue concept will be implemented: ‘¢ Print queue — Jobs sent to the printer © Operating system maintain queue in allocating the process to each unit by storing them in buffer © The interrupts that occurs during the system operation are also maintained in queue ‘© The allocation of memory for a particular resource (Printer, Scanner, any hand held devices) are also maintained in queue. Program to implement queue using array ifinclude 21Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT #include #t define MAX_SIZE 10 class queues { int front,rear; int queue[MAX_SIZE]; public queues) —_// Constructor { } void insert_rear( int); void delete_front(); void display(); b void queues::insert_rear(int item) { Ii(rear>=MAX_SIZE-1) { cout<<"Queue is fulll\nOverflow"; t else { rear-rear+1; queuefrear]=item; } } void queues::delete_front() t if{front> rear) { cout<<"Queue is empty!\nUnderflow"; } else { cout<<"\nltem deleted."<=front;ptr--) ‘cout<>choice; switch(choice) { case 1: cout<<"How many clements are in the queue: "; cin>>length; cout<<"Enter "<>element; ql.insert_rear(element); } ql.display(); getch(); break; cease 2: ql.delete_front(); ql.display(); getch(); break; case 3: gl.display(); getch0;Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT break; case 4: exit(0); break; default; cout<<" geteh(); break; Please re-enter tour choice."; 3 getch(); } Circular queue Ina standard queue data structure re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is connected back to the first node to make a circle. Circular linked list fallow the First In First Out principle Elements are added at the rear end and the elements are deleted at front end of the queue Both the front and the rear pointers points to the beginning of the array. It is also called as “Ring buffer”. Items can inserted and deleted from a queue in O(1) time, Using array In arrays the range of a subscript is 0 to n-1 where n is the maximum size. To make the array as a circular array by making the subscript 0 as the next address of the subscript n-1 by using the formula subscript = (subscript +1) % maximum size. In circular queue the front and rear pointer are updated by using the above formula. The following figure shows circular array FM, RO Algorithm for Enqueue operation using array Step 1. start Step 2. if (front = (rear+1)%max) Print error “circular queue overflow “ Step 3. else 24Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT { rear = (rear*1)%max Qlrear] = element; If (front == -1) f= 0; } Step 4. stop Algorithm for Dequeue operation using array Step 1. start Step 2. if ((front = rear) && (rear = -1)) Print error “circular queue underflow Step 3. else {element = Q[front] If (front == reat) front=rear = Else Front = (front + 1) % max t Step 4. stop Program to implement Circular queue using array ifinclude class equeue { private : int *arr; int front, rear ; int MAX; public : ‘equeue( int maxsize void addq (int item ) ; int delq() ; void display()) ; i equeue :: equeue( int maxsize ) { MAX = maxsize ; arr = new int [ MAX ]; front = rear =-1; for (int i= 0 ;1 {J array has been declared as global so that other functions can also have access to it int arr[5]; {! function prototype void a_insert(int, int); void a_delete(int); void main(void) { int ch; int num,pos; while(ch!=4) { 31Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT cout<<" I> Insert"; cout<<"\n2> Delete"; cout<<"\in3> Show"; cout<<"ind> Quitin"; cin>>eh; switch(ch) { case 1 cout<<"enter element:"; cin>>num; cout<<"enter pos.:"; cin>>pos; a_insert(num,pos); break; case 2: ‘cout<<"enter pos.:"; cin>>pos; a_delete(pos); break; case 3: cout<<"inArray:"; for(int i=0;i<5;i—+ cout<=pos arr{i]=arr[i-1]; arr(i}=num; } // deletion funetion void a_delete(int pos) { for(int i=pos; i<=45i++) arr[i-l]=arr{i}; ~) 32Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT arr[i-1]-0; 3 Linked list A linked list is a dynamic data structure. It is an ideal technique to store data when the user is not aware of the number of elements to be stored. The dynamic implementation of list using pointers is also known as linked list. Each clement of the list is called as node, Each element points to the next element. In the linked list a node can be inserted or deleted at any position. Each node of linked list has two components. The first component contains the information or any data field and second part the address of the next node. In other words, the second part holds address of the next element. This pointer points to the next data item, The pointer variable member of the last record of the list is generally assigned a NULL value to indicate the end of the list Linked lists can be represented in memory by two ways they are © Using array method © Using pointer method Array method: In array method all the elements are stored in the continuous memory locations. It is having following disadvantages they are © It follows static memory allocation. # It is not possible to extend the size of the array at runtime ‘© Due to static memory allocation some memory space will be wasted. Pointer method: In pointer method all the data elements are represented using nodes. Each node is having data item and pointer to the next node. The elements in the list need not occupy continuous memory locations. The advantages of this method are ¢ Efficient memory management is possible, i.e., due to dynamic memory allocation the memory is not wasted It is possible to add or delete an element any ware in the list Itis dynamic in nature It is possible to handle a list of any size It is possible to extend the size of a list at runtime Various operations performed on lists: The operations performed on lists are Inserting a new element at the given position. Delete the element from the given position Find the length of the list Read the list from left to right Retrieve the ith element Copy a list awbeNeLecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT 7. Sort the elements in either ascending or descending order 8. Combine 2 or more list Single Linked list Single Linked list is a linear data structure. It is used as a fundamental data structure in computer programming. It contains a collection of nodes which are connected by only one pointer in one direction. Each node is having two parts the first part contains the data and second part contains the address of the next node. The first part is called data field or information field and the second part is called as link field or next address field. The graphical representation of linked list is start D he} fa ie Fad int node Las Hear the pointer start always points to the first node of a list and the end node is represented by special value called NULL. ‘Need for linked representation: The following problem arises when it is implemented by using arrays © Wastage of storage ¢- Itis not possible to add or delete in the middle of a list without rearrangement © Itis not possible to extend the size of a list, © To overcome all the above problem by implementing the list using linked representation. In linear lists insertion and deletion operations are inexpensive. Operations applied on single linked list: The basic types of operations applied on single linked list are Inserting a new element at the given position Delete the element from the given position Find the length of the list Read the list from left to right Retrieve the ith element Copy a list Sort the elements in either ascending or descending order Combine 2 or more list Algorithm to add an element to an existing list: It is possible to add an element to an existing list in three ways they are © Add at the front © Add at end of list © Add at position Assumptions: © start is a pointer which always points to the first node of a list ¢ next stands for next node address 34Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Add at the front of a list Step!: create a new node Step2: newnode->next = start Step3: start = newnode start —of1 Ka newnod = —+[4 start —of4 all byf2 New node Add at the end of Step]: create a new node (newnode) Step2: t= start Step3: while (t->next Step3: t>next = newnode stat —ofi bk ] newnod —+[4 start —of1 }[2 bola ] New node Add after a node of a list (position) Step1: create a new node (newnode) Step2: read the position of the node p; Step3: t= start Step4: traverse the list up to position as for (i=1; inext; Step4: newnode->next = t->next; Step5: t>next = newnode 35Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Algorithm for delete an element from the list Itis possible to delete an element from an existing list in three ways © Delete at front © Delete at end © Delete at a position Delete at front: Step]: t1 = start Step2: start = start->next Step3: delete (t1) «et SET ED bE start —»j2 +4 TS Delete at end: Step]: t= start; Step2: traverse the list up to n-1 nodes as For (I=1; [< t=" t">next Step3: tI= t>next; Step4: t->next = t>next->next; Step5: delete (tI) Delete at position: Step]: read the position of the deleted node p Step2: traverse the list upto p-1as For (i=1;inext; Step3: tl = t>next; Step4: t->next= t->next->next StepS: delete (t1) delete a node at position 2 36Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Drawbacks of a single linked lis It is having only one pointer so that it is possible to traverse in only one way Double Linked list Double Linked list is a fundamental data structure used in computer programming. It consists of a sequence of nodes connected by two pointers in both directions. Each node is having three parts the first part contains the address of previous node and second part contains data and third part contains address of next node. The first and third part is called address fields and the second part is data field. The start pointer always points to the first node of a list. The graphical representation of a node structure shown in the fig ogee aF [me Lied ss se a “t From the above fig the node is containing 2 pointers. © Pointer] is pointing to the previous node ‘© Pointer? is pointing to the next node. tg Hel Rib ei et eee at Doubly linked list can be represented as above fig. in doubly linked list it is possible to traverse both, forward & backward directions. It is also called two way lists. Operation applied on double linked list: © Inserting an element Delete element from the list Find the length of the list Read the list from left to right or right to left Copy a list Sort the elements in either ascending or descending order Combine 2 or more list Search alist Algorithm to add an element to an existing list: 37Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT It is possible to add element to an existing list in three ways they are add at the front, add at the end of the list, add after a node of the existing list. Assumption: start always contains the current list start node address. >next stands for next node address LR « -ZTSIN wt Add node at the front of a list Stepl. Create a new node Step2. n->right = start Step3. start->left =n Step4. start a sat —a = Ss Add node at the end of a list Stepl. Create a new node Step2. t= start where t is a temporary variable Step3. Traverse the tree until t->right = null Step4. t>right =n Step5. n>left a TOSI ent 7 TTT ST TT NT Add node after a particular position or a node Step]. Create a new node. Step2. t = start where t is a temporary pointer variable Step3. Read position p from console. Step4. Traverse the list until the position p Step5. if not found the position error “no such node exist “: Step6. n->right = p->right Step7. Steps. Step9. ul start —>| > Insert node after second (2) node 38Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT ee 7ST STN on ZOOS COS x Program to implement singly linked list #include #include class list { struct node { int data; struct node *next; Mp: public: list; void append(int); void addatbeg( int); void addatanyloc(int, int); void addatend(int); void delatbeg(); void delatend(); void delatanyloc(int); void display(); i list:list) { p=NULL; $ void list::append(int item) { struct node *q, *t; if(p-=NULL) { p-new node; p->data =item; p->next=NULL; t else 39Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT { =P: while(q>next! { } t=new node; t->data=item; t->next=NULI qenext } } void list::addatbeg(int item) { struct node *q; grnew node; qe>dataitem; qenext=p; pa } void list:: addatanyloc(int item, int loc) { struct node *q,*t; P; for(int i-1; isloc; i++) { q=q->next; $ t-new node; t->data=item; te>next=q->next; qene } void list::addatend(int item) { struct node *q, *t; 7 while(q>next!=NULL) q-q->next; t-new node; t->data=item; t->next=NULL; qp>next=t; } NULL) qrq->next; 40Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT void list::delatbeg() { struct node *q; 4 4 delete q; >next; } void list::delatend() { struct node *q,*t - while(q->next! t ta: g=q->next; } t->next=NULL; delete q; NULL) void list::delatanyloc(int loc) { struct node *4,*t; ran for(int i-1; isloo; i+4) t>next=g->next; delete q; $ void list::display0, { struct node *q; cout<datac<" "; gra>next; } } 41Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT void main() { list I; cout<<"first node"< #include class list t struct node { a2Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT int data; struct node *next, *prev; list; void appendtint); void addatbeg( int); void addatanyloc(int, int); void addatend(int); void delatbeg(); void delatend(); void delatanyloc(int); void display(); h list:listO PNUL Ly vi list::append(int item) struct node *q, *t; if(p-=NULL) { penew node; p->data =item; p->next=NULL; p->prev-NULL; t else { - while(q>next!=NULL) { } t=new node; t->dataitem; t>next=NULL; te>prev=q; qenext 3 } void list::addatbeg(int item) qrqenext;Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT t struct node *q qrnew node; q->data=item; g>next=p; Pa void list:: addatanyloc(int item, int loc) { struct node *q,*t; Pp: for(int =1; idatar t>prev= qe>next->prev=t; qe: } void list::addatend(int item) { struct node *q, *t; = while(q->next!=NULL) q-q->next; data=item; t->next=NULL; t>prev=q; q->next=t; 3 void list::delatbeg() t struct node *q; ray peq->next; p->prev=NULL delete q; } void list::delatend() 44Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT t struct node *q,*t; Cay while(q->next!=NULL) t->next=NUL delete q; } void list::delatanyloc(int loc) { struct node *4,*t; =P for(int i=1; inext->prev=q->prev; delete q; 3 void list::display() { struct node *q) cout<data<<"->"; qrq>next; } cout<<"NULL"; } void main() { list I; cout<<"first node"< #include class stack t struct node { int data; struct node *next; Prtos; public: stack(); void push(int); void pop(); 46Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT void display(); u stack::stack() { tos-NULL; void stack::pushtint item) { struct node *p; p= new node; p->data = item; p->next = NULL; if(tos!=NULL) { p->next = tos; + tos =p; t void stack::pop() { struct node *q; s-=NULL) -<"\nThe stack is Empty"<next; cout<<"\nThe value popped is "<data<data<next; } i } void main() { stack s; s.push(10); s.display(); cout< finelude class queue { struct node { int data; struct node *next; }*front,*rear; 48Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT public: queue(); void enqueue(int); void dequeue(); void display(); queue::queue() { front=rear-NULL; } void queue::enqueue(int item) { struct node *p; p= new node; p->data = item; p->next = NULL; if{fiont—=NULL) { front=p; } if(rear!=NULL) { rear->next = p; } rear =p; } void queue::dequeue() { struct node *q; if(front==NULL) 49Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT cout<<"\nThe queue is Empty"<next; cout<<"\nThe value popped is "<data< fro if{front—=NULL) { cout<<"\nNothing to Display\n"; } else t cout<<"\nThe contents of Queueln"; while(p!=NULL) { cout<data<<" " po p-next; + t } void main() { queue q; qeenqueue(10); 50Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT adisplay(); ndl; q.enqueue(20); cout< qeenqueue(30); q.enqueue(40); g.enqueue(50); adisplay(); q.dequeue(); q.display(; q.dequeue(); a.display(; q.dequeue(); a.display; getch(); } Chapter Recursion A recursive method is a method that calls itself either directly or indirectly There are two key requirements to make sure that the recursion is successful: + Every recursive call must simplify the computation in some way. «There must be special cases to handle the simplest computations. Iteration Vs. Recursion «Ifa recursive method is called with a base case, the method returns a result. If a method is called with a more complex problem, the method divides the problem into two or more conceptual pieces: a piece that the method knows how to do and a slightly smaller version of the original problem, Because this new problem looks like the original problem, the method launches a recursive call to work on the smaller problem. © For recursion to terminate, each time the recursion method calls itself with a slightly simpler version of the original problem, the sequence of smaller and smaller problems must converge on the base case, When the method recognizes the base case, the result is returned to the previous method call and a sequence of retums ensures all the way up the line until the original call of the method eventually returns the final result. © Both iteration and recursion are based on a control structure: Iteration uses a repetition structure; recursion uses a selection structure. © Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated method calls 31Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT © Iteration and recursion each involve a termination test: Iteration terminates when the Joop-continuation condition fails; recursion terminates when a base case is recognized. © Iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case. n repeatedly invokes the mechanism, and consequently the overhead, of method scan be expensive in both processor time and memory space. The advantages and disadvantages of the two are not always obvious, and you should really take it on a case-by-case basis. When in doubt: test it. But generally: 1. Recursion may be slower, and use greater resources, because of the extra function calls, 2. Recursion may lead to simpler, shorter, easier-to-understand functions, especially for mathematicians who are comfortable with induction formulae. Either way, one of the most critical aspects of writing either a recursive or an iterative function is to have an exit clause (or "base case" for recursions) that is checked at every recursiorviteration and is guaranteed to be reached at some finite point, given any input. Otherwise you will get either Infinite Recursion: More and more functions being spawned, never closing, using up resources until there are none left, possibly crashing the system. Infinite loop: A loop that cycle forever, burning CPU and never completing. Recursive Fibonacei Fibonacci can be defined recursively as follows. Each number is the sum of the previous two ‘numbers in the sequence. The 7 Fibonacei number is Fib(n) = Fib(n-1) + Fib(n-2) Fib(0) = 1, Fib(1) = 1. That is, the n® number is formed by adding the two previous numbers together. The equation for Fib(n) is said to be the recurrence relation and the terms for Fib(0) and Fib(1) are the base cases. The code for the recursive Fibonacci sequence is provided in Figure 3 below. int Fib (int n) { if (n<=1) return 0; else return ( Fib(n-1) + Fib(n-2) ); i Fibonacci in C To find Fib(n) you need to call Fib two more times: once for Fib(n-1) and once more for Fib(n-2); then you add the results. But to find Fib(n-1), you need to call Fib two more times: once for 52Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT and once more for Fib(n-3); then you need to add the results. And so on! You can see the recursion tree for Fib(n) in Figure 4. The recursion tree shows each call to Fib() with different values for n. Fib(r-2) {/— Fib(n-3) Fib(n-4) Figure 4: The recursion tree for Fib(). Click to enlarge For example, consider Fib(5), the fifth term in the sequence. To find Fib(5), you would need to find Fib(4) + Fib(3). But to find Fib(4), you would need to find Fib(3) + Fib(2). Luckily, Fib(2) is a base case; the answer to Fib(2) is 1. And so on. Look at Figure 5 for an example recursion tree for Fib(5) ~ it lists all of the computations needed to carry out the calculation recursively. 53Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Fib(6) Fib(d Fi) oo \ Fib(3) Fib(2) Fib(2) ‘The recursion tree for Fib(5). Base cases are highlighted in blue. It may help to visualize the nested instances of the series of recursive calls for Fib(S) in a sort of table. Figure 6 shows the recursive calls for Fib(5), with each call generating two subtables. The call to FibQ returns when both subtables have been worked down to their respective base cases, and the return value is propagated up the tree (down the table). IFib(S) — Fib(4) + Fib(3) FFib(4) = Fib(3) + Fib(2) Fib(3) ~ Fib(2) + Fib(1) Fib(2) = Fib(1) + Fib(0) D=1 FiO Fib(2) = Fib(1) + Fib(0) Fib(1)= 1 FBC) = 1 Fib(O)= 1 | FBC =1 FBO =T | papa) = Retum 1 Retum1 Retum1 || |Retum1 Return 1 |p a Return 1 =141 E1+t pRetwmn 2 Return 2 tum 2 =241 =2+1 Retum 3 Rewns = 3+2 Return 5 34Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT =543 Return 8 Figure Nested calls to Fib for Fib (5) Iterative Fibonacei The Fibonacci sequence can be defined iteratively by describing how to obtain the next value in the sequence. That is, if you start at the base cases of Fib (0) = Fib (1) = 1, you can build the sequence up to Fib (n) without using recursive calls. For example, calculating Fib (5) may go as follows. Fib(0) = 1 Fib(1)=1 Fib(2) = Fib(1) + Fib(0) = 1+ 1=2 Fib(3) = Fib(2) + Fib(1)=2 +1=3 Fib(4) = Fib(3) + Fib@2)=3 +2=5 Fib(5) = Fib(4) + Fib3)=5 +3=8 A\ll that is needed for this calculation is a while loop! RECURSION VS. ITERATION We have studied both recursion and iteration. They can be applied to a program depending upon the situation, Following table explains the differences between recursion and iteration. Recursion Vs. Iteration Recursion Iteration Recursion is the term given to the mechanism of defining a set or procedure in terms of itself. [The block of statement executed repeatedly using loops. A conditional statement is required in the body lof the function for stopping the function execution, IThe iteration control statement itself contains |statement for stopping the iteration, At every lexecution, the condition is checked. |At some places, use of recursion generates extra Joverhead. Hence, better to skip when easy solution is available with iteration. |All problems can be solved with iteration. [Recursion is expensive in terms of speed and memory. Iteration does not create any overhead. All the programming languages support iteration, 35Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT ADVANTAGES & DISADVANTAGES OF RECURSION Advantages of recursion, 1. Sometimes, in programming a problem can be solved without recursion, but at some situations in programming it is must to use recursion. For example, a program to display the list of all files of the system cannot be solved without recursion, 2. The recursion is very flexible in data structure like stacks, queues, linked list and quick sort, Using recursion, the length of the program can be reduced Chapter 6 Trees Basics Some basic terminology for trees: + Trees are formed from nodes and edges. Nodes are sometimes called vertices. Edges are sometimes called branches. «Nodes may have a number of properties including value and label. # Edges are used to relate nodes to each other. In a tree, this relation is called "parenthood." + An edge {a,b} between nodes a and b establishes a asthe parent of b. Also, bis. called a child of a. # Although edges are usually drawn as simple lines, they are really directed from parent to child, In tree drawings, this is top-to-bottom. + Informal Definition: a iree is a collection of nodes, one of which is distinguished as "root," along with a relation ("parenthood") that is shown by edges. «Formal Definition: This definition is "recursive" in that it defines tree in terms of itself. The definition is also "constructive" in that it describes how to construct a tree. 1. Asingle node is a tree. It is "root." 2. Suppose N is a node and T;, T:, ..., T, are trees with roots ny, np, ....m, respectively. We can construct a new tree T by making N the parent of the nodes m, 1s, ... Mh Then, N is the root of T and T,, T,, .... T, are subtrees. 56Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT The tree T, constructed using k subtrees More terminology A node is either internal or itis a leaf. A leafs a node that has no children. Every node in a tree (except root) has exactly one parent. The degree of a node is the number of children it has The degree ofa tree is the maximum degree of all of its nodes. Paths and Levels * Definition: A path is a sequence of nodes nj, ny, ...m such that node n, is the parent of node ng, for all 1 <=i1 10. Because both the left and right subtrees of a BST are again search trees; the above definition is recursively applied to all internal nodes: Exercise. Given a sequence of numbers: 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31 61Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Draw a binary search tree by inserting the above numbers from left to right. Searching Searching in a BST always starts at the root, We compare a data stored at the root with the key we are searching for (let us call it as toSearch). If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise - to the right child. The recursive structure of a BST yields a recursive algorithm, Searching in a BST has Oh) worst-case runtime complexity, where his the height of the tree. Since s binary search tree with n nodes has a minimum of O(log n) levels, it takes at least O(log n) comparisons to find a particular node. Unfortunately, a binary serch tree can degenerate to a linked list, reducing the search time to O(n), Deletion Deletion is somewhat more tricky than insertion. There are several cases to consider. A node to be deleted (let us call it as toDelete) # isnot in a tree; * isaleaf, # has only one child; © has two children. IftoDelete is not in the tree, there is nothing to delete. If toDelete node has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted 62Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT before deletion after deletion Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two sub-trees and therefore, some children of the internal node won't be accessible after deletion, In the picture below we delete 8: before deletion after deletion Deletion starategy is the following: replace the node being deleted with the largest node in the left subtree and then delete that largest node. By symmetry, the node being deleted can be swapped with the smallest node is the right subtre Given a sequence of numbers: 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31 Draw a binary search tree by inserting the above numbers from left to right and then show the two trees that can be the result after the removal of 11 63Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Binary search tree Adding a value Adding a value to BST can be divided into two stages: © search for a place to put a new element; insert the new element to this place. Let us see these stages in more detail Search for a place At this stage an algorithm should follow binary search tree property. If a new value is less, than the current node's value, go to the left sub-tree, else go to the right su-btree. Following this simple rule, the algorithm reaches a node, which has no left or right subtree, By the moment a place for insertion is found, we can say for sure, that a new value has no duplicate in the tree. Initially, a new node has no children, so it is a leaf. Let us see it at the picture. Gray circles indicate possible places for a new node. (2) (18) C4) (3) 64Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Now, let’s go down to algorithm itself, Here and in almost every operation on BST recursion is utilized. Starting from the root, 1. check, whether value in current node and a new value are equal. If so, duplicate is found. Otherwise, 2. if'a new value is less, than the node's value: © fa current node has no left child, place for insertion has been found; © otherwise, handle the left child with the same algorithm, 3. if new value is greater, than the node's value: © ifa current node has no right child, place for insertion has been found; © otherwise, handle the right child with the same algorithm, Just before code snippets, let us have a look on the example, demonstrating a case of insertion in the binary search tree. Example Insert 4 to the tree, shown above. 65Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Binary search tree. Removing a node Remove operation on binary search tree is more complicated, than add and search. Basically, in can be divided into two stages: © search for a node to remove; «if the node is found, run remove algorithm. Remove algorithm in detail Now, let’s see more detailed description of a remove algorithm. First stage is identical to algorithm for lookup, except we should track the parent of the current node. Second part is more tricky. There are three cases, which are described below. 1. Node to be removed has no children. This case is quite simple, Algorithm sets corresponding link of the parent to NULL and disposes the node. Example. Remove -4 from a BST. 66Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT (2) (8) 4 © 2. Node to be removed has one child. It this case, node is cut from the tree and algorithm links single child (with it's subtree) directly to the parent of the removed node. Example, Remove 18 from a BST. 67Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT OOD ® 3. Node to be removed has two children. This is the most complex case. To solve it, let us see one usefull BST property first, We are going to use the idea, that the same set of values may be represented as different binary-search trees. For example those BSTs: 68Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT contains the same values {5, 19, 21, 25}. To transform first tree into second one, we can do following: choose minimum element from the right sub-tree (19 in the example); © replace 5 by 19; © hang 5 asa left child. The same approach can be utilized to remove a node, which has two children: © find a minimum value in the right sub-tree; replace value of the node to be removed with found minimum, Now, right sub-tree contains a duplicate! © apply remove to the right sub-tree to remove a duplicate Notice, that the node with minimum value has no left child and, therefore, it's removal may result in first or second cases only. Example, Remove 12 froma BST. 69Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT (2) 12) OQ ®O® gg @ © Find minimum clement in the right sub-tree of the node to be removed. In current example it is 19. (2) 12) OQ ®O® gg Replace 12 with 19. Notice, that only values are replaced, not nodes. Now we have two nodes with the same value. 70Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT (2) © OQ ®O® gg @ Remove 19 from the left sub-tree. {/Binary Search Tree Program include #include using namespace std; class BinarySearchTree { private: struct tree_node { tree_node* left; 1Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT tree_node* right; int data; h tree_node* root; public: BinarySearchTree() { root = NULL; + bool isEmpty() const { return root—=NULL; } void print_inorder(); void inorder(tree_node*); void print_preorder(); void preorder(tree_node*); void print_postorder(); void postorder(tree_node*); void insert(int); void remove(int); h i Smaller elements go left I Jarger elements go right void BinarySearchTree::insert(int d) { tree_node* t = new tree_node; tree_node* parent; t>data = d; t left = NULL; NULL; NULL; //is this a new tree? ifisEmpty0) root else { //Note: ALL insertions are as leaf nodes tree_node* curr, curr= root; // Find the Node's parent. while(curr) { parent = curr; if{t->data > curr->data) curr = curr->right; else curr = curr>left; 2Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT t ifft->data < parent->data) parent->left else parent->right } } void BinarySearchTree::removetint d) { //Locate the element bool found = false; iftisEmpty() { cout<<" This Tree is empty! "<data = d) { found = true; break; } else { parent = curr, if{d>curr->data) curr = curr->right; else curt = curr>left; 3 t if{{found) cout<<" Data not found! "<left = NULL && curr>right != NULL)]| (curr->left != NULL && curr>right = NULL)) t if(cur->left = NULL && curr>right ! { if(parent>left = curt) { parent->left = curr->right; delete curr; } else { parent->right = curr->right; delete curr; t } else // left child present, no right child { if{parent>left = curr) { parent->left = curr->left; delete curr; } else { parent->right = curr->left; delete curr, } } return; t ULL) JNWe're looking at a leaf node if{ curr>left == NULL && curr->right NULL) { if(parent>left == curr) parent>left = NULL; else parent->right = NULL; delete curr; retum; 74Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT //Node with 2 children / replace node with smallest value in right subtree if (cun->left != NULL && curr->right ! NULL) { ‘tree_node* chkr; chkr = curr->right; if((chkr->left == NULL) && (chkr->right == NULL)) { curr = chkr; delete chkr; curr->right = NULL; } else // right child has children { ‘if the node's right child has a left child /! Move all the way down left to locate smallest element if\(curr>right)->Ieft != NULL) { tree_node* leurr; tree_node* leurp; loump = curr>right; leurr = (cun->right)->left; while(leurr->left != NULL) { Iourrp = lourr; Teurr = Icurr->left; } curr>data = leurr->data; delete leurr; leurrp->left = NULL; } else { tree_node* tmp; tmp = curr>right; curr->data = tmp->data; return; 15Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT void BinarySearchTree::print_inorder() { inorder(root); t void BinarySearchTree::inorder(tree_node* p) { if ! { iffp->teft) inorder(p>left); cout<<" "<

datac<" "; ifp->right) inorder(p->right); } else return; t ULL) void BinarySearchTree::print_preorder() { preorder(root); } void BinarySearchTree::preorder(tree_node* p) { if(p != NULL) { cout<<" "<left) preorder(p->tleft); if{p->right) preorder(p->right); } else return; } void BinarySearchTree::print_postorder() { postorder(root); t void BinarySearch'Tree::postorder(tree_node* p) { if(p != NULL) { if(p>left) postorder(p>lef); if{p->right) postorder(p->right); cout<<" "<data<<' } 16Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT else return; } int main() { BinarySearchTree b; int ch,tmp,tmp1; while(1) { cout<>ch; switeh(ch) { case | : cout<<" Enter Number to be inserted cin>>tmp; b.insert(tmp); break; case 2 : cout<>tmp1; b.remove(tmp1); break; case 6 1Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT return 0; Rebuild a binary tree from Inorder and Preorder traversals This is a well known problem where given any two traversals of a tree such as inorder & preorder or inorder & postorder or inorder & levelorder traversals we need to rebuild the tree. The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree: Preorder traversal visits Node, left subtree, right subtree recursively © Inorder traversal visits left subtree, node, right subtree recursively Since we know that the first node in Preorder is its root, we can easily locate the root node in the inorder traversal and hence we can obtain left subtree and right subtree from the inorder traversal recursively Consider the following example: Preorder Traversal: 1 2 4 8 9 10 11 5 3 67 Inorder Traversal: 8 4 109 1125163 7 Iteration 1: Root — {1} Left Subtree — {8,4,10,9,11,2,5} Right Subtree — {6,3,7} 8Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Iteration 2: [Root — {2} [Root — {3} [Left Subtree — {8,4,10,9,11} [Left Subtree - {6} ight Subtree ~ {5 IRight Subtree ~ {7 Iteration 3: [Root - {2} ‘oot — {3} lLeft Subtree ~ {8,4,10,9,11} [Left Subtree — {6} IRight Subtree — {5 Right Subtree — {7} [Root — {4} [Done jone Left Subtrec ~ (8) Right Subtree 10,9,11 Iteration 4: 79Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT FRoot — {2} [Root — {3} ILeft Subtree — {8,4,10,9,11} [Left Subtree ~ {6} IRight Subtree — {5 IRight Subtree — {7 IRoot — {4} [Done [Done [Left Subtree — {8} Right Subtree 4 10,9,11 [Done IR- {9} [Done [Done left ST 4 {10} IRight IST-{11 Given inorder and postorder traversals construct a binary tree Let us consider the below traversals, Inorder sequence: D BE AF C Postorder sequence: DEB FC A Ina Postorder sequence, rightmost element is the root of the tree. So we know A is root. Search for A in Inorder sequence, Once we know position of A (or index of A) in Inorder sequence, we also know that all elements on left side of A are in left subtree and elements on right are in right subtree. 80Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT A rN iN DBE FC Let i be the index of root (i is 3 in the above case) in Indorder sequence. In Inorder sequence, everything from 0 to i-1 is in left subtree and (i-1)th element in postorder traversal is root of the left subtree. If i-1 <0 then left child of root is NULL In Inorder sequence, everything from (i+1) to (n-1) is in right subtree and (n-1)th element is the root of right subtree. If n-1 is equal to i then right child of root is NULL Recursively follow above steps, and we get the tree shown below. oN ao ae Examples An important example of AVL trees is the behaviors on a worst-case add sequence for regular binary trees: 1,2,3,4,5,6,7 All insertions are right-right and so rotations are all single rotate from the right. All but two insertions require rebalancing: at 1 2 at 3 = > 81Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT a2s ats It can be shown that inserting the sequence 1,...2°"'=1 will make a perfect tree of height n. Here is another example. The insertion sequence is: 50, 25, 10, 5, 7, 3, 30, 20, 8, 15 9) cn és 22 (25) double (25) @ QO @ @ single rot, left te) 25> 82Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT add(30), add(20), add(8) need no rebalancing double rot. right atT> The AVL Tree Rotations 1. Rotations: How they work A tree rotation can be an intimidating concept at first. You end up in a situation where you're juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what's going on with any of the sub-trees which are attached to the nodes you're fumbling with, but that can be hard. Left Rotation (LL) Imagine we have this situation: Figure 1-1 a \ b \ To fix this, we must perform a left rotation, rooted at A. This is done in the following steps: b becomes the new root,Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT a takes ownership of b's left child as its right child, or in this case, null. b takes ownership of a as its left child. The tree now looks like this: Figure 1-2 b N ac Right Rotation (RR) A right rotation is a mirror of the left rotation operation described above, Imagine we have this situation: Figure 1-3 © f b i a To fix this, we will perform a single right rotation, rooted at C, This is done in the following steps: b becomes the new root c takes ownership of b's right child, as its left child. In this case, that value is null. b takes ownership of c, as it's right child The resulting tree: Figure 1-4 b iN ac Left-Right Rotation (LR) or "Double left" Sometimes a single left rotation is not sufficient to balance an unbalanced tree. Take this situation: Figure 1-5 a \ © Perfect. It's balanced. Let's insert’ 84Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT Figure 1-6 a © i b Our initial reaction here is to do a single left rotation. Let's try that. Figure 1-7 c / a \ b Our left rotation has completed, and we're stuck in the same situation. If we were to do a single right rotation in this situation, we would be right back where we started. What's causing this? The answer is that this is a result of the right subtree having a negative balance. In other words, because the right subtree was left heavy, our rotation was not sufficient. What can we do? The answer is to perform a right rotation on the right subtree. Read that again. We will perform a right rotation on the right subtree. We are not rotating on our current root. We are rotating on our right child. Think of our right subtree, isolated from our main tree, and perform a right rotation on it Before: Figure 1-8 © / b After: Figure 1-9 b \ After performing a rotation on our right subtree, we have prepared our root to be rotated left, Here is our tree now: Figure 1-10 a \ b 85Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT © Looks like we're ready for a left rotation. Let's do that: Figure 1-11 b N ac Voila. Problem solved. Right-Left Rotiation (RL) or "Double right” A double right rotation, or right-left rotation, or simply RL, is a rotation that must be performed when attempting to balance a tree which has a left subtree, that is right heavy. This is a mirror operation of what was illustrated in the section on Left-Right Rotations, or double left rotations. Let's look at an example of a situation where we need to perform a Right-Left rotation. Figure 1-12 © / a b In this situation, we have a tree that is unbalanced. ‘The left subtree has a height of 2, and the right subtree has a height of 0. This makes the balance factor of our root node, ¢, equal to -2. What do we do? Some kind of right rotation is clearly necessary, but a single right rotation will not solve our problem. Let's try it: Figure 1-13 a \ © / b Looks like that didn't work. Now we have a tree that has a balance of 2. It would appear that we did not accomplish much. That is true. What do we do? Well, let's go back to the original tree, before we did our pointless right rotation: Figure 1-14 c 1 86Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT a \ b The reason our right rotation did not work, is because the left subtree, or ‘a, has a positive balance factor, and is thus right heavy. Performing a right rotation on a tree that has a left subtree that is right heavy will result in the problem we just witnessed. What do we do? The answer is to make our left subtree left-heavy. We do this by performing a left rotation our left subtree. Doing so leaves. us with this situation: Figure 1-15 c i b / a This is a tree which can now be balanced using a single right rotation. We can now perform our right rotation rooted at C. The result: Figure 1-16 Balance at last. 2, Rotations, When to Use Them and Why How to decide when you need a tree rotation is usually easy, but determining which type of rotation you need requires a little thought. A tree rotation is necessary when you have inserted or deleted a node which leaves the tree in an unbalanced state. An unbalanced state is defined as a state in which any subtree has a balance factor of greater than 1, or less than -1. That is, any tree with a difference between the heights of its two sub-trees greater than 1, is considered unbalanced. This is a balanced tree: Figure 2-1 I N 87Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT This is an unbalanced tree: Figure 2-2 This tree is considered unbalanced because the root node has a balance factor of 2. That is, the right subtree of 1 has a height of 2, and the height of I's left subtree is 0, Remember that balance factor of a tree with a left subtree A and a right subtree B is, B-A Simple. In figure 2-2, we see that the tree has a balance of 2. This means that the tree is considered "right heavy". We can correct this by performing what is called a "left rotation". How we determine which rotation to use follows a few basic rules. See psuedo code: IF tree is right heavy { IF tree's right subtree is left heavy { Perform Double Left rotation } ELSE { Perform Single Left rotation 3 } ELSE IF tree is left heavy { IF tree's left subtree is right heavy { Perform Double Right rotation } ELSE { Perform Single Right rotation 88Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT As you can see, there is a situation where we need to perform a "double rotation". A single rotation in the situations described in the pseudo code leave the tree in an unbalanced state. Follow these rules, and you should be able to balance an AVL tree following an insert or delete every time. B-Trees Introduction A Betree is a specialized multiway tree designed especially for use on disk. In a B-tree cach node may contain a large number of keys. The number of subtrees of each node, then, may also be large A B-tree is designed to branch out in this large number of directions and to contain a lot of keys in each node so that the height of the tree is relatively small. This means that only a small number of nodes must be read from disk to retrieve an item. The goal is to get fast access to the data, and with disk drives this means reading a very small number of records, Note that a large node size (with lots of keys in the node) also fits with the fact that with a disk drive one can usually read a fair amount of data at once. Definitions A.multiway tree of order mis an ordered tree where each node has at most m children. For each node, if k is the actual number of children in the node, then k - | is the number of keys in the node. If the keys and subtrees are arranged in the fashion of a search tree, then this is called a multiway search tree of order m. For example, the following is a multiway search tree of order 4, Note that the first row in each node shows the keys, while the second row shows the pointers to the child nodes. Of course, in any useful application there would be a record of data associated with each key, so that the first row in each node might be an array of records where each record contains a key and its associated data, Another approach would be to have the first row of each node contain an array of records where each record contains a key and a record number for the associated data record, which is found in another file. This last method is often used when the data records are large. The example software will use the first method. 89