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 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 2Lecture 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 byLecture 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 DefinitionsLecture 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 8Lecture 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 =0; cout > ch; switch(ch) { case 1: cout > 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, 14Lecture 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: 15Lecture 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. 16Lecture 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. 7Lecture 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 18Lecture 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, 19Lecture 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 20Lecture 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 21Lecture 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 rear) { cout=front;ptr--) ‘cout>choice; switch(choice) { case 1: cout>length; cout>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 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) { 31Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT cout Insert"; cout Delete"; cout Show"; cout Quitin"; cin>>eh; switch(ch) { case 1 cout>num; cout>pos; a_insert(num,pos); break; case 2: ‘cout>pos; a_delete(pos); break; case 3: cout=pos arr{i]=arr[i-1]; arr(i}=num; } // deletion funetion void a_delete(int pos) { for(int i=pos; inext = 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 35Lecture 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; [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 36Lecture 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: 37Lecture 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 38Lecture 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 39Lecture 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; 40Lecture 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; coutdatacnext; } } 41Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT void main() { list I; cout #include class list t struct node { a2Lecture 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() 44Lecture 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) coutdata"; qrq>next; } cout #include class stack t struct node { int data; struct node *next; Prtos; public: stack(); void push(int); void pop(); 46Lecture 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) -next; coutdatadatanext; } i } void main() { stack s; s.push(10); s.display(); cout finelude class queue { struct node { int data; struct node *next; }*front,*rear; 48Lecture 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) 49Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT coutnext; coutdata fro if{front—=NULL) { coutdata 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 61Lecture 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 62Lecture 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 63Lecture 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) 64Lecture 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. 65Lecture 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. 66Lecture 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. 67Lecture 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: 68Lecture 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. 69Lecture 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. 70Lecture 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; 1Lecture 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; 2Lecture notes on Data Structures And Algorithms, By Dilendra Bhatt, Assistant professor, NCIT t ifft->data data) parent->left else parent->right } } void BinarySearchTree::removetint d) { //Locate the element bool found = false; iftisEmpty() { coutdata = d) { found = true; break; } else { parent = curr, if{d>curr->data) curr = curr->right; else curt = curr>left; 3 t if{{found) coutleft = 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; 74Lecture 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; 15Lecture 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); coutdatacright) inorder(p->right); } else return; t ULL) void BinarySearchTree::print_preorder() { preorder(root); } void BinarySearchTree::preorder(tree_node* p) { if(p != NULL) { coutleft) 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); coutdata>ch; switeh(ch) { case | : cout>tmp; b.insert(tmp); break; case 2 : cout>tmp1; b.remove(tmp1); break; case 6 1Lecture 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} 8Lecture 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: 79Lecture 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. 80Lecture 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 81Lecture 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> 82Lecture 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’ 84Lecture 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 85Lecture 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 86Lecture 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 87Lecture 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 88Lecture 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