Data Structures and Algorithms in Python | Syed Mohiuddin | Skillshare

Data Structures and Algorithms in Python

Syed Mohiuddin

Play Speed
  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x
57 Lessons (5h 21m)
    • 1. Why Data Structures?

      1:53
    • 2. Python Installation

      1:56
    • 3. PyCharm Installation

      1:28
    • 4. Linear Search Algorithm

      2:44
    • 5. Implementing Linear Search Algorithm in Python

      3:24
    • 6. Recursion in Python

      4:09
    • 7. Binary Search Algorithm

      6:18
    • 8. Implementing Binary Search Algorithm in Python - Iteratively

      3:15
    • 9. Implementing Binary Search Algorithm in Python - Recursively

      2:40
    • 10. Algorithm Analysis - Time and Space Complexity

      12:34
    • 11. Abstract Data Type (ADT)

      0:59
    • 12. Stacks Introduction

      2:54
    • 13. Stacks Abstract Data Type (ADT)

      1:59
    • 14. Implementing Stacks using Arrays/Lists in Python

      7:45
    • 15. Queues Introduction

      1:14
    • 16. Queues Abstract Data Type (ADT)

      2:17
    • 17. Implementing Queues using Arrays/Lists in Python

      4:33
    • 18. Deques Introduction

      1:36
    • 19. Deque Abstract Data Type (ADT)

      1:57
    • 20. Implementing Deques using Arrays/Lists in Python

      5:26
    • 21. Linked List Introduction

      16:17
    • 22. Implementing Linked List in Python

      18:12
    • 23. Circular Linked List

      7:41
    • 24. Implementing Circular Linked List in Python

      13:15
    • 25. Doubly Linked List

      12:38
    • 26. Implementing Doubly Linked List in Python

      16:49
    • 27. Implementing Stacks using Linked List in Python

      5:38
    • 28. Implementing Queues using Linked List in Python

      5:05
    • 29. Implementing Deques using Linked List in Python

      2:53
    • 30. Trees - Definition and Properties

      7:41
    • 31. Binary Trees and it's Properties

      6:00
    • 32. Level Order Traversal of Binary Trees

      2:15
    • 33. Preorder Traversal of Binary Trees

      2:58
    • 34. Inorder Traversal of Binary Trees

      2:43
    • 35. Postorder Traversal of Binary Trees

      2:25
    • 36. Implementing Binary Tree using Linked Structure in Python

      12:11
    • 37. Binary Search Tree Property

      6:16
    • 38. Insertion and Deletion in Binary Search Trees

      4:29
    • 39. Implementing Binary Search Trees in Python

      11:33
    • 40. Priority Queues & Heaps Introduction

      3:20
    • 41. Heaps Abstract Data Type (ADT)

      6:03
    • 42. Implementing Heaps in Python

      8:55
    • 43. heapq Module in Python

      4:31
    • 44. Graphs Introduction

      5:44
    • 45. Graph Abstract Data Type (ADT)

      1:43
    • 46. Implementing Graphs in Python

      7:02
    • 47. Graph Traversal Algorithms

      8:38
    • 48. Implementing Breadth-First Search Algorithm in Python

      3:07
    • 49. Implementing Depth-First Search Algorithm in Python

      3:01
    • 50. Selection Sort Algorithm & Its Implementation in Python

      5:01
    • 51. Insertion Sort Algorithm & Its Implementation in Python

      4:49
    • 52. Bubble Sort Algorithm & Its Implementation in Python

      4:09
    • 53. Merge Sort Algorithm & Its Implementation in Python

      6:17
    • 54. Quick Sort Algorithm & Its Implementation in Python

      7:37
    • 55. Heap Sort Algorithm & Its Implementation in Python

      3:05
    • 56. Python's Built-in Sorting Functions

      4:46
    • 57. Asymptotic Notations Big-Oh, Omega & Theta

      4:54

About This Class

This course will help you in better understanding of the basics of Data Structures and how algorithms are implemented in the high level programming language. This course consists of lectures on data structures and algorithms which covers the computer science theory + implementation of data structures in python language. This course will also help students to face interviews at the top technology companies. This course is like having personal tutors to teach you about data structures and algorithms.

There’s tons of concepts and content in this course. To begin the course:

  • We have a discussion of why we need data structures.

  • Then we move on to discuss Analysis of Algorithms ie Time and Space complexity, though the Asymptotic Notation ie Big O, Omega and Theta are taken up at the end of this course so that you do not get confused and concentrate on understanding the concepts of data structures.

  • We have a programming environment set up to make sure you have all the software you need in order to get the hands-on experience in implementing Data structures and algorithms.

Then we get to the essence of the course; algorithms and data structures. Each of the specific algorithms and data structures is divided into two sections. Theory lectures and implementation of those concepts in Python. We then move on to learn:

  1. Recursion

  2. Stacks, Queues, Deques

  3. Linked List

  4. Trees & Binary Trees

  5. Binary Search Trees

  6. Priority Queues and Heaps

  7. Graphs & Graph Traversal Algorithms

  8. Searching and Sorting algorithms

Again, each of these sections includes theory lectures covering data structures & their Abstract Data Types and/or algorithms. Plus the implementation of these topics in Python.

Transcripts

1. Why Data Structures?: Hello, everyone. And welcome to why many data structures before we begin. Let's define data. Data is nothing but some useful information stood on the computer memory, for example. We have documents. We have photos only majors. Are you clips, videos and soccer programs on application? This data has to be stood efficiently. UN computer memory. You must be wondering about why many data structures? Why is it important as well as wondering about why do we need to study internal structure of the data on why is it important to employment data structures? The data can be stored in the memory in several weights. But by using the structures, we can store the leader efficiently. The data structures is a way off arranging the data efficiently in the memory applications are programs that use this data can access it efficiently. The term efficient are efficiently, is very important because that is the reason we need data structures. Any application of programme may contain algorithms. These algorithms are set off. Instructions are rules that performs some task. Our operations and finance amount of time on the data structure is a systematic way of organizing and accessing the leader. Therefore, we need data sectors so dark the algorithms are programs can access the data and systematic and efficient way data structure is mainly divided into two categories. Lenient data structures on non linear data structures in leniently district as we have stacks, queues and accused, as well as linked lists on In Nonlinear did a strictures. We have trees and heaps on graphs. Now, having seen by many data sectors, we will move on to the next lecture. 2. Python Installation: to implement data structures in fighting programming language we need to install Python interpreter or bites and software Open Google Groom on Die Fightin Download on Select the Lincolns. Download Fightin Now you've given fine Download the latest version for Windows. This will be downloaded and saved a near downloads folder. Be that if you open it and tired and stop fightin once the installation starts, make sure that you have are fighting 3.72 parts checked and then install this build a couple of minutes to Einstein and once the installation is successful, just stay close. Now let us verify, but that the fighting has installed successfully. Just go to the windows start and then here you will find recently order despite an idol biting more dudes on biting man will just trying to use idle. This is an integrated development environment for biting. If you observe, this is the idea for the fightin. Neither does the straight to execute a statement Print. Let's say hello, Wrightson on you can get the output of the pin statement. With this, we make sure that the fighting has been successfully and start. Obviously, we've learned be using this idol integrated development environment for biting. In the next section we will see how to download and install by charm on we will be writing programs and working in by chance. But we need fightin Insulation are we need fighting sock Where? Our interpreter So that Bytom will work on the Spuyten interpreter Apart from her those you can also download and install fightin for Lennox systems as well as far mackerels. 3. PyCharm Installation: in this section we even see how to download by charm That is the Buyten's integrated development environment. No destroyed to search for by term just grows the link by charm the bite and I d for professional developers by jetbrains And here we have down Lord, by Tom, we will select Windows, though you can also don't look for Mac OS as well as the Knicks sisters. Now here we have professional as well as the community addition Professional is ah, Reid was in, but the coming the addition is free and open source. So let's down toward the community version. Once down, ordered, the by time will be saved down notes for that Let us open the insulation file and then let it install up item. We will select the 64 bit Plancher. We will select a clear deck stop short court as well as a treat the path very in. Then we will associate not be by extension with deep item i d. The installation may take some time, depending upon the capabilities of your system Destroyed the click finish It is open paycheck by Tom will be in start inside the jetbrains folder. Once we are able to open the I. D. That means the installation is successful. Now we can go further with the implementation off fighting programs for the death structures and algorithms. 4. Linear Search Algorithm: in this section, we will see the very first algorithm of this course. That is linear search algorithm. This is the simplest search algorithm. Let us consider a certain limits. The linear search algorithm will search for the key within this set in fightin, set off elements are represented using list. So therefore, we have a list with the name A and it has five elements. And here are the Indus is for each element. We will be able to retreat the value of each element using the index. So the first element has, like zero followed with second element which 1000 x one till the last element which has index four. Let us consider a key 47. The approach of linear search algorithm has to visit each element and then match the key with the element. If it is founder, turn true health return faults even see how this algorithm books. The key 47 is taken and then compared with the first element in the list. If it doesn't match, the search will move to the next element in the list and then compare the key with the element in the list. If it is found better turns true. Now let's take another example off searching a key 15 again. The algorithm starts from the first index, compared the Limmer moves on to the next and next compares the element and so on. That the last element and so on till the last element in the list. If it is found, it will be done through. Now, if you observe, the linear search algorithm will start from the first index and move to the last index at each iteration. Hurtful Masti element in the list with the key. If it is found, it will return through else Wilder down parts. Now we will search for the element which is not present in the list. Key over here is 50. We start with the first index. It doesn't match moves on to the next index did the last 10 days. Even their limit in the last index doesn't Max with the key. And once the end of the list is reached and none of the element advanced, it will return faults. This is how linear search algorithm works. In the next section we will see the implementation of linear such algorithm in fightin 5. Implementing Linear Search Algorithm in Python: in this section, we will implement the linear search algorithm. We'll create a new fight and file on Give it the name as linear search. This will open a blank fightin file on. We will write the implementation for linear Search algorithm year. We will define a functional in your shirt with stakes in two arguments. 1st 1 is the list. On the second argument is the key which we are searching. We will then define a variable position which is a sign Zito. The variable position will be used in a loop two travels from the start. In the end of the list, we will define a variable flag and assigned the value falls. This variable will be used to check whether we have found the key or not. The next statement will be the core of the algorithm. We will use a via loop while position less than length of the list and not a flag. They will come back to the conditions in the via Lou later. Let us continue with the program. We will use an if statement if a off position equal to equal Toki that be said art flag equal do through else we will inclement deposition that this position equal to position plus one. Then finally, we will return the value of the flag that is execute this program on. We find no editors. Let us create a list of some elements. These are the deliverance, which we have already seen in the previous section. As an example, the next statement we will have has found equal toe. Let's call the linear search algorithm function on past the value A coma 96. Now here 96 is the key which we are trying toe search. And finally, we will have a parent statement where we will display the value returned by the media search algorithm. No once. Well, on this program, you can see that better turns true because 96 is the Limmer president in the list. Let us try to search for a limit. Nine. Once we were on this program, you can find that element minus falls that it's not president of the list. Even talk over the conditions in the value. The first condition that this position less than lent off the list is used to travel the list from Position zero till the end of the list and the next condition not flag flag, is initialized to falls. So very first time flag will be false and not a flag will be true so that I look executes and once in the vial condition if the key is founded, the position the flag is assign value True. And when did I look executes the flag will be true, not of true is false and the program comes out of the loop. This condition is very useful because once the key is found, there is no need to travel to the list. 6. Recursion in Python: this section is about Rick Ocean and fightin. We use loops in any programming language as well as in fightin to execute repetitive statements such as a via loop or a for loop is used in fightin to execute repeated of statements an entirely different way. Our approach can be used to achieve execution off repeated statements through rickerson. The coercion is a technique where the function of a method makes a car to accept the best examples of Riker Shen is a factorial function. This is a classical mathematical function on. We will use this factorial function in the next slide to demonstrate how Ryker Shin works. The other example is fiber 90 cities, which is a sequence of numbers, and each number is the sum of the previous two numbers has villas. Rick Ocean can be used in binary search algorithm. This algorithm is very important, so its algorithms in computer science. In the later section we will see the implementation off mining research angle Girton through iteration as well as through Ryker. Shin's in Rick Ocean approach. When a function calls itself, it may go into an infinite loop. Therefore, there should be a condition through which no recursive call is made on this values known as base case the implement Ryker Shin There should be a Cleese toe One base case on the chain off records of calls should eventually reach the base case. We will use an example of factory in to demonstrate Ryker Shin as well as to understand the concept off base case The factorial off end numbers is a multiplication of cities that is factorial off three as one into into three we will take an example of factory in fight Here we have a function factory in on this function Factorial will have a variable fact for factorial five We say that fact it will do five into factorial four If you observe we are calling the factorial function recursive Lee. So now a Carla's make two factorial for and factorial four function will evaluate us four into factorial three in the same way Factorial three will evaluate as three into factorial too On factory will do will evaluate as do into factorial one and factorial one will evaluate us one into factorial zero here when the argument and the beach zero we call this as a base case on we will end the Ricker shin when an equal to zero are the perimeter past is equal to zero and then we will return one factorial zero will eventually return the value one without continuing the chain off the precaution. Therefore value one s return for factorial zero for factorial 11 into one is returned for factorial too Do into one is return factorial three three Interview is returned and for factorial four four into sixes. If you observe at each stage the return value has multiplied by the value already present in the equation. And finally, the value of factorial four is returned. That is four into six which is 24 on multiplied by five, which gives us the reserved for factorial five. And this is how a Ryker shin works Always remember that they should be a base case where we terminate the gene off recursive cults 7. Binary Search Algorithm: in this section, we will learn how binary search algorithm works. Let us take an example of a list hand it's in. This is the buying a research algorithm books only if the list is sorted. Unlike the linear search, where there is no need for the list to be sorted, order, let us take the key. That is, the element to be searched within the list. The Binder research algorithm starts from Index zero, which is represented as low on the end of the list is represented as high by any research algorithm. Works on the formula made equal to low plus high by to remember that this division off to is an a teacher division. The murder value in this case will be zero plus four by two. That is true. Therefore, we take another valuable Azman in the nation states of by any research. The mid is nothing but the middle of the list are made element of the list. Now this Middle America that is a off mitt is checked with the key. If it matches the algorithm, Miller turned true. That is, the key is found on the list. But if the key is less than the murder value. Then the lower half of the Leicester searched. And if the key is larger than the murder element than the upper half of the list asserts, no. Suppose if the key is less than the middle value we serves the lower half on the value of high. It seems to me the minus one now. In the second iteration, the low index values not changed, but the high values changed on becomes a mid minus one. The upper half of the early, along with the murder value, is discarded. Now the searching continues only in the lower half of the list. If suppose the key value is greater than the men, then the upper part of the less dis searched on low becomes made plus one. In this case, high value is not changed. Only the low value becomes mitt plus one on the upper half of the list asserts. If suppose the loo and the high indexes cross each other, that is, the low index becomes larger than the high end eggs. Then we say that the element is not formally list. We will take an example and apply the buying research algorithm in this case we have the key as Levin on, we even searched the ski Using the binary search approach initially low will point towards the first index of the list and high will point towards the last index of the list. We calculated the murder index in this case made indexes to and we compare the 1,000,000. Next with the key. The key is less than the murder next. Therefore, lower part of the area searched and high becomes mid minus one since murders to in this case high will be to minus one, which is first index are high index will move the words the first endings Onda We discard the upper part of the list. Now the murder value is again Computer lo a zero and high is one so zero plus one by do since it's an indigent division figured the middle value as zero. Now the murder in next feel point words zero index in the list. The value of the key is compared with a off mid that is a off zero on it doesn't match. The key is now compared with a off murdered that is a off zero. Now the key is greater than The middle value, which is four, therefore low will be made plus one that is murder zero. So nobody will be zero plus one that is one on Global Point words. First index of the list Again The Medicis calculator and now made will be low plus high by two. That is low as one and high is one. So we have medical due to buy two. That is one. The midpoint are the mid indexes one now, and key is compared with Mitt. Since Key is equal, do a. Offerman, that is a often we have found the element in the list on the algorithm returns true. Let us consider another example. In this example. We are taking the key as 15 now, just by the look at the list, we can say that it's not fun, but let us see how by Navy search algorithm works again. Initially, we start with the low index, which points toe the start of the list on high index, which points toward the end of the list. The murder values computer made points towards the second index are middle of the list. He is compared with the day off man, he is less than the value of the murder element. Therefore, lower half of the asserts hi becomes mid minus one. That is high becomes one. On move to the first index, the rest of the area is discarded. The newly of the murder will be murdered equals zero plus one by to that zero, so murder will move toward zero index on the eliminate. Discomfort with the key The key is greater than the value of the murder element. Therefore, low will be mitt plus one that is zero plus one. It's one and then local point words. The 1st 10 days mid value is again computer. Now the murder values one plus one that is two by two mid now points towards the first endings the eliminating the first indexes. Compared with the key, it is not equal on. The key is greater than the first element. Therefore, low is changed to mitt plus one Now I know will become too that has made is one plus one. It is too on low index is larger than the high index. Therefore the algorithm terminates on returns faults. This is how, by any research algorithm works. In the next section we will see the implementation of binary search algorithm you tentatively as well as recursive Lee 8. Implementing Binary Search Algorithm in Python - Iteratively: in this section of evil. Implement binary search algorithm a relatively let's create a new pipe and file on give the name is by any research it every game. This will open a blank fight and fight on. We will define a function known as binary search. This function takes in do para meters that his first Param Eter is the list and the second para meter is the key. That is the value who researched On the next line? We declare Lou as a variable which is assigned a value zero on high as another variable which is assigned the value let off list minus what? Please remember dark blue and high at the two indexes, representing initially the start of theory that is index of the start of the day earn index of the end of the day. We will then have a look viol Luke is less than equal to high and we will compute the MiG value that is made equal toe low plus high divided by two. Here we have two slashes Since the division is in teacher division and then inside the via loop. The second statement we have is the if statement we will check if key is equal to a off May . If it is equal, then return true else. If that is a lift and tighten, we take key is less than a off Meg on high will become high equal due mid minus one. The next statement we will have else. That is we're taking if key is greater than a off murdered. So we have else lo equal toe met less What? Let us execute this program to check for any others. No, we will clear denarii with some elements. And then we will call binary search algorithm using farm equal do by any desserts on because the list a comma, the key to be searched That is, in this case, it is 96. And finally we will have a print statement printing the return value off the buying research on Greta. Once we exude this program, you will see that true is returned since 96 is found only list. Now suppose if we try to find an element that is 46 the Alberta returns none. Now we will make some changes since it has to return false. If the element is not formally list so therefore the last statement outside the value. We will write it US return faults now empty eliminates. From then return, true will be executed, which is within the via loop. And once the via look complete, that is, if low becomes greater than high Then the violet terminates and leader turn faults That is the element is not phone This is how binary search algorithm is implemented in relatively 9. Implementing Binary Search Algorithm in Python - Recursively: in this section be able implement binary search algorithm recursive Lee. Let's create a new bite and file on Give it a name as binary suit because it we will define a function. Bind research with stakes in arguments as list. The second argument as key The third are human as low on the fourth on human does. Then we will have a condition. If low is greater than high, they're done, folks. Hence mid equal do low plus high by do on here also, it's an in teacher division. We will have a condition if key equal to a off murdered. Then they're done through and lift. He is less than he off men. Then we will call by any research function recursive Lee that is return by any research we will pass A That is a list key value which remains the same. No value, huh? High value as murder minus what hell's that? Is the condition key? Greater than Hey, Offerman. The village like the statement were done on call buying research function with a key earn answered off low. We will have make plus one and high as the fourth that immediate. Let us create a list A with some elements least remember there and buying a research, the element must be sorted. We will make carded buying research function, passing the list that the key in this case it's 84. Low value with Zito on high value, which is fight. Let's execute the program. You will find that the value returned this who because 84 is the element phone. Suppose if you tried to search eight we will get the result this false because it is not present in the list. This is how, by any research algorithm can be implementer using Rick Ocean. 10. Algorithm Analysis - Time and Space Complexity: in this lecture, we will talk about analysis of alligators on the main topic of discussion Is this Time and space complexity. The concepts of data, structures and algorithms are central to computing. We need an analysis tune to measure the goodness of Adidas. Structure operations are algorithms in real world scenarios. We have a clock so that we can measure the amount of time taken to complete a task are to complete some work in the same way we can use a scale to measure the distance. Or we can have a speed o meter to measure how fast a car is moving as well as we can have a blood pressure monitor to measure the blood pressure in computer science to measure on algorithm our operations of any time and space complexity. Time complexity is an amount of time it takes to run an algorithm in the same way the space complex city is the amount of memory used by the algorithm. There may be several ways of computing and tasks are implementing a solution for a problem . For example, searching and sorting. They are very Salva terms for searching on sort of each algorithm will takes its own time to compute. Let us take a scenario off two cars as compared to the two algorithms we have for solving a problem. Acindar. Both the cars. We have two people. City. If both the cars traveled from origin to the destination, one car may take less time to reach down the other. In the same way one search algorithm. It take less time to compute than the other sorts algorithm. Now let us take another scenario where we discuss the running time of Alberta. More data structure operations increases with the in crowd size. Now let us take same car on a zoom dart in one car, their two people on an undercard There five people. These two cars are synonymous to the same algorithm, but with different inputs. Now, when these two cars move from the origin on travel towards destination car with the less number of people, maybe is the destination much earlier are in less time than the other car with size of the import has increased. Therefore, the algorithms are categorized according to the function of the input sites. We have two ways of analysing the Uncle Tom's true time complexity. That is one is the experimental analysis and the other one is the political analysis. Let us tight talk about experiment analysis in experimented analysis. The running time often algorithm may can be measured by executing it on various inputs on their by recording the time spent on each execution, fighting and several other programming languages provide a time function laughs. Time from this time function can be computed by recording the start and the end of the Al Delta. They are several disadvantages. With experimental analysis. The experiment should be performed in the same hardware and software environments. That is, we need to use the same hardware and software to compute the time for different algorithms . Then the experiments can be done only unlimited inputs the even now discuss of our theoretical analysis. The analysis is performed directly on description of the algorithm or actual program or function or operation. The advantage of theoretical approach is that it is independent off hardware and software environments on also takes into account all the possible inputs. Now let us take an example of binary. This area has five elements represented by the indexes, which is starting from zero. Assume dark. We are performing the search operation and the key for the search is 47. We start from the beginning of the area and check with 47 s present in the zero their necks of theory. If it's not present, people wanted the second index still be leads the end of the party. This is the same way the linear search works, which we have seen in the previous section. The area might have any number of elements, so the searching will continue until end, minus one as well as silly and element. Therefore, the algorithm needs to perform the comparison off the key with each element in the attic. That is, they are n number of comparisons that needs to be, but for as well as we need to Travers theory and number of times, therefore, the complexity will be ordered off him. Let us try to see the algorithm in the algorithm. Execution of primitive operations has taken us constant. That is, we assumed, are a constant time is taken for any primitive Operation Tartus assignment. Performing any an automatic operations combat isn't statements accessing elements calling functions as well as returning functions. Let us try to examine the mathematical function let us take the first statement of the bite and function. This statement is an assignment statement. Therefore we see that it takes a constant time. The second statement also takes a constant time to compute as well as the third state. Now the state went to the far Luke will compute are run for n number of times and the if statement that is the comparison followed by the for loop will by itself take constant time . But since it's within the for loop, it has to execute a number of times in the same way. The return flag Els on incriminating the position will are the end number off night to compute and finally we have returning the laugh. Therefore, when we compute the mathematical function FN, we have six statements running n number of times on four statements taking a constant time for execution. Therefore, this function is off order and since the polynomial contains degree one on, we say that this algorithm will take at most off any time for execution. Let us consider another example Now here we have another A, which consists of five elements on our solution is to compute the partial some off elements at Eat Index, we have an algorithm known as partial some and this Allerton will take the starting index in 14 loop That is I, which is represented here in Green Arrow on another for Luke Day, which is represented with the Red Arrow. For the first iteration, the RDS will contain the first element. Then the eye for look will move to the second element in the SRE on VI vill compute the sum off zero on first index off it every which is 25. We move on to the third element and then compute the sum of three elements and a This will continue with the fourth element where some off four elements are stored in Ras On finally the some off All the five elements are stored in the last index off SRE Let us try to analyze if you observe to compute the partial Some are every element we need to Travers theory again and again from the beginning until the end element Therefore the time complexity of this algorithm iso offense square. Let us try to see the time complexity through the algorithm. The first statement will day concert time Since it assignment statement. The second statement will also take a concert name. The third statement that is far Luke will run and number of times the fourth state went with this sum equal to zero will by itself taken unit time on a constant time, but since it's a part of the farm loop, it will execute for a number of times. Nested for loops itself will run end times, but since it is within the ICT for Luke, therefore it will take end into end our end square time for computation the same way we haven't assign some statement as well as assigning the somebody at that area. Now let us compute a mathematical function. FN. If you observe their two statements with takes in and square times, plus the three statements it takes an end times to compute on three statements will take a constant time for completion. The highest degree of this function is in square. Therefore, we say that this algorithm will take often square or we'll take order off and square for computation. Let us I did see the third scenario, and here we have three arrays. Each of its contains some elements on our solution for the problem is to find if the sets are designed, we have this Alberta. If he observed the first far, Luke will turn for a number of times. The second far Lou, that is for Jay will run for and square times on the third for look for it Is Agnes stirred within the ICT for loop on the date for Luke will run for n cubed times and we have a comparison statement. That is, if I equals t equals okay, This also will run for in Cuba times on Finally, we have a return statement as well as end off return statement for the function. If we exceed the mathematical function FN for this algorithm, we will see dart there three statements which stakes in n cubed times to compute. There is one statement which takes an end square time to compute as well as there is one statement which takes an end times compute And finally we have a statement which takes constant time to compute. If we see this Pollen Ami in the highest degree is in Cuba. Therefore we say that this algorithm this joint will take off in Cuba times to computer to run are the time complexity of this algorithm is off and cube. Now let us take another scenario where we have honoree on. If you observe this area isn't sorted. Order. I will try to perform the binder research which we have already seen in the previous section. This is the anger time for buying a research. This binder research algorithm will start from the mid off theory and search towards the left side, where all the elements are smaller than the mid element on right side where all the elements are larger than the male element. Now, for the first instance, it will check the murder element. Assume that we are searching for the key for the comparison with the mid element of the day is made with the key. If the key is less, it will search only the lower half of the other on discard the upper half of theory. So the via loop announcer, it's for the lower half of the other on At each iteration, the loop will discard half. Therefore, we say that the via loop will take longer and times to compute on. If he compute the mathematical function, we say that this algorithm will take off log and times compute on the complexity of this algorithm. Iso off Logan. Let us summarize the time complexities, which we have seen earlier. 1st 1 is the constant, which they say it takes one unit of pain. Next we have seen is De la Greta that has off log in. 3rd 1 is the linear which is off in then. We have also seen car traffic, which is offense square on cubic, that is often cube. We also have time, complexity as end Logan, which we say as go off and Logan and finally, exponential, which we say that off group overran. These complexities are arranged in ascending order according to the time to take. That is constant takes less time that log in on Logan takes less time than end off and will take less time than off. And Logan, as villas and square that is car traffic, often cube on exponential algorithms. Having exponential time. Complexity takes worse. Time to compute. We have a chart summarize this chart. You can clearly observe the time complex. It is taken for various number off imports that is in on X axis and FN function on the Y axis 11. Abstract Data Type (ADT): In this section, you will learn about abstract data. Type. Abstraction is one of the front number Do Prince puts off object oriented programming. When abstraction paradigm is a play to the design of data structures, entities are formed. The entity is a mathematical model of data structures. The A D D specifies types of data stored the operation supported under data on perimeters. For those operations, 80 is used to specify what each operation does. A D T. Does not specify how operations are done. A did. He only talks about what are the operations but how those operations are implemented. It depends upon the programming language. For example, you can have a stack a GT R a Q 80. These tax ADEDY can be implemented using C plus plus our any other high level programming language. But in the scores, we will be using fightin to implement the abstracted, a type of media's infrastructures 12. Stacks Introduction: Welcome to this lecture off Introduction to Stacks Stack as a collection off object, which works on last in first out principle, the fundamental operations of Stack is pushing and popping for better understanding. Let us try to see an example of a bottle. We will put each ball into the bottle where the bottom of the bottle is closed and the other end is open. Their pre caller does a top. The first operation will apply this push that is pushing the Redwall. If you see the stack can refill only from the top. The second operation is to push the yellow wall, which is again pushed from the top of the stack, and the third operation is pushing the Blue Boy, which is also pushed from the top of the stack. Now for the pop operation that is removing the balls from the bottle. We cannot remove yellow because it's not on the top of the stack as well as it is not the last in. We also cannot proper Werth the Red ball because that is also not the last one which was inserted when we apply pop operation with Stack, we can only pop out the blue ball, which is on the top of the stack. Therefore, the pop operation will remove the blue board, and then the subsequent pop operations will remove the yellow ball as well as the Red Bull . We will take into the scenario faggots incident, fusing top and bottom. We will use help, which points towards the engine, and they'll, which works as the top of the stack. If he puts the blue wagon, it can be inserted only at the tail, and now the blue wagon becomes the tail of the stack. Then, when we push the green wagon, it will be harder to the end of the stack as well as the red bag it. So in this case, if you observe the wagons and not attached to the head. But it is a cast to the tape on. The pop operation also works from the tail side. Stacks can be used in various applications that does. We can have a browser history with stores, the Web pages we have visitor and the simplest application to observe is the texture detect where we can perform on new operations. That is, the last operation can be undone. As the first out. We can also use to evaluate automatic expressions. Parentis is matting on matting. The estimate attacks in the webpage as well as we can a place tax to in fix and post tricks conversion. In the next lecture, we will learn about the abstract data types of stats. 13. Stacks Abstract Data Type (ADT): In this section, we will learn about abstract data type of stacks. These tax 80 stores objects. The last in first out scheme is used for insert and elite operations. The operations off stack entity are Bush, which is used to insert the element of the stack Bob Operation, which is used to remove under turned the element from the stack top operation will return the last inserted element. Please do remember Dark talk will only return. The last inserted element on it will not remove the element. Then we have length, which it turns the number of elements in the stack on his empty operation with checks whether the stock is empty honor. Now let us see the working off these operations, the first operation, this push and we're trying to push element in. Initially, the stock is empty, and then once people form the push operation that is pushing the element and displays inside the stack, the next push operation that is 20 will be on top of the stack. If you played the letter operation there, two elements in the stock and then once we pop out the last element that is 20 will you pop . Note his empty operation will be false because Stack is not empty. The little strata Paabo then will be popped out. And if he apply, is empty operation at Billiton. True, the letters push 30 push again 40 and then you can observe dark when we use a top operation top of Stack 40 is return without removing the element from the stack and then we're going to push for 50. Now the length of the stock is three the pop. OK, so the last inserted element that is 50 million pop note and then we push 60 as well as 70 . Now the top of the stack will be 70. This is how the stack adedy operation works. In the next section we will see how to implement stacks Using arrays are more specifically using lists and fightin. 14. Implementing Stacks using Arrays/Lists in Python: in this section we will implement stocks using arrays infighting we will use by Champ as the integrated development environment. On months we cleared the project. We will create a new bite and file on give it the name as Stack Buddy. This opens an empty pipe and find where we can write this tax program to implement Sac CID et We will create a class known as a stack and then defined the in It mattered for this stack of it is nothing with the constructor and the members of the stack class will be underscored data which is a list. Since we do not have a raisin beytin, we will be using list to implement stacks using a raise. Then we will define the length matured for the stack. This lent my third will return the length of the list. We will have another function that does is empty. This function will er done whether the stock is empty or not. Then we will define the push operation. The method off push operation will take element as an argument. Then we will upend this element using the weapon mature off the list. We will now define the pop operation using the pop mature Popma. Third will not take any arguments. The very first thing we will do is check whether the stock is empty or not. If the stock is empty, we will raise an exception, saying that stock is empty. If Stack is not empty, then we will return the pop element from the data list. Then we will define the top mature in the top method. Also, we will check whether the stock is empty, not MTV Millerton Data off minus one index Do remember that in fightin lists can have positive as well as negative, and this is minus one indicates the last element of the list. Therefore, wither turn data off minus one, which is the last element of the list. Since we are catching exceptions, we will create an exceptions class from where we will import empty. Let us now keep an exceptions class. In the exception class, we will define class empty, and then we will pass exception as the argument and use. The pass is the key word to complete the implementation off empty class. Let's save this program and execute that will not output anything because we have just created the class which can handle empty method for exceptions, we will run US tax program to check for any errors. Now, here we have defined the entire implementation off stack A d. D. Using arrays to perform the operations with this stack of which we have implemented above, we will create an object s off the type stack. Hurry, We will use s object to perform operations on the stack. The first operation we do is s start Bush. Then doctors eliminate 10 will be pushed onto the stack and subsequently we will also use else Start push 20 so that element 20 will be pushed onto the stack. Then we will have a print statement to print the contents of the stack using s Dart Underscore Data data is a pie tens list which we have defined as the member of the stack class. The next operation will perform as to print the land of the stack using alien operation. We will also check if the list is empty. That is the values but and s start is empty. His empties Um, 1/3 implemented as part of these tax class. Then we will use pop operation to pop out the element on print the element which has bean removed from the stack. Then again, we will try to print the contents of the stack. We'll execute this program. The first statement of the execution displays the content of the stag darkest 10 and 20. Then we're displaying. The length has to because in the stack we have two elements. The car to the function is empty. Billiton falls because Stack is not empty. Then we have applied. The pop operation 11 20 sparked out because that is the last in element, which is first out. Then we have despaired the content of stock. Now the start contains only one element that distant. We will perform pop operation again and then we will print the contents of the stack. We will first check if the stock is empty on our 10 print. The contents of the stock that's executed this program and you will find our then was the element which was there to the stack. And then we performed the pop operation. So 10 element has been popped out. Now the stock is empty. It's this place true, we will push to more elements that is 30 and 40 onto the stack. Then we will you stop operation to find the contents of the top of the stack. You can observe that 40 has been returned at the top of the stack and the content of the stock is 30 and 40. Please remember that top operation will only return the top element but will not remove the top element from the stack. 15. Queues Introduction: In this second, we will see the cue data structures and beytin. Q is also a collection of objects which follows the first in and first out principle. The fundamental operations off cues are and you and thank you. It is considered a pipe where we have the front of the pipe and then the date of the bike. When we perform the anti cooperation, the elements are inserted from the rear of the queue, for example, and your heard the red ball will be inserted from the end of the queue are rare of the queue. The next operation and Q that is, the yellow ball will again be added from the rear of the queue the same way. The third and cooperation will also add the element from the rear of the queue. The D cooperation will remove the element from the front of the queue. This is how the Q data structure works. Que data structure also has several applications such as this data structure can be used to implement waiting queues as well as it can be used to implement the access to shared resources. The Q data structure will also abused in other sections. When we learn about graft, Traversa methods 16. Queues Abstract Data Type (ADT): in this section, we will learn about abstract later type of cues. The Q abstract later type is used to store object which works on first and first out principle. Our scheme for insert and delete operations. The insertion is done at the rate of the queue on removal are delete. Operation is performed are different of the cube, the operations off to a de Dion. Thank you. This operation is used to insert the element at the end of the queue. De que operation is used to remove the element underdone from the front of the queue. We also have first operation which only returns the element from the front of the queue but do not delete this element. We have a length operation which returns the number of elements in the queue on is empty operation which returns whether the Q is empty or not, let us try to look at the operations for better understanding. Initially, the Q is empty and the first operation we perform is and you which art element in the rear of the cube. Then the next and your position will Arden Element 20. The length of the queue is now, too, when we perform Dickie operation. The first in first out principle is used and 10 is removed from the front of the queue. We will perform DT once more. Now the Element 20 is removed from the queue on If he use his empty operation, it returns. True because Q is empty. If he further perform the dick, you operation on an empty queue. We get in at it. Let us try to in Q 40 element and then ank you another element 50. And once people form first operation, it will return the element at the front of the queue. We will have in cooperation again. Now the length of the cuse three once ridiculed 40 will be removed, which is a different of the queue. This is how the operations are performed in the queue. In the next section we will see the implementation off Q entity using lists and fightin 17. Implementing Queues using Arrays/Lists in Python: in this section, we will write the court to implement Hughes using a race that is using, list and fighting. We will create an empty file and give it a name as you ari. The first statement we will write as from exceptions import empty This exceptions fighting file we have already implemented when we have seen the working of this tax. The exceptions find contains a class empty, which is used to handle exceptions in our Q class. We have a long career. The Q class with the name thank you followed by the constructor on this class will have a member underscored data, which is a list which we use it for storing the elements in the queue. We will use another variable a size which we initialize 20 on another variable front which we will initialize 20 We will write the implementation for Lin function. This land function will return the size of the queue. Legal implement is empty function. This is empty function Miletic with size zero in the size zero, it will return through else faults. We will now implement the into operation, even have a statement as underscored data dot weapon off he and then the next statement would be size equal size plus one. The ANC, you, the end human Third world, take one Are human Mrs de Element to be inserted into the Cube. We will now, right, a Ikuma Third, this Duke Human third will not be any arguments. The first statement people check is whether the Q is empty using if is empty on If it's empty, we will raise an exception that you is empty. Hence we use available value, which is a sign the eliminate contain on the front index. Then we will make data offer equal to none. Then we will inclement the front index by using front, equal, different plus one. And finally we will declare in the size, size, equal toe size minus one, and returned the value which is a ridiculed. We will also write a mature first. And in this meth or the first statement we will check with the queue is empty or not and reason exception as leaving their done data off front. This completes our Q class. We will run this class to see if there is any others. No, ive been cleared An object you Vidic last name as a wreck. You and then apply the n Q operation on the skew object that is cute in Q off then and cute and you off 20. Then we will print the queue using q dot data data. As a member of the You Glass, we will also find the length of the queue using alien function v Villa Play de que Operation that is cute Dark Dick you. After the decay operation, we will print the Q once again even in Q. One more limber that this u dot in Q 30 and then you not in Cuba 40 on we will print Dick you. We will also retrieve the first element from the queue using q dot first method and then again print the Q. We will apply Dick your operation once more and again ridicule. Let us run this program to CDO the 1st 2 elements we have inserted in the queue. I understand in 20 length of the cues do. Then we perform the de que operation so we have none common 20 and that the first element return is 20 again, but you d cured. You will find the Q has only two elements. Now that is 30 year 40. None in the CUNY presents the place where we have been killed. The element from the Cube. 18. Deques Introduction: in this section we will learn the dick you did a structure. The CQ works the same way. Ask use. But with additional operations, that is. You can art as well as removed from the front on the rail so insurgent can be done from the front as well as really deletion performed from the front as well as from the date. Let us see the working off pick use here we have the front as well as real. And then the operation act first on our last will insert the element in the empty de que And then if he performed, are lost, it will insert from the real And then once we performed elite first the element from the front of the league you is removed if he perform the operation delete last the element from the rail of the dick us removed If he again performed the operation arc first we can insert the element from the front of the queue as well as our last will insert the element from the mayor of thank you. This is how Dick you works. The only difference between cues and accuses dark in Q. You can only insert from the raid on the lead from the front. But in the use you can insert from rail as well as from front on, you can delete are removed element from the front as well as Trump, really. 19. Deque Abstract Data Type (ADT): in this section, we will learn about abstract later type of dick use. The D Q 80 is also used to store objects. The insertion and deletion operations are performed at both the ends that is front and rail off the dick. You the operations of Dick you led our at first which is used to insert the element in front of the queue. Our last, which is used to insert the element at the rear of the week you delete first operation is used to remove the element from the front of the week. You, the elite last operation is used to remove the element from the rear of the week. You the first and the last operation is used to return the element at the front on the real of the de dupe, respectively. We also have lent operation which is used to turn the number of elements in the week. You Asprilla's is empty operation which is used to check whether the D. Q is empty or not. Let us look at the working off these operations. Initially, the Dickie was empty. And then once we perform our last, the element is inserted into the lead. You again. Another element 20 is inserted from the rear of dick. You on the third operation are last will also insert the eliminate 30 from the rear of the vic. You a fee performed elite First the Element 10 which is at the first of the week You is removed on delete Last will remove the element from the read if you use art First operation The 11 40 is harder in front of the kids. Pick you on our glass with argon. A limit 50 at the rear of the Egypt This is how the operations of de que books in the next section we will implement the abstract later type off the accused and fighter. 20. Implementing Deques using Arrays/Lists in Python: in this section, we will write a program to implement Dick use. The very first statement will be from exceptions import empty This statement we have already seen in the earlier programs. Then we will find a class with the name D. Q. It will have an it mattered on the members of the in It Mattered are underscored data, which is a list and self start underscore front. We will assign a zero. We will write the implementation for the length operation that is alien mature. It will return Lent that is alien off self dark underscore data that is the length of the data list We will have. Another function is empty. This function will also not take any arguments, and they're done leant off Celt our data equal to zero. Then we will have first mattered on. We will check if the D Q is empty. Andres. The exception else we will return. Sell their data off self dot front. Next, we will create art first with heard on. It takes 11 p as the argument. The next statement will bees self dot data dot insert off cell dot friend Comma E, which is an element then the next. My third would be hard last on the perimeter would be e the statement Inside our last, we will have self doubt data dot weapon e We will then write delete first mattered on The very first statements we have is to check whether the dick you is empty Else we will use value equal to sell dark data dark pop off cell dart friend and then finally run the value the next method will be delete Last this mattered also will not taken any arguments. On first thing is to check whether Dickie was empty then value equal toe cell, dark data, dark pop And then we will return value. Let us execute this program to check for any errors. We will create an object d of the class a ridicu Then perform the operations that is the dark are lost We will pass 10 then the dart again our last We will pass 20 the same way We will insert five elements 10 to 50 Then we will print the dick You using the print function on Dick You dark data Let's execute this program on VCD output off five Deliverance President in the did you it is known. Perform the delete first operation and then trendy beat you. We will also perform elite last operation That is the dark delete last on Execute the program. You can observe that initially there five elements in the league You The first element is 10 leave alone Perform art first operation passing the value is 50 on printed like you as well as we will perform our last operation passing the value as 60 and then printed you as villas Computer t lent of the details We having that out here? Let's check was the problem. The problem is, I forgot to our two underscores in defining the lent method. Let's execute the program. You can observe dark deliverance on order to the first of the week. You has villas at the end of the big you on the length five is displayed. This is how the led of dick you is implemented in beytin using studies are specifically using list in fighting 21. Linked List Introduction: in this section, we learn about a data structure known as link list. Even first tried to see why we need link lists. We have already seen Stags Data Structure, Hughes Data Structure as well as Dick used data structure on these data structures we have implemented and fightin using list list works the same way as a race. In other programming, language today provides centralized the presentation of data that is a large piece. Off memory is a locator for storing the collection. Off objects are elements. There are problems with theories. The first problem is that the area is off fixed sites on it is immutable. That is, once the sizes fix, the size cannot be changed at run time. But in real world problems, the collection off objects are elements will be decided at runtime on. We do not know how many elements will be added. Therefore, it is difficult to determine the size of the area. That complaint link list is used because we need a data structure which would grow and shrink at runtime. That is, any number of elements are notes can be harder, are deleted, are trying type. Let us see the difference between implementation of data structures Using arrays on link list today is a collection of elements which are stored in sequence in the memory. But whereas link list distributes the elements throughout the memory efficiently utilizing the memory space link list uses an object known as node. A node has two members. One is the element. The other one is the next The Element member will store the data object part the element itself On the next member will store the reference to the next Norden the linked list. Let us look at how link list are created. Using knowns, we will use the same elements in the array to re present a linked list. Therefore, for element 10 a new notice creator where the eliminate member will have the value s 10 on the next member of the North. We'll be assigned now initially. Now you re present the second element That is 20 and you notice creator where the element member will have the value 20 and next member will also be none. Since these elements are a collection of data, therefore, a link is created from north tend to know 20 that is next member of the north end will be pointing towards Nor 20 are the value off next member off north and will have reference to the North. 20 for Element 30 a new nordiska later on the next member off North 20 will have a reference to North 30 for Element 40. Also, a new note will be created and next member off 11 30 will be having reference to the North 40 in the same way. North 50 will be creator on next member. Off North, 40 will be having linked with North 50. This is how a collection off elements are represented as a linked list are. This is how a linked list escalated for collection off limits the next member of the last nor will always be having none value, since it does not reference any other node. Therefore, arrays will use a sequin Shal memory allocation for storing the elements. But where are the length list? Will efficiently use the memory on lords? Are elements may not be in sequential order. Now let us see how Nordisk Creator we have already talked about Lord having to members that is element on next in fightin. These will be considered, as instance variables to implement north and fightin. We create a class with the name as Nord on a class level member named A Slots will be creator, which will be assigned instance. Variables, Doctors Element and next in fightin any class created will be using a built in dictionary class to map the members with Eric Wise. Additional memory usage on is not suitable for data structures. To overcome this problem, Biting provides slots as the class level member which efficiently Alak its memory for instant variable. In this case, we have to instance, variables started a limit on next. Therefore, every link implementation will have a class North which will have class level member as slots. We will also use variable Heurtaux point towards the first North of the linked list as well as another object are variable tail, which will point towards the end of the list are the last note off the linked list. Let us now see the detail of limitation of class known. We have already seen how the members of the North structure that is eliminated and next are assigned to slots. We will be defining, um, 1/3 in it with self as a perimeter because it's part of the North class and element. And next as the two perimeters, the element perimeter will be assigned. So the instance valuable that is underscored element and Next para Meter will be assigned. The instance variable underscore. Next, we can create a Nord using the North class, Let's say and want equal do underscored north on passing the values as 10 and none. Once this ex statement is executed, a Nordisk computer, which will have then as the limit on now as they are none inviting as the value for the next member invite and we can access the instance. Members using the name of the North, for example, in one dot underscore element will have value 10 on anyone. Dart underscored. Next will have value none. Let's create another North that is end to equal to underscore Nord on past the value as 20 comma, none a new nor will be created. The memory, which will have 20 as the element member on again, now are known as the next member. If you use a statement en Duin dot underscored next equal to n do. That means they are assigning the reference off north to that is end toe next member off north, and one therefore a link will be created from Nord. Want to nor to now if he access the next member off Norman, that is No. One daughter under school. Next we will get the reference to the Lord, and to this is how a North class can be created as well as the norms can be commuted in beytin and these north scant reference at that lords. The next thing is we will discuss what are the operations that can be performed on link list. We can perform insert operations as well as delete average. There are three ways with in which we can insert Nalls, that is, a note can be inserted at the beginning of the link list. A note can be inserted at the end of the linked list as well as a north can be inserted at any position within the link list. In the same way for deletion, a node can be removed or deleted from the beginning of the linked list. A node can be removed from the end of the linked list as well as a nor can be deleted from any position within the linked list. Let us look at insert operations of the link list. The first operation we'll see is to our north are the beginning of the link list. We will define um, 1/3 known as art first with steaks and element as a perimeter. Even looking, You're the Nord on collar. Does newest nu est equal do self start underscored Nord off Ikuma None. We have already seen this. That is underscore Nord often comma none in the previously the same maybe are creating this nor instead of giving a name as in one, were saying it s newest. Initially the list will be empty. Therefore a new nor will be creator And then we will check if the list is empty. If it is empty, we have a member as hurt which points toward the first north off the link list. So we assign her to the new a snore and then the tail. Also we assigned to the newest Nord because the link lists only has one known. Now suppose if the list is not empty on we're tryingto hard A new lord At the beginning of the list, let us say that it is 70 so 70 will be created on the next member off North 70 will be none on We will assign newest dark next equal do self dot Head that is We cleared the reference from new Nordo the hurt or the first northerly link list and then we will assign her to the newest. So now head will point with this starting north that is 70 and finally we will increase the size of the link list by one if he considered the steps off operation of RD a new node at the beginning of the list. The first step is to create a new Nord and then assign the next member of the new north to the hurt of the list and then stays the herd to the new north. Now let us look at how to insert a new Lord At the end of the linked list, we will define the function art last which will take apart a meter as the element We will create a new Nord the same of what we have done for Harding. In order the beginning of the list that is new s stick will do self start underscore Lord with the element as well as the non Param It. Therefore the new node will be creator and the element is 70 and the next member will not point anywhere. It will be done. We will perform the same steps off taking whether the list is empty. If the list is empty, the herd is assigned to the new note as well as tale is assigned to the new North. If the list is not empty, then we will assign tail dark next to the new Nord that is the last north fifties. Next member will be pointing to the new nor are having a reference to the new north that the 70. Then we will change the tail to point to the last North that is now a 70 on increased the size of the link list by size equals precise bless one. Let us now see how to Arden or anywhere in between the link list. Same every cleared and you note, as we have done earlier on, call it as newest. Then we will take a temporary variable known as he heard. This t hurt is assigned the value off heard now they had anti head will point towards the beginning of the link list we even use of. I looked or travels in the position where we need to insert the element. So assume that we're trying to insert the 11 after the third Ward, the Via Loop will check for I less than the position on move the T heard Pointer to the next note. Therefore, if we have to insert after the third element, that is 30. In this case we will move. He heard twice and then if you see now, the T heard will point to the north 30 and he had not. Next will point to North 40. The newest art next will be assigned third Dart. Next. That means a reference Our link is created from next member off newest. Nor do they had dark next note, which is 40. Then they heard dark. Next will be assigned newest So he heard dot next means next member off North 30 which was pointing towards 40 will now be pointing the words new esten ord on now if we see he had dark next it will be the new s known. Therefore, once this notice in sorter the link list will contain then 2030 70 and then 40 50 as the elements finally the size of the list will be increased by one. Now let us see the delete operations. We even cleared the matured remove first to perform the deletion off note at the beginning of the link list. The very first thing we do is to check if the list is empty. If it is empty, we can already leave the node. If it's an art empty, then the value of the element is a tree using tell underscore element equal toe head, dark element. This will give us a value then and then, since her disappointing to the first Norden, the link list head dark. Next that is, the next member of Head North will point to North 20. We need to shift the head to North 20 now. Therefore we will assign had dart next value to the herd. Now the head will be pointing to the second, nor that is not 20. And then we can believe the note on decrease the size of the list by one that this size equal to size minus one. If the link list hard, only one north on that. Nor do we have the leader, then we will assign her to none as well. A stale took none and finally returned the value of the deleted element. Viva lousy! The delete operation that is deleting the north at the end of the link list, we will define, um, 1/3 as removed. Last on. If you observe, remove first as well as removed. Last will not take any arguments. Though self refers to the member of the same class, you're also we will check whether the list is empty. If it's empty, we can or delete any limit, whether it is from the front of the link list. Our from the back of the link list. When there is no Nor are the list is empty. The lead operation cannot be performed, but to delete the last Nord in a late list, we will take a temporary her no nasty hurt and assigned the value off hurt their forehead. Andi heard with long point to the first North and the link list. The values of I loot this why Luke is used to travel still last but one Nord. Therefore we use less than lent off the link list minus two minus one will give the last note. So therefore we are using minus two. Once this file loop execute, you can see that at each iteration that he heard will be moving to the next north through he heard equal duty her dark next and finally he had will be pointing last but one north. In this case, it is north 40. Before we delete the north, we will make they'll point to be heard. Now the tail will be pointing towards the last but one north of the link list. We will use the hand equal. Toti heard art. Next on move the T heard pointer to the last note of the link list. We will retrieve the element that is present in the last note of the linked list through the l underscore element equal to be her dark 11. And then we will make tail dot Next. That is the next member off Day Lord as none on now. Dale points towards North 40 and we have the leader the last Nord. We will degrees the size of the link list and finally return the element which have been deleted. Now let us see the last operation that can be performed on link list that is deleting a Nord from anywhere in the list. We will clear the function, remove any on We passed a perimeter as position and here also we will take a temporary heard, no nasty head and assigned the value off hurt. So now head anti head will be pointing towards the first north of the link list. We will use a via loop to travels to the position of the leading the north. Suppose we're trying to delete North 30. That is the third North. The Via Luke will execute till the position, but one each time moving the T head to the next north. Therefore, if position mystery that is Third Lord, we wanted really It will move till position toe if you look at the internal structure of the link list The observed art They had no points towards the north. 20 Andi Her dart next has nor 30 as well as the her dark. Next dark. Next is North 40. Therefore, we can use a statement he heard dot next on assigned a value off the her dark next start. Next. That is the reference our value off North 40. When's this statement is executed? The t heard dot next will remove the reference from next North 30 on pointed towards the next to next Nord that is No. 40 and now the North 30. That is the third nor can be deleted. On the size of the list is discriminator as well as we can return the value, which is the leader. So these are the operations which can be performed on link list that is inserting a Nord at the beginning at the end as well as anywhere in between the link list on. We can also delete the north from beginning of the link list as villas and on anywhere in between the link list in all three operations off insert A new Lord s creator has the first statement on in all the operations whether it is insert or delete wherever we are using d heard it is a temporary hurt. We cannot manipulate our change. Our lose the context off the head of the linked list. Therefore, we are always assigning the value of her to our temporary heard no nasty heard and then working with the herd because if we lose the T heard reference then they will not be any way to access the link list. So always the reference off heard is taken in her temporary her. And then we perform the traversing of the link list. In the next section, we will see the implementation off link list and fightin. 22. Implementing Linked List in Python: in this, I can't even see the implementation of linked list on beytin. We will create an empty pipe and file and let us give the name of filers link list. The very first statement would be the important glass, which handles exceptions. We have already created an empty class to handle exceptions. We have also used the Empty Class and other implementations doctors for Q as well as stacks , the implement link list or single link list. We will clear the class link list since the link list users north. Therefore, we will create an inner class known as no. It does give it a name as under school more in the North class, we will define slots as the class member. It's takes in two and since variable started underscored element and underscored next, even then defined the indictment heard for the North class mistakes and to bottom eaters that is delivering time. Next, we will assign Perimeter 11 to sell dart underscore element that is the instance, very even, as villas, we will assign underscored next to the Valley off Next para media. This is all we have for the definition of the North's class. Now, even define the in it matter for the link list class this in it may 3rd off link list class will or take any arguments. We will have the members as head, which we assigned to none as well as we will have another member known as stale. We will assign this also to none. That means initially the linked list is empty. As villas, you will have a variable size, which we say it does. Zero. We will define Atlanta MMA, third on this method, will return the size of the linked list that is self dark, underscore size. Then we will define these. Empty my third this method also been or take any arguments, it will be done through our falls. Depending upon the size of the link list, we will define them. 1/3 art first, and it takes on argument. Does Element E. This method will be used to insert the north our limit at the beginning of the link list. We will clear than us nor using self dark underscore, nor on a positive para meter as Element E and next will be assigned to none. We even take if the list is empty. If the list of them. TV will make sell Dark Head as newest as well as sell dark. Then as newest else, that is. The link list has some elemental north. In this case, we will a sign us start next with the beginning of the linked list that is self underscored head. And then we will make head as the newest using self start on that score had equal doof newest, and finally, we will increase the size of the link list by one. Now, even defined I'm 1/3 art underscored. Lost to insert the element are the end of the linked list, and this method, also even clear than us ignored. Using Cell dot underscored North on past the element as well as make the next remember as none. Then we even take if the list is empty if it is empty, then said that on this, go ahead will be assigned us as well as self dot Underscore Pale will be a sign. Newest ends, that is, the link list is not empty. We will make self start underscored tail that underscored next as the newest and then shift the tail using sell dark tale equal do newest and then increase the size of the link list we've allowed defined him. It hurt as hard. Any and this method is used for inserting the element are no at any position within the linked list. So that will contain a part of meters element. He as well. Last the U. S. Which we will use for position as done earlier. We will create a new nor using self underscore north passing the element as well as none. Then we will have ah variability heard which is temporary hair on assigned the value off self dark underscore head. We will initialize a variable I equal to one and use of I loop with the condition. I less than position that this for us Travers the link list. Then the position we need toe insert and you know in Divi. Look, we will have a statement He had equal toe. He had Dr Underscore next then inclement. I therefore in consideration, the D head will be going to the next known using T had equal duty her dark underscore Next . Then we will use newest dark underscored next. Onda pointed towards D head that underscore next that is assigned to he had dot underscore next. Then we will make. He had not underscored next. As the newest on increased the Seiss of the link lists now even define them at her. Do they move or delete the element from the beginning of the linked list using Remove Underscore. First, it will not take any ballerinas. We will first check if the list is empty. If the list is empty, we raise an exception that is linked, lest empty. If it's not empty, we will continue with retrieving the value of the north of its. We are deleting, so we will have value equal toe self dark underscore head dot underscored element and then even you self underscored head equals yourself underscored had start under school. Next, that is assigning are moving the hurt to the next known, even dickered him in the size of the linked list by one. And then we will check whether deleting a Nord will make the list us empty after religion and the link list is empty. Head has already been made as no using served on D head equal to sell Dirty had dark next. So if the list has only one element on that element we're deleting already. Self start underscored art. Next will be none. But here we need to take care about the tail. We will also make the Taylors no and finally return value that is returned the value of the element which we have believed it. Now we will define them 1/3 to remove the last element from the link list using any move on the score. Last, we will check using the state same statements whether the list is empty And so we will create a temporary heard using T had equals self dark underscored head. We will assign the value for the variable I equal to zero on user to the via loop with the condition I less than leant off self minus two. So we will be moving the d Heard to last word one north. We will use t heard equal to be her dark underscore Next and then incriminating Inclement The value off I No. Once we leave the last part one nor in the link list reveal assigned self underscored tail equals D head. And then we will move the hair de head not underscore. Next we will retrieve the value stood now in the P head that is the last Nord in the link list. We will assign self dark underscore tailed art underscored. Next, that is the next Remember off. They'll do none on the agreement, the safe of the link list finally returned. The value of the eliminated between the leaders, we will know define method. Remove any which is used to remove the note from any position within the linked list. This remove any. We'll have a perimeter as position. Yet also, we will check whether the list is empty. If it's empty, we cannot remove or delete an element. If it is not empty, we will use t heard other temporary hair on assigned the value off her. We will create a variable I which is a sign value one. The values of I look to travelers in the position but one of the north which were the leading. So therefore we will have I is less than position that this view s minus one. We will move to be here with that position using he had equal duty her dark next, incriminating the value off I for the way I look. Then we will make the hurt not next equals D head the next dark next and finally delivered the value of size. And here we will use variable Then you to store the value of the eliminate Between believing so we will use value. We heard dark next dot underscored a limit because the head is the position but one which were deleting So he had heart. Next will be the in order which were deleted to retrieve the 11. We need t her dark next dark eliminated And finally we're done The value of the element Toby the needed. We even allowed to find him 1/3 display which is not part of the entity. But it will help us in knowing what all the elements present in the link list. So we will use display and the next statement We will have a steer equal doof self not underscore head, that is we're declaring a temporary head. No nasty head. We will use a statement while he heard. That is why he heard is not now We will print the herd, not underscored element. And then we will use an end g word. Do have an adult, then we will move the hurt too he had dark under school. Next, and finally use a print function Different. A new life. These are the maternal, which we have implementer for the link list a d. D. Let us now apply the operations which we have implemented in link list fighting class. Even create an object El equal to link list. And then we will say l not hard. Last was the value of the 11 intestine. Then we will person of the value 20 followed by 30 and 40. Let us display the list using the display method. You will run this program and take the output if you see, since we have used our last initially, the list was empty, so 10 was ordered then twenties order to the last or end of the link list as well as 30 and 40. We will apply may 3rd. They move first to remove the first element. We will also print the element, which has mean removed look. So let's say the leader and use L dark remove first and then look does this flavor link list. If you observe from this list, we're removing the first element using rebel first. This is the first element deleted and returned on. We have the list US 20 linking to 30 and then linking to 40. Let us try to our on element at the beginning of the link list. So evil ardent limit 70 at the beginning of the link list. Then again, we will display the link list letters run this program. You can find that North 70 has been insert er as the first start are the beginning of the link list we have already seen are lost and we have seen now aren't first we will look at how to remove the A liver are the end of the link list. We will use print the leader and then use the method Eldar removed last where does display the link list once more and you can see that the last eliminate has Beene deleted. That is 40 on now. The link list is 70 20 and 30. Even now, try toward the element after the position. Do let us display the link list. After RD, you can see we have provided position as to on after the position to the celebrant has be inserted. Now maybe use remove any to remove and eliminate from Britain D link list. We will pass to as the position that is. We're removing the north. Who and then this place the list. If you observe this was the list and then the applied. Remove any air position to so, nor 20 are the second position. Has Beene deleted? This is how the operations off 80 works on the link list. 23. Circular Linked List: in this section, we will learn about circular link list. We have already seen link list data structure as well as the implementation of the operations of link list started. Insert on daily in fightin we will now look at Circle a link list. Circular Linguist is also a link list. The only difference between link list and circular link list is dark. The last North in the circular late list will point back towards the first north of the circular link list since the links form a circle that is the last Northville reference again, the first north of the list therefore be colored as a circular link list. The circular link list will also have heard which will re present the first North in the circular link list as well a stale which will represent the last North in the circular link list and circular link list. Also, we have insert or delete operations. Insertion can be done at the beginning as well as are the end our anywhere in between the circular linked list, the same way delete operation can be performed at the beginning of the circular link list. Are the north can be removed from the end of the circling list as villas on north can be deleted from any position within the circular link list. Literacy and insert operation off inserting element are the beginning of the circular link list. We will define a method hard underscore first with stakes in an argument element. A new notice creator the same way that the link list that is we're creating an order 70 as a new north. The next member off North 70 will be pointing initially to none. We will check if the list is empty. If it's limpy, then the head will point towards the new node as well as since we need to create a circle. The next member of the new North will again point toward the new Nordic itself. If they're nodes in the circular link list, then the very first thing we need to do is to assign the reference in the last north off the circular link list. That is a reference of the tail to the new Nord. Now the day Lord are the last Nord will be pointing towards the new node. Then the next member of the new Nord should be assigned the value paid on help should now point towards the new north That is 70 as well as we need to increase the size of the circular link list. This is how a new Lord is inserted are the beginning of the circular link list. Now we will see how to insert a Nord At the end of the circular link list, we defined a function art last, which also takes in 11 does the pedometer. We will clear the new north colored as newest and here the new Nord a 70. We will again check whether the list is empty or not. If it's MDP, perform the same steps as we have performed for inserting in order at the beginning else. If the circular linguist is not empty, then the very first step is next member of the new North will be assigned Dale Dart. Next that is, will be assigned to hurt. Therefore, the link from the new north is pointing towards the head of the circular linked list. Then we will use the statement a lot Next equal. Do you est That is right now the tail is not 50 and next member off Norfolk 50 will be assigned to newest. Now the tail should point towards the new. Nor that as we say Dale is assigned. Took newest. So tail now will be pointing towards north 70. This is how a new lord is inserted at the end of the circular link list. And finally we increased the size of the circular link list. Now let us look at how to insert a new Lord within a circular link list. Let us say that we want to insert a new Lord. After third position, we will create a new s Nord. In this case, it is not 70. Then we will use the same steps and statements which we have used to insert a Nord in between. But a link list that is we will use our T hurt pointer and then of I look, we will move the T heard pointer to the Nord, after which we want to insert and then perform the same step as newest art. Next equal do he heard art next and then they had got next equal Do newest. There is absolutely no difference between the procedure off inserting a lord in between for a link list on circular link list because we do not have to manipulate the tail are the link of the last Lord which points toward the first north are the herd. Let us now see the delete operations in a circular link list we will define Um 1/3 remove first to remove the north at the beginning of the circular link list. We will check if the link is empty. If it's empty, we cannot remove the element else we create a variable a pointer that is old heard equal Don't tail dark Next that is now the last known which is represented by tail will be pointing towards the old head Fun Now head an old head are the same north. Then we will use still not next to point towards old head Dark next that is No 20. Then we will move her toe. Hold old her dark Next that is No. 20. On the size of the list is dick limiter. This is how a Nord is deleted from the beginning of the circular link list. Let us now look at deleting the Nord art the end of the circular link list Well defined, a function removed Last and then we will check If the list is empty else we will use the t heard that is a temporary hurt which points towards the first north off the circular link list. Are they heard? Then we will use of I loot. Same as what we have done in deleting the last north of the link list. We move temporary, heard their testy heard to last word one known. So when divide loop execute each time he heard will be moving to the next Norden the circular link list Once the vie look completes his execution, he heard will now point towards north. 40 people make they last a hurt. That is, we will shift. They'll position to the last Birdman Nor then we will make a lot next. That is next member off North 40 will be assigned the value off head. Therefore the link from 40 will be pointing towards the Heard. Nor that is the first note in the circular link list. We will then move the position off the her to be heard dot Next, that is, the north will be deleted and we will remove the element on legal ever decides by one. This is how the last nor is deleted from the circular link list. Let us now look at deleting the element from anywhere within the circular link list. We will define the function, remove any and passed the position of the north to be deleted. Now, if you observe, this method will work the same way as them 1/3 for deleting a Nord anywhere within the linked list. Because here we are not manipulating the tail are the hurt positions the D heard is assigned. They had value and he had will move the words the Lord Toby deleted but one. And then the link is assigned to the D heard dark. Next start next and then orders the leader. There is absolutely no difference between they remove any mattered, which we have seen for link list as well as for circular link list. Finally, we declare minutely size of the circular link list. In the next section, we will see the implementation of circular linked lists in Brighton 24. Implementing Circular Linked List in Python: in this section, we will cover the implementation of circular linked lists in fightin. Let us create an empty python file on Give the name as circular linked list. The very first statement were to be to import an empty class to handle exceptions. Then we will clear the class named as circular leg list on circular link list. Class will have an inner class known as North. This nor class we have already seen in the implementation of link list. They will then have the unit mattered for the circular link list. Class on this in it mattered is also same as what we have seen on implemented in linguist. We will also have the length as well as ism tima Thirds And these methods are also same as president and the link list last even now, like the myth heard art first, the uncertain Limmer at the beginning of the circular Linguists, this method will have a bad a meter for element. We've been clear the newest lord, using newest equal to self underscored north on past the eliminate e. On make the next member as none the next statement would be to take if the list is empty. If it is empty, then we will make self not head equals the newest as well as we will make cell dark underscored tail. It will do newest. Since this is a circular link list, we need to make next off newest point again. Back to the same north that is newest. If list is not MD, that is else. We will make self not underscore, then dark underscored next as the newest and then newest. Not next. He will do self, not understood head. Then we will move or point the Heurtaux, the new US Nord. On finally inclement the size of the circle a link list. We will define another matter that is our last and the last position in the circular link list. This method will also have E which is an element as a perimeter. We will again clear the same US Nord and positive value e and none. We will take it. The list is empty and the list is empty. We will have the same steps which we have seen in art first, my third and we will have newest, not next. Who sells dark? They'll God next than self dark, then dot next we will assign newest, then make self dark tale equals on us on increase the size of the circle. A linguist, We've allowed to find him 1/3 toe art in order with a limit at any position within the circular link list, This will contain two arguments. One he which is for a Limmer. And the next is the position that this pew s we'll clear the US North passing the eliminate Don, we will use a company Heard no nasty head mystery assigned the value of him we news available. I assigned the value one and use it in the loop while I is less than position And then we will move the head. But he had dark next and inclement and I knew if I ones that he heard beaches the position after which we want to insert the known evil Use newest dark next through the head dark next And then he had not next the newest on finally increase the size of the circular linked lists. The implementation of this mattered are dinny is exactly same as what we have seen in the linked list class, Even though they removed first met her to remove the element from the beginning of the circular link list. We will check if the circular link list is empty using the same statement which we have seen in the earlier implementation. No sense. This is the implementation for circular link list we will create, told her and assigned the value self dar till dark. Next. Then we will have a statement cell, dark tale dark next, pointing toe or head. Not next. We will then move the head. The ward head dark next and finally delivered the size of the circular link list are not only will it take whether the list is empty after the leading the note, if it is empty, we will make self start a legal do none because her Bilal already reporting toe none and finally returned the a limited present an older head using their done all her dark elements , we even arrived the implementation for remove last that is removing the element from the end of the circular Linguist, the evil First check. If the circular link list is empty, then we will move to the position, but one that is last north, but one using the same statements which we have seen earlier in the length list implementation and now we will may deal as see her and self dart the dark next as sell dark head on. Move the hair to the north of its We are deleting using t heard equal to be heard dark. Next on will treat the value off the element which we are deleting using value equal to be here the element and they get over the size of the surgical link list our and finally return the value of the north of a tree. The leaders And now we will see the last operation that is removed the element from any position within the circular link list. We will use a parliament up your starting position and the rest of the statements for the matter will be same as what we have seen for removing any element within the list in the link list implementation. And then we will have a disc limiter, which is again same as we have implemented in link list class. Now let us create an object. Let us say CIA of the circular link list class develop like had last operation Andi insert and eliminate 10 as well as in certain 11. 20 30 End 40 They will use a disclaimer Third No. Before we execute this program let us go through the display matter now in this displacement heard we are assigning p here to the head and then we are using of I, Lou, Guilty heard becomes none on renting the elements. But this logic will not work in circular linked lists. Because the next member of the last Nord will not continue, it will point back but it will have the reference of the head Nord. So if we apply the same same logic, then the violetville execute in finance times. So therefore we will change the Via Luke that is he will use available I and then assigned the value zero on inside off taking the herd as none they will use the condition I less than lend off sell If that is the length of the list on inside the value we will incriminate I So I bless. What now? Let us execute this program and see there. Is it here? We have in certain four elements that is 10 2030 and 40 That has bean displayed there does not remove the first glimmer on display the list. Eliminate tennis. The leader on blissed has bean displayed. We will use our first to our north 70 as the first element. Then we will again use display. It is not this program. You can find that 70 has been displayed as the first North. We've inaudible the last element of circular link list on again This clay when we had on this program that is a mistake here It has deleted north 40 but it is displaying the result Does no leader Letterman as 70? Let us go back and check the problem. Now we have a blade removed. Last salute as looker the mattered removed last in this method removed last. This is correct. We are taking whether it's empty. We are using temporary head Travers the last but one, nor to be deleted. And then we are using self Taylor sending us see her then self pain dark next as self dot head then dear. Okay, here. That is a mistake. This statement should have bean after assigning they'll equal to be heard and then we need to move. He had equal to be heard Underscore next. Then we will assign a lot next equal duty here, and we'll treat the value of the element here. It is not on this program Here. We got the correct razor that is the last north of beating. Luke is 40 and then we're displaying the list on 40. No, does mean removed. Let us try to apply the operation up. Inserting at the end. That is art. Last. There does Arden, Element 80 and then this crazy list we will run this drug now. Okay? And this month, they needed to be in cuffs. It is it on this program. Now, after deleting the Element 40 we heard the list with 70 20 and 30 and we have hardly element 80 at the end of the list. So this is how circle early blisters implemented. 25. Doubly Linked List: in this section, we will learn about double league list. Double link list is another 1,000,000,000 off link list. Doubling list is sometimes also called as doubly linked list. The node off a double link list has three members. 1st 1 is the element which contains the object. Or did I itself? The 2nd 1 which contains the difference to the next note in the double link list on these two members that is a limit and next are same as what we have seen a link list. It also contains the third member that this previous previous will have reference to the previous Norden. A double link list. Let us look at how doubling Calista created. Each element of the collection will have a note off a double link list. A new order will be created for element in on this, Nor will have next member as well as previous member assigned us None. Arnel. A new note for Element when he will be cleared her on this, nor will also have none on none for next and previous members Now. No, then should linked words, not 20. So therefore, the next member off north then will be assigned the reference off North, 20 on previous member Off North 20 will be assigned reference Off, nor Pen and the previous member of North. Then we'll have none because there is no nor before nor 10 as well as the next member Off North 20 will be none because there is no Nord next to North 20 the Devil it list will grow on. Let's say we have a North 30 both next and previous Off North, 30 will be signal. Then we assigned next off. No. 20 Reference see nor 30 and previous off North, 30 referencing nor 20 in the same way for North 40. Next off No. 30 will reference North 40 and previous. Off North, 40 will reference North 30 and then for North 50. Also next off North. 40 with reference not 50 on previous of North. 50 will reference North 40. This is Howard. Double link list is created. Now let us see how to create note for double link list. Since the Nord for double link list has three members, we have three instance Variables that does a limerick Petit via sat next on the nor Class for double link list will have slots member containing three instance variables that is element previous and next. We will also have heard on detail were hurt points to the first North in the double link list until points were the last note of the double linked list. We will have the in it with hurt for the class Nord, where the element is assigned to the instance. Variable underscore Element Previous will be assigned toe instance Variable previous that is underscore PR TV and next will be assigned to instance valuable underscore. Next, you can observe the difference but to be the North class off a single link list, which contains only two instance variables that is, a liver done next. But in this case, the North class off Doubly Linked lists has three instance. Variables that is element previous and next, as well as the in it mattered, will assign values for three instance millions. Now let's see an example of creating an order when this statement and one equal du Nord off 10 comma none and none is used in fighting. A new lord will be creator with the name and one where the element distant and next, as well as previous points towards no Arnon. We can access the instance variables of this Nord, for example, in one dot element and one dot previous as well as in one dark. Next, and we're not deliver right. No convinced then, and we're not previous convince None as well as anyone dot Next contains not reveal Kate Another North that is Nordoff 20 Common in common. None on assignment. To note to this will create are doubly linked list Nord with Element 20 as villas Next and previous pointing to know are then the statement and we're not next equal to n Do will assign a reference from next member off anyone to end toe. That is the reference a friend to will be stored in next member off anyone. Then, if he used into dark previous equal when one that is the previous member off Endo will be assigned a reference off North End one No. One's. We have seen the basics of how nor classes created for the blink list as villas, how the assignment operation works. We will see the details off in certain delete operations here. Also in Double Inc list, we will have insertion and deletion insertion can be performed at the beginning of the double link list are at the end of the Devil Link list as villas at any position within the double link list. In the same way, even removing in order are deletion off. A node can be performed at the beginning of the doubling list. At the end of the double link list. Has villas from any position within the double link list. The first operation we will see is adding a Nord are the beginning of the double link list . We will define um, 1/3 art first with takes in one para meter element. We will create a new Nord on college as newest that is nearest equal to sell dark Nord off e coma, none and none. This is the same statement how we have created the North End one in the previous slide. If you look a new Nordiska leader whose element is 70 then we will take if the double link list empty same way we have checked it for singling list. If double link list is empty, head and tail both will point towards the newest Nord. If they are north and double link list, then we need to use a statement. Newest start next equal to sell dot heard this statement. The next member off North 70 will have a reference off. Heard Lord. Then the statement heard dark previous equal the newest here, the North End, which is the Heard Lord right now, the member previous will point towards the newest known. And lastly, we will move the head toward the newest Nord. Using the statement, self doubt heard equal do newest and then increase the size of the double link list. This is how a new lord is inserted at the beginning of the linked list. The next operation we will consider is inserting the element at the end of the double link list. We will define a function art last and then pastie element as a perimeter, A newest Nordisk creator sanely what we have seen in the previous slide. In this case, we're creating a north 70. Initially, this North 70 will have previous as well as the next member us. Now we will check if the double link list is empty. If it's empty hurt until will boat point towards the new est in order. If the double link list is not empty. Then the tail dot next will be assigned reference off newest Nord that is, next member off. They'll note 50 will be assigned the reference off New Nord that the 70 then the previous member off New Lord will be assigned to Dale are not 50 on the last thing we need to do has moved the tail to the new norm using the statement self dark tale equal Lou Newest and then in criminally size of the list. In this light, we will look at how to insert a Nord within the double link list. We will define them. 1/3 are Denny and cleared the new north same average we have done earlier in this case in us, Nord is north 70 and then we will use a temporary variable that this t heard equal Do self dot Head. We will use a via loop Traver Still the position we need to insert the North. That is in this case. Let us suppose that we're inserting the Lord after third position, the Via Loop will execute and he heard will move to the next north till the position after which we need to insert the north in this case now that the head will be pointing towards North 30 internally If you see the head will point towards 30 on d had got next will point towards North 40 because North 40 is next door to 30 we will use a statement us nord dot next equal Don't be her dark next that is the next member off. Newest North will have reference off Nord 40. Then he had not Next which is not 40 Dark Previous will have the reference off North 70 and then he had dark next equal Do newest means that is the next member off North 30 will reference us Nord, then newest start previous will be assigned d Heard that is the previous member off newest Nord will be assigned the difference off North 30. This is how a North can be inserted at any position within the double linked list. We will now see how to remove an element from the beginning of the double link list we will define um 1/3 remove first on we'll check if the double link list is empty on Earth. If the double Inglis is not empty, then we will retrieve the element of the deleted. Using the statement element underscored Elite Equal do Self Dart Heard Dart element since heard points worth the first northerly doubling list. Then we will over the Heurtaux handout next, that is nor 20 now, nor currently becomes the first element of the double link list. And then we will assign previous Member of Heard has none. And finally, Redick element the size of the double link list and then returned the deleted element. Leave alone see how to delete a north. From the end of the double link list, we will define a matter known as removed last, and then we will check. If the double link list is empty, we will retrieve the element of the North to be deleted. Using the statement, he elite underscored elite equal to sell dark tale dart element that is element fifth. Then we will make cell dark tale equal to itself. Dart a lot previous this film off the tail to note 40 and then we will say self dark tale dot Next equal to none on decorum is the size of the double link list underdone the element which is deleted. This is how the last deliver of the double link list is removed. We've alone look at removing on element from anywhere within the double link list. We will define off mattered remove any and provide the position as a perimeter. Suppose we wonder delete nor 30 we will use d hurt and assign the value of deep heard that is the first north of the double Linguist now head as well as D Heard will be pointing towards north 10 We will use a via loop traveler still in order to be deleted But one in this case when we're deleting nor 30 that is the post north at the position 30 We will move t hurt the Lord 20 internally If you see the herd with the presents nor 20 will have dark next value referencing nor 30 on dark Next value referencing Lord 40 We will use a statement They had got next equal to the had Not next start Next on now next member off North 20 will reference north 40 And now he had dark Next will be north 40 since we have all the data Frenzer So he had not next is not 40 dot Previous is the member off North 40 which will point, are refer TOA nor 20 then then orders the leader as well as the size of double link list. Is decommitted on. Even the element really good can be returned. This is how the insert on delete operations are double link list works. In the next section, we will see the implementation of these operations and fightin. 26. Implementing Doubly Linked List in Python: in this section, we will see the implementation are doubly linked. List infighting. We will create an empty pipe and fight and give the Neymar's double link list. The very first statement would be same. That is, to import a glass which handles exceptions. We will create a class with the name is doubly linked list really cleared and in a class north that is underscored Nord and then use slots as the last member on a sign. Now hear this larks member will have three instance variables that is a limit be on TV for previous reference on next. For next difference, we will define in it but her for this inner class Nord. Now this method were taken three arguments that is, element PR TV for previous and next Next. Then we will assign itself dark. Underscore element equals element. The next statement would be self underscore. The TV equal to be on TV and then third statement would be self underscore. Next Equal do next. Once we have created the nor class, we will write the mattered in it for the doubly linked list class. This will not take any arguments. We will declare her using self dot underscore health and a signer two. None as the previous link as well as known as the Nextlink. The same way we will create Dale using self dark underscore tail with the nor class. And here also element will be none previous will be known as the last. Next will be No, no, we will use another statement. Self dark head Dark Next equals self dark do on. Then self dark underscored tail dark underscored. We R E V equals toe self dart underscored head. Now these statements are there because the herds next shirt point to tail on tails previous you 0.0.0 head Now, initially, this doesn't matter, because head and tails previous and next are none. We will then define size. Initially the V Zito. We will have the length with her Mitch Miller, done size of the doubly linked list and then we will have is empty Mattered, which were done, true or false, based upon the size there, the self dark size is equal to equal to zero. We even learned to find him 1/3 art. First you are and eliminate At the beginning of the doubly Linguist, it will take one para meter. That is the element Eat. We will clear the newest north using us equal herself dark, underscored Nord and then passed the value off. The element that is thank you on next will be known as the last previous will be No. We will check if the double link list is empty. That is, using self dark is empty. If it is emptying the self dot underscore Heard will be the newest as well as self dark. Underscored tail will also point towards the Nu est North else, the newest dark. Next, we're going to hurt that itself. Dark head and self dark head. Not previous. I will point the works newest, since we after maintain the next link as well as the previously No. One's. This is done self dark head, that is, the head should know. Point works newest No, and then we will increase the size by one. The next 1/3 we will define his are lost, which will are the element on north at the end of the double link list. This also will take in a perimeter E, which is the element we will create a new Esther Nord that doesn't USD equal do self dark under school north and then passed Element E as well as none for the next member on done for the previous one even then take if the list is empty. If it is empty, we will assign the same statements What we have used for art first and that is the double Inglis is not empty. Reveal yourself dark tale dark next equaled on you est and then in us dark previous equals yourself the tail and then we will move tail that a cell that tail equal do our point words newest on Finally in Callista size off the double link list by what we've allowed to find. I'm 1/3 hard any for guarding the element at any position within the double link list. This matter takes in two perimeters e for the element on the U. S. For position, we will clear the newest Lord using the north class and pass a limit as well as the next. And then previous member will be none. We will take a temporary heard nasty head on, assigned the value off. We will clear the variable I, which we assigned toe one and use. I didn't have I look while I less than the position that this be us, we will move the head through the head dark next and then inclement the value off. Hi. After the violent executes, the D heard would be pointing to the Lord, after which we are inserting an element we've allowing. Use us dark. Next do do you herd dark next. And then he heard dark. Next, I will point the newest. Then we will have be here. That next dark but devious will point the words newest and then us dark, devious. I will point towards the D had and finally increased e safe of the double, eclipsed by what we will define. Another mattered. Remove first that is deleting the element from the beginning of the double link list. We will check everything list is empty in the list is empty. We will raise an exception using the empty class See list is empty. This means we cannot remove on a limit. There's this commute value where we will be storing the value of the element, which is I believe then we will move self not heard to self dark head. Not next. And I said Doc, head dot previous to? No, because the next Nord will become the head north. Then we will be grim in the value self that size to one that is, we're documenting the size of the double linked list. We will now check if, after the leading whether the list is empty, if it is empty, we make self underscored Philae's No. And finally we will return the value of the element, which is Dimitri. We will define another with hurt, known as remove last, that they move the 11 from the last position and double link list. We will use the same if condition to check if the list is empty. If it is not empty, we will. Idiot r d heard that is temporary here on assigned the value off, we will use I variable on assigned the value zero the vile condition we will have. I listen length off the double link list minus two because we want to. Travers did the last but one known. Then we will move the Heurtaux He had dark next and in criminal devalue off I once we reach the tale. But one lord we will use a self not Dale equals took the hit. And then he heard we will move to the next Nord that is the north via billeted on retrieve the value of the limits of the Lord, which we are the leading. Using value equal to be hurt Underscored element. Then we will yourself dark tale dark Next equals no. And finally legal mnd size of the double link list. Andre done the value off. The last nervous is the needed Louisville now, right? Um, 1/3 toe. The move A women from any position within the double link list This method remove any will contain an argument the U. S. With this position, we will take every misters empty. If it is empty, we can ask Billy else. We will use t her. That is the temporary hurt on assigned toe they had. We'll create a variable I, which we will use in the Via loop. I less than position minus one that does. We're moving to her, but the north of its we want to believe you think he heard equal to he heard dark underscore. Next and then we will incriminate the value off. I 1 30 heard points toward the North Burton, which we want to delete. We will use D head dark next two point. Oh, the hair dark next dark. Next. That is next to next element. Then we will have be heard dark next dark next dot previous the point do here. And finally we will dig river the size of the double link list. We will also have the display Mitter with the same as the displacement heard off link list . Plus, once we have implemented this class, we will create an object El off the type doubly linked list. We will use l dark hard last. They are the eliminate in the double link list. Louisville art four elements started staying 2030 on 40. Let us display the double link list. Using this limit hurt, we will execute this program. Let us check for the better. This should be under school PR TV well executed again and you can see that the double link list with four element has be career. We will try to delete and eliminate from the beginning of the doubling list, they will use a printed matter to print the value of the limits, which is the leader, and then use l dark. They move first on display the double link list that is execute this program. You can see that 10 has been deleted on No list has only three. The limits we have already seen our last. We will see our first. That is adding an element are north at the beginning of the list revealed art 70. And then again, we will display double link list. You can see after removing the eliminate, the No. A new Element 70 has been added to the doubling list. We will now try to remove from an element family and of the doubling list, and after removing, we will display the double link list. Now, if you see 40 well delivered at the end of the doubling, Klis, 40 has been removed and now the list contains only three elements. We will see our drink on delivering it at any position, so we will use art any. Then pause the valley of the elaborate as 100 comma position is due afterward. England Is this play the contents of the linked list. There is another little rectify. The center now here the size it should be underscored size. Now you can see that the Nord 100 husband in sorter after position to. We will then try to remove any 11 within the double link list, remove any and then passed the position toe and finally display the double link list. If you've seen year, this was the list before removing the Nord art position to after deleting the note at Position two. Now we have the double link list with the limit 70 Pointing 200 mrs Pointing to 30. This is how our double link list is implemented in fighting. 27. Implementing Stacks using Linked List in Python: in this section, we will write a program in Beytin to implement stacks using link list. We will create a vital pile and give it a name. US. Stacks elite. The first statement We will use this from exceptions import empty this empty classes used for handling the exceptions. We will kill you the class link stack. And then since link list contains Nords, we will create an inner class known as node. The Senate class will have slots as the glass member, and it is a sign who instance variables. That is 11 time. Next, we will define an energy buttered pan or class on this in it with her takes in to perimeters a limit on next These statements office entered my third would be self start underscoring element equal to eliminate. The other statement would be sent that underscored Next equal toe. Next we will not create and in it but hurt for the linguist art class. First statement would be self underscore, head equal to none, and the next statement is self dot underscore size equal to zero that is weird in each lazing hurt to none as well as size of the stack. Toby zero We will create a length matter this land. Petar Winterton Sell dark, underscore size We will define and is empty mature this month. Hard winter done through our falls, depending upon the size of the stack. Even now, right, a push matter. It's takes in one para meter. That is element E. The first statement and the push method would be senate dot underscore head equal to sell Dark underscored Nord on past the value of the eleventy. And the definite says, Hey, there, this cell dart underscore Head, Then the next statement would be self doubt size, equal toe cell dot size plus one that is, we had incriminating the size of the stack. The other arm, a turn of the stack and he d s pop even define part matter and first statement would be to check if the stock is empty. So we will write. If cell dot is empty, then raise exception using the empty class followed by the statement value equal to sell darthard dot element. And then the next statement would be said. Dr Harry Quito said dark head dark. Next, we will not be agreement the size of the stack, so we will use self dark size equal does served outside is minus one, and finally, their turn. The value of the pop the limit. The next method of the duty would be to define top end up. Also, we will check with the stock is empty. If the stock is empty, we will raise an exception that is using the every class. We will say stock is empty. Then we will return. Self underscore Heard Dark Element. We will define a display emitter, though it's not part of the 80. But this method is useful to check the elements in the stack. We will use them as a temporary hair and assigned the value of self dark underscore head. Then we will use a vile statement while them great Tim got a limerick and used the n key word to have a narrow and then move them to damp dark. Next, we will use a print statement. This prints treatment will display a blankly. We will cleared an object unless off link stack, we will use less dark push with the Element. 10 subsequently reveal Bush element 20 11 30 11 40 and then letters display the stack using LS Dark Basically we wouldn't property element. So we will use print comma. We will use less dark What this pillar turned the pop deliver on. We will print the 11 which has me popped. We will again displayed in stack and then again pushed e element 70 on display the stock. Then we will demonstrate the working of the top matter So we will use print top deliver on let's start up And then we will again for Porter Value using Ellis Dark pop and then display the stack using ls dark display. He likes to hear this program and we see the very first thing is we have inserted for limits that is 10 2030 40 40 being d had. So we are hoping the liver So 40 million Pablo And now the stack is 30 20 in 10 30 being the top element, we will push 70 on delivering 70 will be Are you don't top up 30 since we have called the top mentor cooperative Hence the top of the stack that is similarly And then we were popping up So 70 is the top polymer. It will be parked out on now the stack will be 30 20 And then this is how a stack program is implemented using link list and fighting 28. Implementing Queues using Linked List in Python: in this section, we will write biting program the implement cues using link list. It does create a Biden file and give it the name Askew. Link the values the first statement does from exception importantly, to handle exceptions, then even clear the class and call it us link you This link you class will also have the inner class, nor with the same as what we have seen in a linked presentation. Off stats. It will also have an enigma Third, but here, with the head and size, we also will have served dot Underscore tail equal, you know. So we are maintaining two positions. Had anti the length and ism. Dimitar will be seen as what we have implemented in the link stacks class. Now we were defined a matured and Q which Dixon and a limerick he We will get a new Nord new equal to serve dot underscore north off e coma. We will check if the key was empty using If Self Dot is empty, we will make changes to new as new north in the if condition even check. If self dot is empty, then we will say self dark underscored had equal don't you know Els, we even say self dark. Underscore tailed are underscored. Next week will do you? No and then we will assign, said Dark. Underscored. A leak will do new nor and increase the size of the que. They're this self or not, underscore. Size equals no cell door dinners go size plus one even now, right from 1/3 as de que and this 1/3 will or take any other readers. The first statement would be detected in the queue is empty, so we will use If self dark is empty, then we will raise an exception that is Cuba's empty else. It even use value equal to sell. Dart underscored head guard underscored Element, which will store the value of the element which is ridiculed are removed from the cube. Next statement would be self doubt. Underscored had equal toe cell. Dart underscored her guard underscored. Next, that is, we're moving the herd to the next position. Then we really came into the size of the cue that is self underscore. Size equal to serve doctor in the school size minus even logic. After deleting rd cuming is the cue empty, so we will use if served art is empty. If it is empty, we will have self dart underscore tail equal to none. And then we will return the value, which has bean Did you using return value. We will not really find them 1/3 post and check with the Q is empty. If it's not empty, even you're done. Serve dark underscored head dark underscore element. We will not really find a meth hurt display. This method is not part of the unity, but it will be useful for us to display the contents of the U so even use them equal to self dot underscore head and then of I looked violent. Temper we will print. I have not understood a limit and use the n key word to printing. After each element, we will shift temp, toe them dark, underscored next, and then have the print statement which will print a blank life. We will execute this program. You check if there are any enters. That is an inner. We will rectify the center. I forgot to place a cooler at the end of the if condition Now even use the same statements up in here in de que what we have used in the elimination of queues using arrays, that is list. They like to give this program. We have another. So here there is no such thing as data, which is a list inviting where we are using north Soviet guillotines the escort data display emitter. No, no, it doesn't on this program we have inserted to elevenses que were getting 10 and 20. But there is a problem. The queue is not getting display. It's displaying none. Okay, the displacement third will print the elements in the Cube, but I will not return any value. So therefore it's returning none. We will remove all the print statements because printing of the elements off the Q is handled and said the displayed said No religious. Execute the program. Once again, we have inserted to allay birds in the queue. 10 20. The length of the queue is too. The teacher would be the first delivery. No, the Q is 20. We have inserted two more elements, so it will be inserted at the end of 20. Sir, it will be 2030 and 40 first element will be 20. There does the element of the hard site and then once we d cured and know that you will have only 30 and 40 29. Implementing Deques using Linked List in Python: in this section we will see the implementation up beacuse using link list and fighting. Let us create an empty pipe and file on Give it a name as Dick you link If you remember the dick you data structure works the same excuse with additional operations. That insertion and deletion can be done at both hearings That is head and the tail. So we have already implementer the link list. Plus let us copy the entire record on Easter in the B two linked what we have created. We will change the name of the class and we will call It does last link to you The north will remain the same in it Mattered of the north in our class will remain the scene the unit muttered of the link Dick You will remain the same as villas. Lenton is empty now The art first is the matter toe are a north of the element at the beginning of the linked list. So this method will also be president of the dick. Use linked implementation. We also have our last matter. This method is used to insert a Nord or element at the end of the did you now the irony mattered. Off link list class Will Arden dilemma anywhere within the list? But Dick, you doesn't have this operation. So we don't need this method? No. The removed first matured will delete and eliminate Are the north from the beginning of the did you So this method will be seen as what we have seen in the link list class. Now the next method remove last. This method was used to remove or delete the limit from the end of the link list. So here also we need to have this matter so that we can remove the element at the end of the video. We cannot remove the element from any position with under thank you. So this method will not be there as part of the the Cube class. This flame attack will remain the same and it is used to display the elements in the league . We will create an object l equals link like you. And then we will use our last We were display. We can use the remove first as well as we can use our first. And then we can use remove last operation. But we cannot have are any operation. And did you, as well as remove any operation in do you. So this way we can change the linguist class to make it a leak. You They did execute this cord and you can see the deserts. The desserts are saying Except art were not inserting are deleting at any position. We are only inserting and deleting from the herd are the pill 30. Trees - Definition and Properties: in this section, we will look at trees data structure. We have already looked at stacks queues link list. All these are linear data structures, but three data structure is a non linear dilla structure. Before we move on to the depth of priests, we will look at certain definitions which are used in trees. Are the terminology which is used in Greece? Did a structure on its properties. Now, if you look at the diagram, it's a tree. Defining various levels are departments inside a company. We have marketing saints, Fortis's manufacturing. These are all the departments form part of the company and then we have several other nodes in the tree. We will take up the definition along with the example in the coming slides, the first and the foremost Tom in the trees. Data structure is the root. Every tree will have a room. So in this case, the route off the street. This company on route is at the top level route will not have any period route. May on may not have Children. In this case, Route has Children's now the term parent. Palin is defined as a Nord, which contains Children. For example, companies apparent because it has Children. Sales to the painter because it's has Children, International is apparent. America is apparent as well as manufacturing. Is it better? All the other norms are not parents because they do not have any Children Now the term child, our Children in this green, all the Nords except company, our child, our Children marketing, sales, purchase and manufacturing our Children off company in the same way we have are the bottom of the tree North America and South America as Children off America. The police remember that company is a route. North Company is not a child because it doesn't have a pair on. Brute Lord will not have parents. Now we look at the term siblings marketing saints perches on manufacturing are all sublets , domestic and international, also civilly. But international and phone is not a sibling because they do not belong to a same painter. The terms that is paid child Children, siblings, descendants on and sisters are all same as defined in English language. The same terminology is also used in trees. Data structure. The next thing we will look at is the internal lord. Internet lords are also called us not leave notes. The north, which have Children, are known as non leaf north. Our internal lords In this case we have saints manufacturing international on America. Our internal lords are non leaf knows. Even company may be called as a non leaf nor, but since it's the root women are color doesn't internal Lord, but we will give a special name as root. Now we have extent and lords are leaf nodes. The North's viz do not have Children. Our child, our leaf nodes are extended lords, for example, marketing or chase domestic phone TV. UK, India, North American, South America are all leaf. Nords are extended notes. They do not have any Children. We've in love discuss few mortem start are used in trees data structures a degree often orders the number off Children off that note and we have already seen what our internal lords and water Extent and lords, what are leaf nodes and non leaf notes? The extent and lords are leaf north since they do not have any Children. The Diggory off the leaf nord is always zero and then the degree off internal or depends upon the number off Children. For example, route there this company in this tree has marketing sales parties as well as manufacturing as Children. So Diggory off company nor is four degree off sales north is too, because it has two Children. Diggory off manufacturing is too on the degree off. International Lord is three as villas. Beginning of America is now here. If you see we have a degree off a Nord, which is the number of Children of that north. But the degree of the tree is the Maxima off the Nords degree. For example. In this tree, we have notes with degrees zero. We have notes with degree three. We have notes with degree, too, as well as we have known where degree for so the maximum off nor degree is four. Therefore, the degree of this tree is four now. The next time has levels and hides level and hide board starts from the root note. We say route north as art level one, but the height off Route north zero the same way the Children off the root note will be at level two, and height of the tree will be one so and so forth in the last limit. Always the height will be one less than the level root is at level one. But the height of the tree at root is zero. Then we have a concept of Sir Preece. That is, if you consider here America is a Nord which has North America and South America as the Children. So this is considered as the secretary. We can also consider this as a sub three where sales is a brute lord of the sub three. The scene be fun, manufactured Even a single lord can also be considered as a sub three. For example. In this case, marketing is a leaf. No, it is also considered as suffering. Even though it doesn't have any Children this century will have Ah, hide zero and marketing will be considered as a route off this subject. We will talk about edges it just define relationship between different nodes in the tree. The relationship which we have already seen There's a parent and child relationship next really considered a part but consist. Off edge are CDs off edges. For example, there is a part between company toe marketing. The next part will be from company sales on domestic. So part is nothing work from the root lily leaf north. So in this case, if you consider company since National America on Leaf Nordeste North America, all the norms on the edges are highlighter to describe the But then that is dumb Forest forest is a collection off trees. If you consider the street company is a root Nord suppose if we remove the company then we have several sub trees are we can call it us trees Now, for example, marketing sales Now sales becomes the root for the secretary POTUS is surgery on manufacturing is surgery, so collection off trees is a forest. In the next section we will see a special kind off three known as buying military. 31. Binary Trees and it's Properties: This section covers about binary trees, types of binary trees on their properties by territory is an order tree on in a binary tree . Every north has, at most two Children on every child known is labeled as either left chain are a great shape . The left child always precedes right child. In order off nodes, let us consider a sample tree. The degree of this tree is for since the route Nord that is a as four Children, which is maximum. Let us consider another tree in this tree. The maximum degree of nodes is too. And if you look at the tree, none of the nodes have more than two Children. Therefore, the degree of this tree is too. By computing the degree of poetry, we can see that the first tree is not a banana tree, but the tree on the right side, which has degree toe is a binary tree. Let us now look at different types of mine 80 trees and here we have seven trees. If you observe all the trees have Diggory less than or equal to cook. Therefore, all the trees are by Mary trees. Now the first property off a planetary is that every vine military with end number of nodes has exactly and minus one edges. The even Nancy wanted a full banana tree full financially is also known as proper binary tree. A binary tree is a full binary tree. If each note has either zero or two Children. Now, let us look at a binary trie in figure one. Nordea industry has two Children as well as North Sea. Any has zero Children. Therefore, Pitzer Full binary. Three. Let me consider binary trees and figure two and three. They are not full by native trees because north, how zero or one Children. Obviously the leaf nodes have zero Children, but the non leaf nodes are internal lords have degree one. Therefore, they're not full binary trees. Let us now consider trees in figure four and type and figure for North. E of the tree has degree one that is only one child. Therefore, it's not a full by nearly three, as well as the Trie in Figure five. Note. C has degree one, that is, it has one child. Therefore, this is also not a full by military. Now let us consider three and figure six. If you observe all the non leaf norms have degree to that is to Children and none of the nodes have degree one. Therefore, this is a full binary tree as well as the Trie. In Figure seven is also a full Binali tree because all the intermediate nodes have Children do Now let us see another type off by an idiot tree that does a complete binary tree. A complete ban. Military is a binary tree where notes are each level are numbered from left to right. Without any gap, this might be a little confusing. So let us look at what the complete by immediately is now again. All the trees which are present on this light have Vigorito are less than two. We will consider the Trie in figure one Nordea is at level one that is the root. Then on the second level, we have no cnd at this level. All the loans aren't field that is a has left north as well as right now. So this is a complete finally pre let us consider the tree and figure toe in figure toe. We have the route Nord Art level one. Then on the second level, we have the left child that does not see. But there is no right child. Therefore, this is not a complete by any tree. Same way tree and figure three, we have right change, but there is no left child on that level. Therefore, this is also not a complete by in every tree the tree in figure four though on the second level we have both left and my child that a c and e Nords. But the third level the left child, is missing for nobody. Therefore, it's a gap at that level. Hence, this is also not a complete binary tree. The tree in figure five at level toe, both the left as well as a right turn this visit as well as act level three, though the right child is missing. But when we travels in level order, or when we travels level by level on start numbering from left to right In that level there is no gap. Therefore, Trie in Figure five is a complete binary tree. They will consider Trie in figure six. If you observe at all levels, all the Children are present. That is all the notes are present without any gap so this is also a complete binary tree. Now we will see the tree in Figure seven in Figure seven, the Nords Act Level two and Level three are completely filled. They're as at level four f, nor do not have any each other, but nor G has Children. Therefore, there is a gap in the level four on. It's not a complete finery. Three. The villain considered another type of a bind entity known as a perfect binary tree. The perfect banana tree is a binary tree. There are non leaf north. Have exactly two Children on our leaf nodes are act same level. Consider the Trie in figure one. All leave notes. That is C and E are the same level as villas the normally, which is a non leaf nor has exactly two Children. So it's a perfect by in every tree, the tree and figure two and figure three. Though the leaf nodes that is no F and figure two on not I in Figure three is a leaf, nor but non leaf nodes have degree one, that is, it does not have two Children. Therefore, they're not perfect by any recreates. Let us consider Trie in Figure four and figure for all leaf nodes are at the same level, but the nor D has only one child. Therefore, it's degrees one on. It's not a perfect binary tree. The tree and Figure five is a perfect binary tree because all the leaf nodes are at same level as well as all non leaf nodes are internal nodes have degree to the tree in Figure six is not a perfect by nearly three, though all the non leaf north are same level, but no de only has one tile darkest. Adi left. Therefore, it's not a perfect binary three, but three in Figure six is a complete binary tree. In the following sections, we will cover different reversal techniques off finally trees. That is level orderto. Everson pretty ordered Roberson in order and post order. Travers is 32. Level Order Traversal of Binary Trees: in this section, we will learn about finally to his level order reversal technique. Traversa means visiting each note in a tree. In this section, we will cover level order Travers, let us consider the street. This tree has route a and then it has left separate. Be on the right, sir. Pretty, though we call them as left Nord on Right, north or left Ceylan. Right in level order. Travers notes are visited by level from top to bottom and within levels. Nodes are visited from left to right. Therefore, for this tree, the level order Travers will be visiting the north packed level one that is the root Nord. And then moving on to the second level are the second level visiting the north's from left to right. That is no B and then North sea. For this tree level order Traverse Ill is visiting north a then Norby, followed by North Sea. Let us consider another example. In this case, the tree has three levels. So the level order Traversa would be visiting the Nord Art level one which has only one lord. That is a rule. Then moving on to the second level where we visit the north from left to right, that is Norby is visitor, and then North sea is visited. Then we move on to the next level. That is level three in this level. Also, we visit the Nords from left to right. Now let us consider another tree. The level orderto reversal of the street would be visiting north a followed by Norby on the second level. Then North Sea, which is on the same 11 and then followed by nor D on third level and then nor e as villas . Nord de. So this is how a binary tree is Travers in level order. In the next section, we will learn about three orderto Everson off mine a tree. 33. Preorder Traversal of Binary Trees: in this section we will learn about traversing binary tree in pre order. Let us consider the street where we have no day as the root on No day has a left Saptari Ara left child. That is not be on right sub tree, right child, that is not see in pretty order Travers and technique. The route has visited first followed by the left sub tree and then the right subject. Therefore the pre order Traversa of this tree would be visiting north a that is the root. Then the left separate that is visiting Norby and then Nazi, which is the right suck pre. The pre order Traverso is applied at every stage. That is for every secretary. Until all the lords of the three are visited let us consider another tree. This really have different levels on. We will apply three order Travers. So to start with, the route is visited first. That is Nordea Then the left suffering in the left. Separate again The route off the left sub tree that has bee is visited first. Then the left sub tree that is nor d And then the right separate. That is No, he know once we have visited all the north and the left separately off Nord A We need to visit the north in the right sir. Pre off Nord A now see is the route for the right subject off north A So therefore see is visited followed by the left surgery That is F that is the left sub tree off north sea and then the right sub tree off north sea that is nor G Let us consider another tree in this dreamy Do not have left sir Prefer Nord See Let us apply Preorder Travers. The route is visited first. That is not a on then the left sub tree off Nordea here. The route is not to be for the left sub tree off nor a so be is visited and then left surgery off Norby, that is nor D is visited, followed by the right salary off Norby that is not even be visited Once all the Nords are visited in the left, Separate off A. We move on with the right separately are fruit that is off Nordea here See? Is the root Lord for the right separately off Nordea. So c is visitor on. There is no left surgery for Nazi. So right. Summary off North Sea is visitor that is, nor G So this is how a binary tree can be traversed in pre order. Please remember that the three order Traverso is applied at every stage. That is for every secretary until all the lords of the three are visited in the next section, we will learn about in order traversing technique off finally tree 34. Inorder Traversal of Binary Trees: in this section, we will learn about in order to reversal in binary trees we will take the same tree which we have seen in the level ordered reversal as villas preorder Travers in the in order to reverse a technique, the left sub tree is visited first followed by the route and then the right secretary. So the in order Traversa of this tree would be visiting the left sub tree. That is not be followed by route that is not a and then the right sub tree that has no see Let us consider it another example The in order to Roberson for this tree would be visiting the left sub tree first in this left sub tree We have Norby as the root Therefore we again apply in order to Roberson that is revisit the left sub tree off no to be so we visit nor d first followed by the root of this surgery that is Norby then the right sub tree That is no e Once we have visited all the nodes in the left surgery we will visit the root of the tree That is not a then followed by the right sub tree of the route that is this Saptari in this right secretary North sea is the root. Therefore we apply in order to reverse into this surgery. That is we will visit left surgery off North sea. That is not f then the route that does not see followed by the right secretary off North Sea that is, nor g. This is the in order Traversa for the above three Let us cancer that another example the in order traversing for this tree would be visiting the left surgery first in this left secretary. We have no B as the root. Therefore we apply in order to reverse into this century. In this Saptari we will visit the left separate off Norby. That is no de. Then the route that does not be itself followed by the right secretary of would be that is no he once all the north of this Saptari visitor, we will visit the route That is not a followed by the right secretary off Nordea. We will again apply in order to Roberson to this surgery In this up three North Sea is the room and there is no left separately for North Sea. Therefore, we visit the route that does not see itself and then followed by the right secretary. That is No G. Please remember that the in order to reversal is applied at every state that is for every sub tree until all the north of the tree are visited. This is how in order to Roberson works 35. Postorder Traversal of Binary Trees: in this section, we will learn about post order traverse, Elin finally trees. Let us consider the same example and apply post order Travers imports ordered Roberson. The left separate is visited first, followed by the right sub tree and then the route therefore the post order Travers and for this tree would be visiting the left sub tree first. That is Norby followed by visiting the right supreme. That is not see then the route that is north a. Let us consider another example and apply the post starter Travers in for this tree. In this example, this is the left sub tree for route with no day. This left subsidy has Norby as the root. Therefore, we will apply post order Travers for this factory in this factory. The left sub tree is Norby therefore nor D is visited first, followed by the right surgery that has no tea is visited, followed by the route. That does not be. Then we move on to the right surgery off the route in this secretary Nazi is the route the apply post order Traversa For this Saptari that is north f is visited, which is the left separate off north sea, then the right separately off north CSG therefore t is visited and then the route that does not see itself. Once all the nodes in the right subterranean visitor, we will visit the route that is no A. This is the Post order Traverso for the above three. We will take up another example. In this example we have this as the left sub tree where Norby is the root. For this Saptari, we will apply the post started reversal. For this suffering that is we will visit, nor d first, followed by North sea which is the right separately. Then the root of this separate that is Norby. Once all the notes are visited in this factory, we will visit the right surgery. In this subsidy, North sea is the root. There is no left surgery. So we cannot visit any north. We will consider the right sub tree off North sea. That is no Genova visit, nor G then followed by the rule of this up tree that it seats it. What's all the nodes? Are visitor in the right sub tree. We will visit through. That is not a Please remember that host order Traverso is applied at every state. That is, until all the notes off the tree are visited. This is how opposed order traverse. It works in binary trees. 36. Implementing Binary Tree using Linked Structure in Python: in this section, we will look at the implementation off binary trees using links structure in Brighton. To start with that has created a bite and file on give the name as vine 83 even clear the class known as binary three on we will create an inner class known as underscored Lord. And this North class will have slots as its member, which takes in three instance variables. The 1st 1 is underscored element, which is used to store the data of the north. And then we will have underscored left has one instance which represent the left binary tree. And then we will have underscore. Right? Brittany presents the right binary tree. We will define the unit mentor for the North class on this, innit? My third World taken element left hand, right. As the Baron meters, we will assign before value of none to left and right parameters. Then we will use self dark underscored element equal to element and then sell. And that's cool. Left equal to left and sell underscored right equals. Look, now the Norden, their classes complete. We will define the in it matter for binary tree class. This in it with her will not taken any para meters. We will have a member self underscore route foodie Present the root of the binary tree on Initially it will be none. Then we will have self underscore size that is the size of the biologically. We will assign it initial value at zero. To create binary trees, we will define a function as Make three which will taken E as the limerick and then left at the left separately on light as they write some three. We will use self that underscore route equal to sell dart underscore known. This is the north which we have created for wine industry. We will pass the element e Then we will pass left dot underscore room that is the root off the left sub tree and light not underscore route that is the root of the rights of free. Then for this north we will make left not rule has none. And right dark under school route. Also as men that is a nordeste created Who's left and right sub tree will be now and then we will try to implement different travels or techniques. The 1st 1 would be level order level order will not taken any powder meters. We will clear an object of the type Que no que class We have already implementer part is link you since we have already implemented link you so we will try to use from cooling That is the filing in which we have commuted this link Few class import link que And now we will continue with the level order method. The next thing is really create a temporary route that s t equals yourself Dark under school group Now using the STI that is the temporary We will Travers deep by an Eritrean level order now in level order revisit the rueful cardinal level one So we will use sprint three dark underscore element on we will use end as the he were to separate the north are the elements of the tree with hyphen. Now we will in Q this north of it We have visited that is, nor people now we will use Why Lou, Maybe we will have the condition as not off you dot is empty and now we ridicu the 11 and assign it to be we will take if the dark underscore left That is the left childless prison . Then we will desert the child that the sprint left dot underscore element and then again used it and keywords. Andi, thank you. This north of its we have visited. That is the dark underscored left if the dark under school right, That is. If you have a right away then we will print the element of the right child that istea dark under school, right? Not underscore element. And then again, use the same and he were. And even in you, this element Hardisty dark under school, right? Let me have a visitor. So in level order, we have started with visiting the route and then in Queued that route we check that the Via Luke Whether the q is empty, we did a big queue. The route first If left childless Blizzard. We will visit the left child and in qd eliminated. If right turn this present. We will also visit the right turn as the last in queue The alert This file loop will continue until we have visited all the notes. Now we will write a method for in order Travers we will use in order and then pas de route . We will take If the route is not known, then Viva Il Call in order, Riker. Civilly, that is self dark. In order, we will visit the left, separate first and then we will visit the route. So we will have print the load off element and then we will recursive call in order to visit the right sub tree. So this is the implementation for in order. And now we were defined. The pretty order technique, that is three order This also were taken root as the perimeter on we will take if the root then for pre order the visit the route first. So we will use print the little dark underscored element. And then we will the curse A We call that the self dark but er does and it personally called the left sub tree that is root dot underscore left and then we will recur civilly called pre order the U off right that is visited right suffering Now we will define both starter Traversa. This post started Trevor several also take the route. And if the root we've recursive really gone who started to visit the left sub tree that is steal underscored left then in post orderly visit the right sub tree. They're the steel dot underscore right and then we will visit e fruit that the spread zero dot underscored element. So in this class we have created a matter to make the three and then four Travers and methods that is level order in order pre order and post order Travers or techniques. Now we will create the binary tree, even create an object, a equal do buy everything. We even create another object x by zer. And then we will also career all right? Yes. And I think these objects of the president's null binary treats. Now we will try to create a tree. We will start with the leaf limits so we will use X dart. Makes three and let us see. The element is 40 and we will assign the left, Sir Priya's none and rights aptly also as not. That is a object we are using, which is already creator on which is a none binary tree. Then we will have, let's say, another leaf north. Why they will use Make three on the element. Let's say that at 60 here also we will assign the left tree has now that is a and right three also as naled artist A. Now we will make a tree with objects it their desert dark make three and we will pass 20 And let us say that Lord, 40 is left child love nor Quincy So we will use 20 comma X that is the left child on There is no right side so we will use a that is the null binary Italy Then we will use another object are on we will use make three on Let's say it's 50 and let us say that North 50 has a right child as north 60 So we will use left Azlan and right child as why Because why is the object three president ignored 60 We will use another object s on may create matter on Let us see this nor will have 30 and assumed are not 50 is a left child off north 30 are not 50 is represented by our So we will use our for left child comma and a that did it doesn't have a great tape Now we will use another object e on Dima Third, make three and let us see this. Nor will have a limited 10 we will make nor 20 as the left child off this north end. So we will use that because 20 easy represented by objects said on we will say 30 is the right child off This north end on 30 is represented by s So we will pass s as the right shape now once we have created the street, let us try to privatise the street. Now if you observe the last state when that s t dot meekly it has a limited and it has a left. Ana Right sir, Please. So we will consider t as the root Nord. We will use t dark level order Roberson And then we will have a print statement to print a blank line and then we will use Did are pretty order Traversa We will also use t dark in order person and he'd our post order traverses. So this is how we will create a binary tree and then apply different Travers or techniques . Now let us execute this program We have another little rectified The center in order Preorder on post order takes in perimeter as root And here we have not provided route So we will provide route that the steed art underscore group the same way in in order. Also, we will provide the dart under school route as well as in post order. We will provide t dot underscore route. They did execute this program once more. Okay, year The queues also getting printer because we have imported link you class. So let us go to link you glass on. We have the print statements Here are we have the entire distinctly will try to come in these statements so that when the class is used now the president the binary tree program once more the first hour port is level order traverse in second or put is for pre order Traversa The third are produced in order to Everson and the fourth output is for post Order Travers it So this is how we can cleared, violated trees and then apply different Traversa techniques 37. Binary Search Tree Property: in this section, we will learn about binary search trees. Binary search trees are also buying any trees. The Binali surgery has certain properties. That is, every node in the binary search tree has a key on the keys in the left separately of the route are smaller than the key in the root as well as the keys in the right. Saptari of the room are larger than the key in the room. The left summaries and the rights of trees are also buying research trees. Let us take an example and see which one is a binary search tree. All the binary search trees are banana trees, but not all binary trees are binary search trees. We need to apply the properties off binary search tree. So therefore letters looker which ones are violently search streets. Now, if you observe all the north in these trees have numbers which represents the key. Let us consider the first violently trie in figure one for a binary tree. Toby, A binary search tree. All the keys in the left sub tree should be smaller than the rules on all the keys in the right sub tree should be larger than the truth. So therefore the Trie in Figure one is a buying elite search tree because the left separately of the rule is smaller than the room on the right. Sir, Pretty of the room is larger than the group So therefore, this is a binary search tree that is now consider the re in figure two and figure toe. The keys in the left sub tree are all smaller than the route that is six. But when we considered the left sub tree a fruit that is the sub three with Nord three and five, the left surgery off three is larger which Wyler is the property of finally search tree that is five is larger than three. Therefore, this is not a binary search tree. Now let us consider the binary trie in figure three and figure three. If you see the very first property itself, is why later That is the keys in the right, Sir, pre should be larger than the key in the room. In this case, we have a as well as to the key to is not larger than the route. Therefore, this is not a binary search tree. Let us now consider the binary trie in figure four and figure for a few. Consider the left. Sir. Perry has 13 and four, which is smaller than fight as well as the right separately has eight and six, which is larger than the route. But the rights a pre off north eight has six. It should be greater than the route. Therefore, this is also not a binary search tree. Let us consider the Trie in figure fight. In this figure, we will look at each nor, nor one is smaller than the room off its factory, and it's on the left side. So this surgery is a binary search tree. Let us consider the secretary with no date as the root in this Saptari Lord six smaller than its root. And it is on the left side as villas nor nine is larger than the route that is no day and it's on the right side. So this right, sir pretty is also a binary search tree. And then once we compare it with the route, all the keys on the left sub tree of the route are smaller than the room as well as all the keys in the right surgery of the room are greater than the brute. Therefore, this is a binary search tree. Let us consider the three in figure six. We have the key five as the root on all the keys in the left sub tree of the route are smaller than the route as well as on. The keys in the right separate of the route are larger than the group. Once we come, the second level that is the north three on Nord one is left off north three and a smaller on Not for right off north, three on its larger. Therefore, this is also a binary search tree. Now let us consider north eight Note six is left off. No day on a smaller than the key That is a as well as nor nine are key nine is larger than the North date and it's on the right side. Therefore, this is also a binary search tree on the notes and her to the properties of the binary search. See, therefore, this is also a violently search tree. Let us look at how search operation works. Let us consider that we're searching for key for the search operation starts with the route and then compares the key with the route. If it is equal editors, if the key is smaller than the root then the left, sir Prettiest searched on the right, sir. Please Discarded. But if the search element of the search key is greater than the root, then the rights up researched and left, sir, please discarded. Now, In this case, we are comparing the key for with the room it is smaller than the room. Therefore, the left separately searched in the left. Separately, we again start with the root of the sub tree that is No. Three we compared the key with north three does not equal, but it is greater. Therefore now the left sub tree is discarded and write some pre off north reasserts The element is found hands through is returned. Let us consider another key that is seven to be searched The search operation against starts with route. In this case, the key is greater than the route. Therefore writes up, researched in the right suffering a comparison is again may And in this case the key seven is less than eight then the left certainly off north eight asserts north six is the left sub tree of slowly and it is compared with the key it does not equal, but it is greater. Therefore, the right separately off north six should be searched. But since north six is the leaf element and there is no left or right sir pre for north six . Then the search operation returns falls. That is the key is not found in The three are buying a research three. Whenever search operation is done, we start with the room and then move on. The part will be reached the leaf nor, if the key is found. Then we returned through else video done faults. 38. Insertion and Deletion in Binary Search Trees: let us Now look at another operation in binary search tree that is insert operation Let us consider inserting a Nord with the key as to insert operation will start from the root. It will compare the route here We only compare whether it is greater than what Leicester We're not performing search operations Therefore we do not consider the equal Now if the key of the element mere inserting is smaller than the route The left Sir please considered part insertion If it is greater than the route then right sir, please consider for in such but in this case nor too is smaller than or five. Therefore we consider the left surgery that is not should be inserted in left sub tree of the group Once again the Nordeste checked with the element to be inserted in this case Also it is less than therefore The left sub tree is considered which is No one again we play the comparison that does No one is compared with nor to be inserted. It is greater that therefore we created nor and insert this north to the light off Nord One . This is how insert operation works now Let us look at the delete operation. Let us consider that we want to delete Nord with key for the very first condition. But the delete operation is that the note should exist in the three. Only then that nor can be the leader Delete operation also starts from the root and compared with the room if it is less than the left Sir, please consider on if it is greater than then. Right Sir, Previous consider in this case north for which has to be the leader is less than north five . Therefore, we consider the left sub tree in the left surgery nor threes consider north for is greater than or three Therefore the right Sir, please consider in the right secretary before not for and now we can delete north for let us now consider another scenario for delete operation for example it is considered dark We will be the leading north three deletion off a north which is a leaf north is very simple We can simply these without Nord on make the parent that this left child of the parents are right child of the parent as now on delete the north But the leading a non leaf north. Our internal lord is tricky now the north three in this case is a non leaf nor the delete operation starts from the route on the north will be deleted is less than the route therefore left Sir, Please consider now we formed the North but this Nord cannot really leader directly because it's a non leaf north and it has Children. The north three is the leader then nor one becomes the left secretary of the group Let us consider another scenario for delete operation supposed dark We want to delete north seven North seven is also a non leaf Nor, in this case, the eliminate To be the leader is greater than the route Therefore right sir previous consider on in the right sub tree We find the elements in the previous case of deleting non leaf nor the nor to be the leader had only one child. Therefore it was easy to assign it to the grandparents. But in this case, if note seven is really did we have do Children that is the left child on the right side Therefore we need to now choose which Nord needs to be replaced says that the property of binary search tree is intact. The scheme would be to choose larger Snowden the left simply as a replacement. Therefore, North six is a left sub tree off North seven, which is to be the leader on nor nine is the right. Separately, we will choose the largest Norden, the left sub tree. The left separately has only one north 36 if at all it hard. Other lords, the largest child would be selected on replaced with note seven. This is how the lead operations work in binary search streets. Inserting a nord is very easy in binary search tree, but believing a Nord from the binary search tree, we need to consider several cases. Deleting a leaf north is very simple, but where us for the leading a non leaf north, we need to make sure that the binary search tree property is intact. In the next section, we will implement the binary search tree as well as its operations in fighting 39. Implementing Binary Search Trees in Python: In this section, we relied the implementation for binary search trees in fightin. We will create an empty fightin file on Give the name as Vanity Search Street. We will create a class on Give the Name us by Neri Search three. We will create an inner plus Carla's underscored Nord, which has a member slots on which takes and limit the left sub tree as well as the right sub tree we will define on in It mattered for the north class and this initial entered will take three parameters. That is a limit left on that I reveal yourself dot underscore element equal to element. The next statement would be settled dart underscore left equals two left on itself, not underscore right equal do like and then we will find the in it mattered for binary search tree. Plus this innit matured would not take any perimeter. We will have remember as root and a signer to none initially as the less self dark underscore size between initialize 20 Now we will define and insert matter which takes and elements e as the about a meeting. This insert method is used to insert the Nords according Toa Binali searched three properties. We will use temporary route and assigned a value as self dot underscore route. We will use another temporary variable that this college has P D and assigning Drukman. We will use a Via Luke by the temporary look. We will make TT route and assigned the value as temporary. If the 11 e is less than the route that is the temporary route dart element, then we will shift temporary Ruto left sub tree using the road dark underscore left. Hence, if that is a lift, a limit e is greater than the blue dark underscored 11 Then we will move temporary to the rights up. Reusing Beatle dark Underscore Right This why Luke will execute till it finds the position of the element Toby Inserted DT route is the temporary object we are using to crack the parent to which the north should be inserted Now, Once we found the position, we will clear a Nord nor the equal toe self start underscore Nord pas de Element e We will check if the three has elements that is using the condition Self dart underscore route Then we will check if element is less than DT loop that this TT route will hold the parent because this element has to be 100. So we need to decide now whether it has to be added as a left are as a like so the condition is eat less than TT route, not element. Then we will assign TT route that left that is the left child as the no else we will assign it as the right child using TT route Dark on Let's go right equal. You know, this is how insert matured is implemented. We will now define a search pattern to search the element in the binary third Street. This search my third will have key K as the perimeter. We will use a temporary route on assign it to the root of the tree we will use via loop with the condition to you. If the 11 to research that s K is less than the look not element Then we will move the route to the left sub tree using the route equal toe reroute dark underscored left. A lift is greater than I feel dot Underscore elements. Then we will move the route through the right sub tree using zero dark on that score. Right? Else. If the eliminators found at the root, we will return through. If the eliminates found it will return. True. Once the violent perpetrates that is, If a limit is not found, we will return faults. Now we will define the Travers or techniques That is level order in order. Pre order and post order. Now, these methods we have already implemented and buying any three class. So here we will use the same methods we need to also important the link you since the length you classes used in level order Travers. Now we will create an object be of the tight binary search tree. We will use the dart insert on. Let us try to uncertain limit 70 the same way we will insert a liberty 30 90 40 50 and something as 100 and 10. We will try to certain Oliver be dark search. Let asserts Element 40 there has execute this program. There is an error here. Look a signified the center the Nord, which we have creator with the element e letters. Ah, see the north class. Okay. In the inert matter, they will assign default value for left so pre as Nin on rights of Priya's None there has execute this program that there are no editors now it's not giving us the correct answer. So let us use P dark in order and then passed be dark on the score route to check the elements in the three. No, in order results in order working. That means the tree itself has not being created. Therefore, let us figure out what is the problem. In the insert matter, we have used temporary route. We have travels using why? Look, we have created the Lord and we are taking if it has left a sign or if it is like here I forgot a statement. Initially, the binary tree will be empty, so we will use else. Self guard underscore route equal Do Lord, that is I forgot to make the first element as root. Another destroyed toe. Execute this program. We got the lizard. Let me just give a Prince statement Here I regard the lizard. The tree has been created. Using these notes on it is returning through because for peace phone, let us try to search for 45 interference foot's. So this is how binary search tree is created and implemented fighter. Now we have performed the insert operation using iteration. The same insert operation can be performed using Rick Ocean. We will try to right the recursive operation off inserting Nords in the binary free. We will define um, 1/3 record insert. Now this record insert were taken to paddle meters. That is the rule on the liver to be inserted. That is e leave it tick. If the route is empty, that is the binding the search trees empty. If it is empty, he will clear a Nord using self dark under school Nord on passing the value off and then return the node. Now, if by any research is not empty, reveal use condition, the less than temporary do dark element if the element will be inserted is less than the route. Then we need to recursive Lee Call the left separate So we will use Tedo dark underscored left equal Do sell dark. We're calling the recursive insert function passing the route dot underscore left that is the left separately as well as the element to be insurgent else. If that is LF is greater than he looked dark underscored element. Then we will coercively call the rights of tree that is steal Dart underscored right equal Do sell dart records of insert on because the arguments as the root of the rights of pre Andy Element and finally returned the temporary route. So this is how a recursive function is written for intervention. They will try to implement the records of calls that is, be dark the cursive insert for the same sort of elements. No recursive insert Nixon to perimeter that is the root as well as the element to be inserted. So we will use be dot underscored route as the parrot on passer Didn't every call of the recursive function. Now let us try to execute the program on We will search for the element 50 We are not getting the correct wizard. They're just figure it out here The first statement we have guard the curse of insert using the dark underscore group and passed the value of 70 Now be dart underscore Route is not initially so. Therefore what we will lose We will use be dark under school rules that is assigned the value of fruit as the first Nord So 70 is the first element, so we will call be dart recursive insert on pass None because there is no room on the value 70. Now, once we clear north, 70 as the root, then we will be able to subsequently gone the recursive in third functions to insert other elements like has executed this program. Now you can find their The buying researching has been displayed as well as the asserting the Element 50 return through like a certain 11 25 better dance faults. So this is how the operations off insert on search in vinyl research tree are implemented in fighting. 40. Priority Queues & Heaps Introduction: in this I can be. We learn about priority queues. We have already seen cues on their implementation has an array based as well. Last link to bees Que is a collection of objects which follows first and first of principle . For example, Hughes can be applied to customers waiting for service, but in many dear time applications. First in first out policy does not suit, for example, in air traffic control their several parameters to be taken into consideration for airplanes to learn. We cannot just consider the first in first serve basis. We also need to take into consideration the waiting time to learn the fuel remaining and several other perimeters, though the first in first Our policy is reasonable, but some situation requires objects to be prioritize. This is achieved using priority queues, but I don't think use our collection of tired eyes. The objects are elements priority queues allows, eliminate insertion and removal of element is based upon priority. AKI's associative when element is inserted in the priority queue element with the minimum key will be next. Delivering Toby removed, we will move further and talk about keeps Heap is an efficient realization of priority queue that is heaps used the concept of priority queues. A heap is a binary tree which has a relational property on a structural property. The relational property talks of our Dickie that is in hate. The value in each north is greater than or equal to those in its Children. Now, when we're saying greater than that means we're trying to create a maximum. He and destruction properties are keep is a complete buying drink. Three. We have a maxi pad as well as many for a min heat. The relation property will change. That is, the value in each note will be less than or equal to those in its Children. Let us take an example of priests since heaps on the thing with trees to. Therefore we will talk about the relational property and structural property, though we have maxi pads, villas many. But at this stage we will only consider Maxie. So for the Trie in figure one, let us talk about the relational property that is, the value in each north is greater than or equal to those off its Children. So the tree in figure one satisfies the relational property on, whereas it's a complete violated three. Therefore, it also satisfies the structural property. Therefore, it's a he let us consider the tree and figure toe. All the notes have the value more than their Children, so relational property status face. But it's not a complete by negatory. Therefore, structural properties not satisfied hands. It's our ducky. Now notice. Consider a tree in figure three. If you look at note for its child is greater than its value. Therefore, it doesn't satisfy the relational properties as well as its not a complete ban military, so it doesn't satisfy even a structural property. Therefore, it's sort of none of this talk about the green figure, for it satisfies the relation property as well as it's a complete ban injury, and it satisfies even the structural properties. Therefore, it's a he. The tree in Figure six does not satisfy the relational property that is not five smaller than its child. That is not six, therefore, relational properties not satisfied. It's a complete violent tree, so structural properties satisfy. But since relation properties not certify, therefore it started. He let us consider Freon figure pipe. It does not satisfy the relational property, as the leather does not satisfy a destruction? Probably. Therefore, this is not a he. In the next section, we will talk about the abstract later Type off heaps. 41. Heaps Abstract Data Type (ADT): in this section, we will talk about heaps. Abstract data types. Heap is a prioritized. You ask you stores collection of objects with the policy of first in first out the same way heaps 80 stores objects, but they are prioritized objects, the members of Heap Media, Max size, current size as well as the heap list. Here, the maximized retirements, the capacity of the me that is how many objects can be stored in a heap and the operations off. He paid media insert that is inserting and deliver on, assigning a key to their deliver and then delete Max. Now here we're talking about Max, because at this stage we are considering too deep to be a max heap. Therefore, we have the operation as the lead Max and Min Heaps. We can have operation as the treatment, the elite Max operation that removes and returns to deliver. It will always remove the root element. Then we have on Operation Max, which returns the value of the root element without removing or deleting it. And then the lengthen is empty operations, which we have already seen earlier. In He Benedetti. Most important operations are insert and delete. Max let us. Now look at how insert operations are done in heaps. We will insert and eliminate 20 in the heat. Initially, the heap is empty on Element 20 will be inserted on this Element 20 is the root. The next element we will insert is 14. This element will be inserted to the left of the route that is, nor 20. To satisfy the structural property and the relational properties. Check that Does the parent should be greater than the Children Now. Next, we will answer a limited to element who will be inserted towards the light of the route to satisfy the structural property here. Even the relation property is satisfied. Next we will try to answer North 50 north 15 will be inserted to the left off north 14 to satisfy the structural property. And now the relational properties not start. This fight that is not 14 which is apparent, is smaller than its Children. North 15. So therefore the time described with its parent that is 14 s word with 15 this operation is known as bubbling and now not 15 ist segment e route to satisfy the relational property. If it decides face no slapping is done, that is no bubbling is done else it will be swelled with the route. Now let us consider inserting north in north and will be inserted towards the right off north 50. This satisfies both structural as well s relational property. The next Nord Weevil insert is nor 21 so the north are eliminate. 21 will be inserted to the left off north. Who to satisfy the structural property. But it does not satisfy the relational property. So therefore it is far. But with this players that is bubbling is perform on 21. A swipe with nor too no at this sink with its parent, Bedard, 20 is less tha it's child 21. So again the swiping are the bubbling operation is performed and we swap 21 with element are north 20. Once we leads the route, we end this web operations are bubbling terminates. This is how insertion is done in heaps to satisfy both structural as well as relational properties. They even look at how delete operation works on heaps. When the lead Max operation is performed, it believes the root lord from the heat and deleted eliminators return. No, the last Norden, the heap will be placed with the route. This satisfied the structural property. Now we need to look at the relational property. The route to is violating the relation property because it's Children is greater than it's it So Therefore now the bubbling operation is performed. The Route 11 will be swabbed over the limit which is greater among the two Children in this case, nor 20 will be swept with north to once this operation is performed, the relational properties also maintain Now once again, let us try to apply. Delete Max, This is the heat which is remaining And once we apply the village Max operation, the Route 20 will be the leader on return. The last element in the heat will be replaced with the route and this and this face the structure property, the relation property sick That is the larger among the two Children that is 15 and to ascribe with the route and then again a district with this Children If relational properties violated again this wiping his perform. So in this case, North 14 will restart with North. Then once this is done, the relational properties also start This way we have seen the bubbling operation an insertion. It is also known as a probably because after insertion, the eliminate district with its parent still the root and bubbling are swiping. Operation is performed aboards. But in case of delete operation, the last north and the heat is replaced with the route which is the leader and then bubbling. Operation is performed downwards till the leaf Nord So this is sometimes known as down bubbly. In the next section, we will implement heaps and fightin. 42. Implementing Heaps in Python: in this section, we will implement heaps data structure in beytin. Let us create a bite and fine on give the name as heaps. The first statement would be to import empty class to handle exceptions. We will clear the class on college has a day he here we will be using a Rabies re presentation That is the list off fightin to implement heaps we will define on in it mattered which doesn't take any arguments. We will have a Mac size variable which even initialize to attend. We will have a list that is underscored a tough on. We will initialize all the elements off data Toby Minus went using Self Doc Max Ice And we will also have a member as current size with people in place to zero. We will define the let matter which Miller done The letter of the later we will define is empty which will return true or false. Depending upon the length of the list, we will define Max Etch Matured, which represents the maxim 1/3 of the heap led and this my third even check If the current size zero if it zero we will raise an exception that heap is empty. Else we've Elarton self dark underscore data off one does the data starts from zero index. Here we are assuming the heat to start with the next one. Even then, define the most important function. That is the insert. Since we are using Arabize representation that is listed fightin, we will check if the current size as equal toe maximum size that is max size. If guarantees it will the Mac size, they will not be able to insert any element in the heat. So evil raise an exception, saying no space else we will incriminate the current size by one on. We will use a variable I on a sign like that in size of the heat, reveal use of I loop on. Very first thing we will check. The condition is I is not equal to one on a the element e, which we are inserting. They have not used the parliamentary. So a sign about a meter e to the insert mattered. We will take whether Element E is greater than self dark underscored data off high, divided by to hear the division is indigent division because indexes are always in teachers . This wild statement is used to apply the relational property so the state were inside the violetville half self not underscored. Data off I is equal to self start underscored data off high, divided by two. Then we will decommitted I to I divided by do now these statements in the violin Britain to perform swiping that is the bubbling operation, and we're performing bubbling from the the last north of the heap, the dependent that does wait each time we are dividing it by to reach to its better until we leased the route. Now, once this is done, self dark underscore data off. I assign the element. This is how the insert mint heard will be implemented. The villa. Implement the delete max mattered and let us give the name of the matured as delete Max. This delete Maxima third will not take any arguments since it always return on. Deletes the root element we will take if the heat is empty that is self dark. Underscore there in size is equal to equal to zero. If this is truly evil race an exception, saying he is empty. If the heat is not empty, we will use a variable X and assigned the value off self underscore data off one which is the root Nord. And then we will use a variable life which we will assign the last element of the heap that is underscored. Data off self dart underscore current size. Then we will be criminally cutting size. We will use I variable, which is assigned value one on. We will use a temporary I very even, Let's say CIA, which is assigned to we will use via loop while CIA less than equal do self dark current size. Then we will use an if condition if CIA is less than sell dark, current size and self dark underscored data off CIA is less than self dark underscored data off. See, I less one that does. Here we are taking which child is greater. Then we will inclement See, I buy one we will take by is greater than equal Do self dark underscored data off CIA. Then we will break Now This statement that is, if my greater than equal to self dart underscore data off, See A we are taking with the last element that is why is greater than equal do its child. If it is greater than equal to it. Say that means the relational property is satisfied. Therefore, we will use self dot Underscore data off I and assigned cell dart underscore data off CIA and then we will the place I with C I that does we are replacing The index is off the list . We will make CIA equal toe. See, I multiplied by two. And finally we will make cell dark, underscore data types off I and replace with the elaborate why, that is the last northern e he now this. Why loop on the if conditions are used to perform bubbling operation from Rupe in the leaf node On that each generation we are taking with the relational properties satisfied. This is how the Delete Max operation is implemented and fighting Leven and create an object it off the glass away. He we will insert some elements using the insert mint her letters insert 25. Then let us say 14 Let's say 2 11 2011 10 on 11 will now this will clear the he let us drink the elements of the heat. That is each dot underscored later even now executed this program and see the desert. You can observe you there Since we are using a database, representation are we are using lists and fightin to implement the heat. Uh, we are starting the heat from the position one that is the index one of the list. So therefore, the big zero is minus what on? We have inserted six elements. So we have the six elements and certain and the rest of the elements of the list R minus one. Since we have created a list of Max Ice Tent on a sign our 10 elements The value minus one , we will now perform the operation of the elite Max on the heat. It's dark. Let's say believe Max on again. 20 He we have another here. Let us rectify this currency. I should be underscore current size. There's execute once more. You will find our 25 with the largest element which has been deleted. So this is how he did. A structure is implementer infighting 43. heapq Module in Python: in this section, we will look at the heat Q model and fighting. Let us clear the fight and fight and give the name as heap you money fight and provides a building model known as he que on. This model has several methods, such as he push He popped, he pushed swap typify has villas and largest and end smallest. Let us look at how these methods off hit you more new books. Very first statement would be to import keep you morning on use as heap In our writing program we will create a black list with the name as N We will use heat dot He push on bus The list has velocity. A limit will be inserted in the heat. We will insert 20 We will insert another element 14 the same way we will insert five on Element 15 11 in as well as a limit to now we will print the list. Let us run this program. The list has been displayed, but usually what happens is when we are deliverance to the list it will be assigned in the list in the sequence as they're ordered here, you can find that a limit to is the first element in the list, though we are inserting a study. And so the MMA turn he push of the heap Human Yoon is creating the list as a heap. We will use another matter known as he pop of the heat Morning. So even use heap dark he pop on pastie list. We will print the element which has been deleted from the heat. Selectors use aspirin, He dart, he pop, he confined dark The element to has bean Pablo, we will again currently heap that is the list. You can observe that the heap has deleted the element to on here. The list is displayed after the delete operation has been performed. The he predicted a structure which we have implemented in fightin was a Maxine. But the heat human you hear uses amend him So therefore the root of the heap has the minimum element. Now he also has, um Attard Bush Bach. We will use heat dark, a push pop and pass the list as well as the liver to be pushed in this case, let us past the element has 80. We will print the tape again. Now you can find art he has deleted the route. That is the minimum Eliminate five on as well has inserted in the same operation Element 80 . We will use print statement here. Parenti, push and pop. If you see this is very clear, it is popping out the eliminate five on at the same time pushing the element 80. The heat model also has, um, 1/3 known as N largest. Let us create a list element on we will use Heap, dart and largest. The first argument would be an intermediate that does the number off largest elements in the heat to be returned. So let has used three comma and we will now print has one That is the list containing and largest numbers of the heat. You will find that the heap hard five elements on the largest are 2089 15. We can as well use dark and smallest on let us past three comma the heap itself that is in and we will print Do you can find our and small less numbers from this heap as me but returned The heat model also has a maternal Heaphy fight. Let us create a list l three with some elements. For example, 2014 to 15 10. 21. Now this list is not a heat. Therefore, we will use Keeper Dart typify that is make the list l three as a heat and pass the list l three itself. And after the butler did sprint the list l three, we will bring the list before he defined as well as after typify. You will see that these are the elements which was there in the list as we have creator. After applying the hip ify operation, the list has been converted into a heap. So here we have seen the heap you more you as well as we have demonstrated how each my third off heap Humadi books. 44. Graphs Introduction: in this section, we will learn about graphs, data structure on grabs, definition as well as its properties. Graph is a collection off objects called as witnesses on together with its relationship between them called as edges. So basically, graph consist er, second Fortis's, for example, a BCG. These are the settle purchases, and then it has a set off edges and eat it in a graph joint stewardesses, for example. The certain fetches Hey Toby and a toady and then be to see and be to the and finally on Ed from sea to the So. A graph is a collection of certain Fordice's on certain off edges each. It defines a relationship between to work. This is the graphs. Data sector has got many applications. For example, in road networks are roadmaps, set off witnesses will be cities and set off edges are the roads connecting the different cities. Another example would be flight network, where set of workers is our cities. Our airports and set off edges are the flight parts with them in the airports. Let us move further with the concept of graphs, edges and the graphs out of three types of director, dead's and on director Dead's as well as waited. Just we will talk about the director legis director that's has an orientation. That is, if there is an edge between 80 B and has an orientation, that means the it is only between a Toby and not from B to a. So this graph is the director got where every edge hasn't orientation. In the undirected graph, EDS has gotten orientation. That is an edge between Toby RB to A are saying So this isn't earn director. Good up. Now we will talk about waited drops when each edge is assigned a waiter at a cost, then the graph is known as awaited grab, for example. This is an earned Eric could grab, and we have a sign, some weights to the edges. So this is known as waited on direct good grub the same way the other graph is a director graph, and once we assigned weights to the edges, it is known ass later that a good graph, the end workers is our end. Points of the graph is are in a graph when it's connects between two workers, is both vortices are known as end workers. Is our endpoints. If there is an edge and that it is a direct credits, then the first endpoint is the origin. But example we have an edge between here to be. Origen is work takes a on the other word X, that is B is the destination. The word is is may have our going. It is our incoming edges. The director is whose origin is doctor Vertex is known as outgoing Edge. For example. For workings, be there is an edge between be totally so be to the edges and are going edge in the same way the edge would be to see Isn't outgoing edge, the director did. Whose destination is that word? It's is known as incoming edge. For example, for workings, be the edge from A to B is an incoming edge. Therefore, for workings, be there to are going edges and one incoming it. The degree of the work takes is the number off incident it just off the work. It's that is, for workings be They are three edges, so degree of the word eggs B is three degree of a Vertex can be categorized into in degree of a vertex and our degree of over days in degree of a Vertex is the number of incoming edges of the word days. For example, were takes. B has one incoming edge from A to B. So in degree off work, Rigsby is one. The our degree of a vertex is the number of arguing edges of the verdicts. In this case, forward takes be the out degrees to because they're too old going. It is from B to D as well as from B to C. There is another term known as Spot, but is a sequence of pitches starting art one word aches and ending on another word. It's, for example, in the first graph, it will be Vitaly Andi to see is a part starting from vortex A and ending our toward X C in the same Lee for waiter director graph. There is a part, but I'm here to be B to C and then see to be so the bad starts from what it's a and ends at . What makes the The term cycle is a part that starts and ends are the same word. Eggs, for example. In an undirected graph, there is a cycle that is, that isn't EDS. from we're takes air to workings be then workings be toward things D on from workings D back toward x eight. So there is a cycle in the same way. Let us find cycles in Vater directed graph. There is no cycle in waiter directed drop. We already have anus from a 20. But suppose if he have a niche from D to A, then there is a cycle from A to B be today as well as D to a. 45. Graph Abstract Data Type (ADT): in this section Lettuce Talk about graphs upside later type The graph CDT has create as an operation to create a graph it end witnesses and no edges. Then we have an armed operation which takes into perimeters you and we That is to insert an edge from were takes you to work next week The same baby How a delete operation delete you comma V, which is used to remove an edge from work, takes you towards XV. The operation it is returns the number off edges in the graph and the operation witnesses will return the number of work This is in the ground the exist operation that has exist. Yuko Movie returns True If there is an edge between where takes you and we're takes me the operation degree which takes in argument as the vortex Millerton the degree of the work takes you in degree a few returns Thean degree off or text you on out degree of cortex. You will return the our degree off where takes you the operations degree in degree and our degree will return and teach your values whereas the operation exists will return a Boolean value through our faults as for last. The operation edges and workplaces will return, and indeed a value that is number off edges on number off work this is the operations are on delete will take our givens as divert asses that does the two endpoints u N we 46. Implementing Graphs in Python: in this section we will see the implementation of graphs led in fightin. We will create a part and fine and give the name as graphs. We will clear the class with the name of scrap and then we will define an enigma. Ter, with stakes in number of workers is as an argument. The next statement would be sell dark on the school udt mark with three presents a descent metrics and we will use number I'm onion which has, um, 1/3 zeros and we will pass the argument as witnesses. The method zeroes off numb, primordial is used to initialize the rows and columns off existence Emaar tricks as zeros We need to important time or you. So we will have a statement import numb pie As MP on we will use NP dark zeros. This number I modeled by default will not be available in fightin. Therefore, we need to install this morning for number to work. We will continue by declaring underscore vortices As a member of the graphs class, we will use self dot underscore what this is equal toe vortices. We will define a matter in certain edge which takes in £3 meters. You ve which are notes and the third perimeter w which be assigned a different value as one . The perimeter W is used for assigning the weights to the just. The next statement would be settled Dark underscored et Matt off you the equal toe w. Then we will define a mature delete edge. This deleted Mathur takes in two para meters you envy as witnesses. Next statement would be self dark under school here, Digimarc off you the equal to zero. Then we will define a meth hurt. Get edge. This method also will take to perimeters you envy as worthless is we even have a statement or done self dark underscored a deejay mark off you. Me? We will now define a matter work. This is on the score. Count which returns. The number of workers is in the graph. This will not take any perimeter. We will have a statement or done self dark. Underscore. What is this? Then we will have, um 1/3. It just underscore. Come this May 3rd returns number off edges in. The graph on this also will not taken any Artemida. We will define a variable count on initial is 20 We will have a for loop for I in range off self dark, under school work, this is And then we will have an inner for loop to travel the columns of the matter it for Jay and range off self dark. Underscore what this is Then we will have an if condition. If not sell Dart a. T. J Maxx off I day equals equals zero. Then we will inclement count their discount equal to compress one and finally even their done. They've been loudly glad I'm a 30 in degree which takes in a perimeter. As the work takes you, we will declare a variable count on initialize 20 We will then use a far look for I and range off self doubt Underscore witnesses. Then we will check if not off Cell dart underscore 80 Jimmer off I you equals equals zero. Then we will income and count. And finally, to turn the value of count, we will define our degree matter which also takes in one perimeter that does the work takes . We will again declare account variable and initially to zero. And you, Zafar statement for I and range off cell Dark under school where this is and we will check if not off. Sell Dart underscored a d J Mac a few I equal to equal to zero. Then we will inclement come and finally down the value of come the last method we will define as their display which doesn't take any para meters. Here we will display the decency Matics using print function Sprint off cell dot underscore unity My once we have defined all the methods of the class graph, we will create an object G off type graph and posit er humor at seven. That means we are creating a graph off seven. What is this? We will use a print function. We will print graphic Justin see my tricks and then we believes Igor display for display the graphic design schematics. Now we will get adjusting. The graph even use g dark insert underscored edge That doesn t matter. We will pass the endpoint work This is let us zero comma one. Then we will have zero comma five followed by zero comma six Then we will have one comma zero one cover to one comma five, one comma six so and so forth We will insert all the edges in the graph. We will again have often function print adjacency, matrix. And then we will have D dark display for display the graph of decency murders. Let us run this program and take the output. You can find that initially, all the values of the A distance Emaar tricks are zeros. And then, after inserting the agents were having once, which represents T. It isn't the graph corresponding to respective, where this is leaving Lampre in the number of Fortis's using D Dark. What is coming on. We will also print number off. It isn't a graph using t dot it's come. You'll execute this program. The number of pages are not printer, so let's figure out what's the problem? There is a problem. It's not a legion. Margaret's underscore a Dejima. So let's execute once more. No, we have the number of where this is displayed, as well as number off it just displayed. We will not find the or degree of a Vertex, for example, who were takes, too. Using the matter did our our degree off to let's execute this program on again. We have an era in the order game. Enter it should be what this is. We will executive once more and now we have the out bigger workers to history. This is how good absurdities implemented in fighting. 47. Graph Traversal Algorithms: in this section, we will cover the graphs. Traverso algorithms are Travers or techniques. We have already seen the implementation off graphs and heighten the graph traverse Eliza technique out of 1/3 of starting from over ticks on visiting all the vortices that can be reached from the start work. It's there are two efficient graph traversing algorithms. Breadth First search, which is also known as BFS and depth First Search, which is also known as the FS. These two are the efficient and very important draft reversal algorithms and data structures. At first we will see how bread for search algorithm works. Breadth first search are BFS algorithm starts from a vortex and identify all the workers is that are reachable from it that is travels through alerts, edges and then start from the first reachable vortex. Identifying all the reachable vortices if the work takes is not yet visitor. And this process of breakfast search continues until all the world This is our visitor. We will take an example Onda, look at a step by step procedure off how breadth first search works. Let us take start work, Xs zero We will define a cue to store the workers is that have been visited And we will also have an r e r A list off number of Fortis is known as visited. This list is used to keep track off the workers which have bean visited. Now they will start from work eg zero And this work this is visited reveal Marc Worth zero and visitor list as visitor We will And you were to zero on a play d to Operation Dick. You'd element is worth zero. We will find all the vertex is that can be reached from Vortex Zero. These are the three edges through which we can visit three different workplaces. The first word takes visited is vortex one. This work takes his monk does visited and then in Cuba the next word X is worth X five, which is not yet visitor. So we visit for 65 and market has visited. And then in Cuba Dicks fight and then we're take six can also be visited from work eg zero on. We're take six is not your visitor. So we visit were take six on Dmarc were take six as visitor and thank you. This word x six. Now we will dig you another element under dick You'd element is vortex one. We will now travels through all the edges off for Tex One through the first edge we can visit Vortex to Vortex two is not yet visited. So we visit where takes two on market has visited and then in queue where takes too through the next edge off vortex One We can visit or takes five. But what? X five is already visitor? So we move for the we can visit were take six. This were take six is already visitor. And now the next word Eggs that can be visitor is worth eg zero which is also already visitor. Now again we apply RDQ operation which will take you were text five and through this for text fight we can visit were takes two which is already visited. We can visit work x three where Text Reznor Tiered visitor So we visit were text three and mark this word x tree as visitor on en que were text three. Then we again apply Dickie operation Since there are still elements in the queue the dick you'd work takes is were take six from Vortec six weekend visit. We're next three but it is already visitor on their no other edges. So therefore Vedic, you nor too from north to we can visit north six which is already visited. We can visit were text three, which is also visitor. We can visit where takes four Where takes for is not here visitor. So we visit were takes for as for less mark or takes for us visited and thank you were takes for there are no other edges So via play dick you operation again on what? X three is dick you through What extreme we can visit were thanks for But what x four is already visited on their no other edges from word X tree So therefore we again a player Dickie operation where takes four is the cute Through what? X four we can visit where takes too What takes two is already visited as well as we can visit Vortex fight What? X five is already visitor and there are no other edges forward. Thanks for once the cure is empty. Then the breadth first search algorithm terminates So this is how great for search algorithm works. We will now look at how depth First search algorithm works depth First search algorithm starts from overtakes and seller The adjacent work This is from start Nordics Visit the a distant word X and then repeat the above step again until they are no interest in tortoises And then the search terminates. We will look at the working off the depth first search algorithm by taking an example of the same graph. You're also the start. Overtakes will be worth zero and we will have a list Ordinary known as visitor with all the workers is we will start the depth first search from war Tuxedo were tuxedo is visitor on dMarc Does visitor in the list from work eg zero There is an edge toward takes one So the visit or takes one and market as visited then from vortex one we can visit were takes zero which is already visitor We will visit were takes to an market as a visitor Then from the Vortex two we can visit what x three where text today is not your visitor So we visit were dexterity and market as visited then from what X tree removal on the work takes four were takes four is not geared visitor. So we visit were takes for as villas market as visited Then from where takes four we can visit were takes two but were takes two is already visitor So through the next stage we can visit overtakes fight Vortex five is not geared visited So we visit We're next five and then market us visited from where takes fight We can visit where takes too. But this vortex is already visited as well as we can visit were text three on this work Takes is also already visitor There are no other edges through which we can visit from vortex fight So we moved back to work next four from Vortex four Also they are no outgoing edges So we moved back toward extreme or text three Also there no outgoing edges. So we moved back to work takes to where takes two has an hour going It's toward takes six on where Take six has not yet been visited. So we visit were take six and market has visited were take six has an hour going edge toward extreme But what x three is already visited So we moved back toward x two and from where takes two. There are no other edges to visit So we moved back toward X one from where takes one we can reach were takes fight. But what x five is already Visitor, We can also reach or take six where take six is also visited So we moved back toward X zero from working zero we can visit overtakes fight But what takes five is already visitor and then we can also visit were take six which is also visitor Once all the word is this out A visitor on there is no more part to any other non visitor edge or non visited were takes Then the depth first search algorithm terminates This is how depth first search algorithm books 48. Implementing Breadth-First Search Algorithm in Python: in this section we will see the implementation off breadth First search algorithm in Beytin We will create a bite and file on give the name as the BFS The apology Creator, the entire 80 d photographs. Let us copy the entire court on Baste it in the office Now Inside the graph class, we will define ometer BFS for Brett for search algorithm This be affects my third really day one para meter That is the source sources We were takes from where we started regret for such We will define available I and assigned the value of source We will cleared another object you for using the link you link you We have already implementer so that is just important link you plus from killing the file import Linda Q Class. We will continue with the implementation off BFS Alberto leaving clear the list with the name visitor and assign all the values as zero using zero multiplied by cell dot Underscore workers is that is all the seven workers is assigned zero. Then we will use a print function to print I which is the word it's we have a visitor. Then we will make the element of the visitor list as one and thank you The vortex I We will use a via loop and check if the Q is empty using vital narc que dot is empty. Then we will have a statement. I equal toe shoot. Or did you? That is we're decaying. The element are the Vertex Inside the Q we will use a for loop for J and range off self doubt. Underscore witnesses Onda We will use an F condition if self dot underscore existent Matic that is a deejay marked off by day is equal to equal one. That means there is a hedge between i n g on visitor of day, equal to equal to zero. That means the Vertex has not here to be visited inside the if condition we will use print J and next statement We will use Visit J equal to one And then we will in Cuba overtake Z. That is cute are thank you Off Jay. We will remove the statements. Did our display that is displaying the adjacency? My face? No. We will call the breadth first search Alberto using D dart BFS and provide a zero, which is the source vortex are these starting work? Expert breadth. First search algorithm. We will execute this program and there is another letters. Rectify this here the class member where this is the spirit incorrectly. So we'll rectify this. Let's execute this once more. We have the output of breadth. First search Albert. So this is how breadth first search algorithm is implemented in fighting. 49. Implementing Depth-First Search Algorithm in Python: in this section we will see the implementation off depth first search algorithm in fightin . Let us clear the bite and fight and give the name us DFS We have already implemented the graph sanity. We will use the same implementation of graphs 80 plus We will copy the scored in our DFS file And then we will create a mature to implement depth first search algorithm. We will give it the Neiman's DFS. This method also takes in source as the para meter sources they were takes from it DFS algorithm will start The next statement would be to check if the word Texas visitor So we will have if self dark visited off source equal to equal toe zero no underscore visitor has not been defined as a member of the class, so we will define it in the end it matter that this self dot underscore visitor and then assign all the elements of the list as zero using zero multiplied by vortices We will continue with the DFS algorithm. We will use a print function to imply that we have visited the source node Next statement would be self dart underscored a visitor off source equal do one. That means once we have visited the source, we will assign value one indeed. Underscore visitor list. We will use a far statement for J in veins off cell dot Underscore witnesses. Then we will check the condition if self dark under school it Justin Mark Rix off source. Kamajii equal to equaled one. That means if there it is that can be used to visit the norms on self dark underscore visited equal to equal zero. That means the Jato vortex is not here visited. And then we will recursive Lee call the DFS matter using seven Dar DFS of G we will use the same graph with seven workers is on same sort off it is. We will call the DFS algorithm using D dark BFS and pass zero lt source or takes our start work takes letters Executive this program on. We do not have any others, but we're not getting the are letters Rectify this problem And the DFS met her in the if condition inside the for loop. We have used self doubt. Underscore Visitor, We are actually accessing the elements of the visitor list So we will use sell dark underscore Visitor off day and take whether it is equal to equal to zero. There doesn't execute this program. I know we have the predict visit. This is how the depth first search algorithm is implemented in fighting. 50. Selection Sort Algorithm & Its Implementation in Python: in this section. We even see how selection sort algorithm books as well as its implementation and fightin. Let us consider the list. Very. We have five elements on these elements. Has to be sorted using selection sort algorithm. This algorithm works by selecting either the minimum element from the list are the maximum element from the list on placing it in the appropriate position. Hence the term selection sort. In this case, we will select the largest A limit on the maximum a limit, and then place it in the light most index. So in the first iteration, we will select the position that is the end of the list on. We will get it through the entire list to select the maximum or the largest element. We will start from the 1st 2 next. Then take the second next, the 3rd 1 So on the fort as villus the last index Now here we found the largest 11 Toby 96 . This largest element is replaced with the position that is the last element in the list. So we swept the last element with the largest element reform. So here we have selected the largest Elmer and then placed her in its appropriate position . The algorithm continues with the second iteration. We have farmed the largest Elmer and placed it in its position. That is the last 10 days. Now the position is and minus one. That is, the position is index, for we will now select the largest element among the left out elements and place it in exposition. That is the fourth index. We will again start from the beginning of the list compared each element and finally largest. Tell him now, in this case, the largest element is 84 this 84 a swap with element 15. In the next generation, the position will be positioned minus one. So now the position is indexed re. We will find the largest delivered from the beginning of the list searching each index. And now we found the largest a limitless 47. The 11th in the index three is the largest on position also isn't extreme. So this is not starved because it's the largest element among the remaining elements. In the subsequent iteration, we will move the position on again. We will try to find the largest among the left out elements. We found 21 as the largest on it is in its place. So we will not swiper Now, Finally, the position is the first index on for the first index. We only have one element, so we do not. So Appert The first delivery is in its place. The selection sort algorithm completes when the position reaches the index zero and the list isn't sorted Order. We've now seen implementation of selection sort algorithm and fighting. Let us create a bite in fine and name it as selection sort. We will define a function selection sort and then posit e arguments as the list. The values are far loop for I in range length of the list minus one commas Ito comma minus one. That is we're taking the length of the list on Deke, limiting it by minus one. We will define a variable max position on assigned the value US zero. We will use another far loop for J in range one comma I plus one inside authority loop even tick. If a of J is greater than a off max position, if it is true, then we even replace the max position liturgy. So once the far J. Luke completes its alterations, we will be having the position of the largest 11 Toby tribe. Then outside the Forge a loop, we will use the temp variable and assigned the value of a off I. And then we will assign a off I equal to a off my exposition. And the last statement would be a off max position equal. Tow them, that is. We're scrapping the elements in a fight with a off my exposition. This completes the selections are Alberta. Let us create a list a on have five elements. We will call selection sort on past the list. A. We will use operate function to print the sorted list before calling selections are. We will have another statement, but it original Ari our original list that is List A and then we'll perform Selection Start and finally printed Saturday there has executed this program. You can find that original Ari or listers unsorted order. And once we called selection start, the list isn't sorted. Order 51. Insertion Sort Algorithm & Its Implementation in Python: in this section, we will learn about insertion sort algorithm on exempt limitation invited. Let us consider the same list what we have used in selection sort algorithm in the earlier section. This list also has five limits, which is in unsorted order. The Insurgents art algorithm works by selecting one element after time on inserting it in its proper position. Hence the dome insertion talk in the first iteration. First, a limited selector on this element is assumed to be an exposition in the second inauguration. The second element is taken as the input and compared with its previous element, it is not in its position. That is, it's pretty us celebrate is greater than the import element on this element 21 it's placed in its position. So therefore, in the second iteration, the second deliberately selected on inserted in its position. Now in the third iteration, the third element from the list of selector on inserted an exposition by shifting the elements. So in the third integration, the third eliminate is selected as an important member compared with other elements, efforts get up. Then those elements are shifted to the right till the position who entered the input element is found on the input element is inserted at that position. So again, if you observe in the third iteration, the three Elevens are in a sorted order. Now, in the next iteration, that is fourth operation Fourth Element from the list of selector that is, in this case 96 then it is compared with the rest of the elements. Now, if you observe are the fourth generation all four elements in the list ardent sorted order , then the final alteration are the fifth generation. We will select the fifth element from the list and find its position by comparing the other elements with the import element on if the other element is greater than the important memory. Those elements are shifted towards the right until the in court element finds its position . Once the positions found, the import element is inserted. So after the final innovation, the complete list is in a sorted order. This is how insertion sort algorithm works. We will now see the implementation off insertion sort Alberta infighting. Let us clear the pipe and file and give the name as insertion sort. We will define a function insertion sort, which takes in list as the perimeter. We will have far Luke for I in range. One comma, one comma lent of the list. Alien off a inside the for loop. We will have a variable value equal to a or fight. We will declare another variable position on a signer as I we will have a value. While position greater than zero earned a off position minus one is greater than the value . Then the statement and the violet will be a off position equal to a off position, minus one. And the next statement will decontaminate the value of position, their disposition equal to position minus one. This why look is used to shift the elements in the position of the input element is found. And then we will have a off position equal Do the value that is. We found the position and inserting the import element in that position. We will clear the list A on assigned some elements. These elements are in unsorted order. We will use upturn function print original Ari, Our list comma He Then we will call insertion sort Alberto passing the list A and finally we will have a statement using the parent function. Prince ordered a comma. The list A. We will execute this program. You will find out the original list of sprinter, which is unsorted order. And then after guarding insurgents sort algorithm, we are printing disordered list. This is how insertion start algorithm is implemented in Brighton. 52. Bubble Sort Algorithm & Its Implementation in Python: in this section we will learn about bubble sort algorithm on its implementation. Invited the bubble sort algorithm it irritates through the list comparing adjacent elements on slapping them If they are not in order, these steps are repeated again, which we call it US Pass that is passing the list is repeated again and again until the entire list isn't sorted. Order. Let us consider the set off elements. That is the list. In the first pass, we will start from the zero there next and compare the glimmer with the next index. So Element 84 21 is compared. They are not in sorted order, so they are swap with each other now The next two elements are compared. That is 84 47. These two are Norton Order. So these two are swept. We're still in first class. We will compare the next two elements in the list. They are in sorted order so they are not stopped. Then we will compare the next two elements. They're not in order, so these two elements are swept. So now the first pass is completed. We will start with second pass because the list is still Norden sorted order again. 1st 2 elements are compared. They are in order. They're not slapped. The next two elements are compared. They are in order. They're not so apt. Next two elements are compared there, Not in order. So these 2 11 side swept. Then again, we will move on with the third pass in the third pass. Again, we start from the beginning of the list. The 1st 2 elements are compared there in order. So they're not swap. The 2nd 2 elements are compared. These two elements are swabbed and in the fourth pass again we start from the beginning of the list. The 1st 2 elements are compared there, not in order. These two elements are so and now after the foot pass, the entire list is in sorted order. We need to perform and minus one passes for a list with contains and elements. So in this case, the list contains five elements. Therefore, we need to have four passes to have the entire list in sorter order. We will now see the implementation of bubble sort algorithm and fighting. Let us clear the bite and fight and give the name as bubble sort we will define a function . Bubbles are which takes in list as the argument. We will have a for loop for pass in veins, length of the area that is alien off a minus one coma. Zito, comma minus went. Never seen the name pass as I because passes a keyword and fightin so the I N for Luke will be D cream entered by one each time the far Lupus executed. We will have another for loop for J in range off I. We will then compare the two adjustment elements. That is, if a of G is greater than a year of J plus one. Then we will show up a off day with a of J plus one that is a off J comma A of J Plus one equal to a of J plus one comma A of J. This is the simplest statement in fightin to swap two elements. We will now clear the list A with some elements and then have a print function to print the original list on call bubble sort algorithm, passing the list A and finally print the sorted list. Using the print function. We will execute this program and in the output. We have unsorted array, our list. And then after calling the bubble sort algorithm, we have the sorted Harry, This is how bubbles heart is implemented invited. 53. Merge Sort Algorithm & Its Implementation in Python: In this section, we will learn about Mozart, Alberta, on its implementation and beytin the mod sort algorithm uses are divide and conquer approach, where the list is divided in two halfs until the list has only one element. That a limit is considered to be in sorted order and then to individual sorted list are months to get a sort of list. We will take an example and then see the demonstration of how what sort algorithm works. We will take a list with some elements. In this case, we have a list with five elements. No mirth start divides this list that is five divided by two and division is a teacher, so we get the result as too. So we divide this list into two and three elements. The list with two elements again divided. So now we have a list with only one element, and this list is sorted. Since it has only one element. The other list also has only one element on. This is also considered as sorted. Now these two sorted lists that is list with 84 on list with 21 are merged together to form a sorted list. Then the other half is still remaining, so this list is again divider in tow to list one with the 11 96. This is considered to be a sorted list. Then again, we have a list containing two eliminated artist 15 on 47. This list is again divided, and now we have list with Element 15 which is considered to be shorter as well as list with Element 47. This is also a sergeant. Now we months these two list with Element 15 on Element 47 bigot, assorted list. We move a step backwards, and now we have list with the Element 96 which is a sort it list as well as we have a list with the Element 15 and 47 which is also a sorted list, we will merge these two lists together. Now we have a sort of list with three elements. These two lists again much to get the complete sorted list. So this is how much start algorithm uses are divide and conquer technique. This are delist. We will now right a heightened program to implement mud start. Let us create a pipe and file on give the name as much sort. We will define a function, Moz Art, which takes in list as the perimeter. We will have an if statement. If length of the list is greater than one, we will calculate the murder value that is made equal. Do Lent of the list divided by two. Here. The division is on in teacher division. Then we will use left equal dough eight off Golan meant and right equal to a off mid cooler . That is we have now divided the list into left and right. Using the major value, we will recursive Lee call what sort for left and murdered start for right list. We will define very well I, which is equal to Zito on variable G, which is also assigned to zero on Variable K, which is also assigned to zero v values of I. Lou, why? I less than lent off left on J less than Lent off right in this by Luke. We will have a condition if lift off I is less than right off I Then we will have a off k equals toe left off. I on incriminating value off I that is I equal to I plus one else we will have a off day assign toe right off Jay. And then in commit the value of J started Z equals J plus what, And outside the NFL's lock, we will income in the value off K. That s K equal to K plus one. This why Loop is used to march the two sorted list into one single sorted list. We will now have another by look, while I'm less than lent off left. And this by Luke will have statement a off k equals left off. I I equal toe I plus one and then K equals Okay. Plus what the same way we will have another biloute while j less than lent off right on decor two j plus one on K equals O K plus one. And this completes the implementation of mirth start function. We will clear the list A with some elements and then called much sort algorithm passing me list as a We will have a print statement to print the original list as villas. After calling mode Stark, we will have another print statement to print the sorted list. We will execute this program. We have another. Let's rectify the center. I have defined three variables on the same line will change it to its declaration, Our honor differently. Let us run this program once more. Navigate the desert. We have no errors, but the residents are The output is not unsorted. Order. Let us go back to the mud. Start function the length of the area sect than in divide loop. There is a mistake in the condition the condition say's left off. I is less than right off. I It should have been right off, Jay. Nowhere does then the program once more. Now we have the connect our port. That is after calling the Mozart algorithm. The list isn't sorted. Order. This is how much sort algorithm is implemented and fight it. 54. Quick Sort Algorithm & Its Implementation in Python: in this section, we will learn quick sort algorithm on its implementation. In fightin, the quick start algorithm uses divide and conquer approach. The quick sort algorithm will first divide a larger list in tow to smaller lists Quick Sark and then recursive Lee sort the smaller list quick sort uses and eliminate called as paper . And then partitioning is perform. Sir Stark. The elements to the left of the pervert are all smaller than the paper, and the elements to the right of the P word are all greater than the paper. After this partitioning is perform, the 11 in the pervert will be our tricks. Final position. Then the quick sort algorithm can recursive lee Sarti elements to the left of the paper as well as the limits to the light of the paper until all the elements are sorted. Let us take an example of a list with five elements. The quick sort algorithm takes list as the perimeter with the starting index of the list and end minus one. As the third party media, let us now see how partitioning is performed. A very below is taken, which is a sign zero and variable highest taken which is assigned and minus one. Let us consider another very well, I with a narrow green and gave it Red Arrow. We will have favored as an audience arrow. When partitioning is performed, the IATA will be pointing towards minus one, though minus one is not an index for the other, but it is initialized as minus one. Then we have a paper which we initially assigned to the last element of the list on J Ville point words Starting index off the list. Now the J Index will move from low to high. That is, from starting index of the list to the ending index of the list. Now the pivot element is compared with the element in the debt index if the 11 in jade index is greater than the paperwork, the inclement detour index. But if the element in the DJATE index is less than the paperwork, then the ICT indexes in Commander all right, the element in ICT index on the element in the date and exa swept date indexes incriminated again and this values again compared with the paper, if the JIT index value is greater than the paper Djate and next one being perimeter. Now, Jade Index is less than the paper. So I ate their nexus and carpenter and these two elements are swept. In this case it is 84 15. And now if the Djate indexes implementer it released the preferred value. Therefore the only inclement right there next and then. So I have the element from the ICT value with the river element. Now the element 47 which was the paper element, is no place that it's partition position. So if you observe the 40 cent a limit is the partitioning a limit? The elements to the left of the partition eliminate is all smaller than the Kardashian eliminate on the elements to the right of the partition Eliminate are all greater than the partition A limits. Now the quick start, Alberto can be the coercively called again with the para meters. As the list on lower index on high index as partition minus one as well as quick start I get can very coercively called with the perimeters as the list and low as partition plus one as well as high as the perimeter. So quick sort will again use a pervert element on partition. The smaller list as well as the larger list. So this way quick sort Alberta is recursive Lee guard until all the elements in the list are sorted. This is how a quick sort Allerton works. This is the most efficient sorting algorithm compared toa any of the other algorithms which we have seen earlier. We will now see the implementation of quick sort algorithm and fighting letters. Open a pint and fine and give the name as quick Sark. We will define the function quick start but stakes in he has the list. Second argument will be low and the third argument will be high. We will check the condition If law is less than high then we will use a variable p equal to partition A comma low comma high partition is a function which we will define later. We've been recursive Lee call Quick Sark passing the parameters as a comma low comma B minus one that this partition index minus one Then we will again record civilly call the quick start function passing the parameters as a comma three plus one that this partition in next plus one comma high They will now define the partition function partition function well taken. Three para meters. That is a that is the list comma, low, comma high. We will define a variable I equal to low minus one on we will define a variable favor. We were people assigned to a off high leaving Then you, Zafar Lou for Jane Ranger Lo, comma high and then take the condition. If it off J is less than equal to Privert then in criminal I that is I equal toe I plus one on a off I comma a off G equal to a off J comma. Hey, off I that is we are swiping the elements present in the next. If I and off Jay once the far new completes its execution, we will swap. They worked with the I plus one element that is a off I placement comma here high equal to air fight, comma payoff I plus one. Then finally return the paperwork value that is high plus one. We will clear a list that some elements and then call the quick start function Passing the list A comma zero, that is D zero. Next comma lent off. List a minus one. We will use a print statement rending the original list that is a And again, after the quick start, we are printing the sorted list letters executive This program you can find dark, the original list a sprinter, which is unsorted order. And then, after calling the quick sort, the sorted list is printed. This is how quick sort algorithm is implemented in pointing. 55. Heap Sort Algorithm & Its Implementation in Python: in this section, we will learn about heap sort on except limitation. In Brighton, we have already implemented heaps and demonstrated the working off insertion as well as delicious. We will use the same program to implement the heap sort. We will cleared a bite and file and give the name as keep sort. We will use the same program off implementing heaps already and copy it in heaps sort file on this class are a heat which we have already implemented contains insert as well as delete methods. But here we have implemented a heat plus to create max heap. In general, sorting is done in ascending order. Therefore, we will change the insert mint hurt to create a min here so that subsequent calls of deletion will delete the minimum element from the heap. We will make some changes in the methods that is insert earned village in the insert methodically will change the condition that is, while I not equaled one on e greater than self underscore data off I divided by two here instead off greater than we will change less than self under school data. We will change the name as delete mint on in the condition. If Self dart underscored data off CIA is less than we will change it to greater than as well as in the condition. If by greater than equal do sell dart underscore data, we will make it us if my less than equal and now they will clear a heap using the same statements. There is no change in the call to the insert matters. We will, right a far Lou for I in range off. It's dark under school getting sakes now. Current size is the size of the heat. We will call leaving card. Elite meant matter. We will also make one change in the elite men matter that is, the X is the root which were the leading. So the last statement we will say Return X and then here we will. But in the deleted element we will use and as the keeper to separate the elements we will execute this program and you can find our We have inserted 25 14 to 2010 and 12 and here you can find the sorted elements using heaps are generated by subsequent call study Delete mint method. This is how heaps art is implemented. Invited 56. Python's Built-in Sorting Functions: in this section, we will look at the Buyten's building starting functions. Let us consider a list with five elements. This is the same list we have been using in the previous sections bite and has a building starting function known as START. The start function belongs to the collection types, so we can use it as a dot sort. Well, sort of the elements in the list. A biting also has sorted function. This function takes in the argument as the collection interface that is the list so we can use sorted Off a on Dead Returns assorted list, which can be stored in another object. This art function by default starts the list according Toa ascending order, but we can use reverse keyword on past livers equal to True as a perimeter to the sort function. It will start the list in descending order. Sort can also use a keyword key on. We can provide a function that is supposed if you use sort and passed the argument as key equals trillion, that is, alien is the Lent function, which is already defined. Then the starting is performed according to the length of the elements, nor devalue. We've allowed by the fighting program to demonstrate how build and starting functions off fightin works. Let us create a bite and file and give the name as biting building sort. And here we will find a list. But some elements on we will use a print function toe print the originalist. Then we will apply a dark sort function and we will use a print function to print the sorted list. There does execute this program and you will find there the original list is now in disordered order. No letters, the monster it sorted function, that is, we will take the same list A and then we will print the we will use Be equal dude sorted and pas de list A. We will again print the original list a and then print the sorted list B Let us execute this program and now you will find are the original list is intact on the started function has returned the sorted deliverance as a list. We've allowed them on ST how to use the reverse keyword Leven posit er giver reverse assigned the value through Let it execute this program. Now you confined art. You have the original list and then we have the sorted list in reverse order that is in descending order. Instead of using numbers, we will get a list off strings. Let us take an example of colors. Let us see it, then green, blue, black on. Let's say why and we will start this list. Let us run the program and you can see that the original list is displayed as well as we're displaying the sorted list. Now here, if you observe the sorting is done according to the dictionary order, we can use reverse equals true and then let the CD desert. You can find that it has sorter the elements according to the reverse dictionary order. I suppose if we use key as the key were on past the function land and then bring the sorted list, there does exist you with this program, we can find that it is not starting. According to the dictionary, order what it is sorting according to the length of the elevators, that is, the size off element rate is three sighs off 11 blue is for followed by size off Taliban green, black and white. If you observe, we have black as well as way and green off. Same lit. Now let us try to swept black with white and execute the program. If you observe, it is starting only according to the length. It's not considering the dictionary order. So if the elements have same land, then it will appear as in the sequence it has appeared in the original list. Therefore, you can find that in the earlier example, we had used black and white, so black waas displayed before. Right now we have used white and black, so it has displayed as it is white and like in the same sequence. So this is how the building starting functions off, fightin works. 57. Asymptotic Notations Big-Oh, Omega & Theta: in this section, we will cover the A sympathetic and analysis that is the big O notation Omega and 3 10 rotations. The meaning of the term a symptomatic is approaching a value with some limits. Now let us take an example of a function f off in on the end. Value can be any positive Indigent in algorithms were not bothered about the small values off in. We are bothered about the large values off. And so if you consider an import and ah five r n off 10 then it doesn't make sense to compute the running time of an algorithm. But if you have a larger values off in, for example, 1,010,000 1,000,000 then obviously the running time off algorithms will matter a great deal . Let us take this function FN, which is n squared plus six in. If the value of N is large, there just let's take 1000 than in squared would be a 1,000,000 on six N or to be 6000. If you compare 6000 with a 1,000,000 it is negligible. Therefore, six n is insignificant. So what we say here is we say f often is set to be a symptomatically equal. Do and square Angleton's are analysed, using mathematical notations for functions with disregards constant factors. For example, in the previous case, we heard a mathematical function FN on really president or Dark as and squared plus six in so algorithms are analysed using FN art mathematical functions. The running time off algorithms are characterized by using functions that is same f off in these functions are marked with the size of the import end. So here we are bothered about and approaching a large value are in improving infinity. The running time off algorithm grows proportionally to, and that is the input sites. We have already seen functions taking constant time lager at some time that is log in. We have also seen linear, which is represented by en garde genetic. There does end square. For example, if you have a function which contains two nested for loops, then it can be presented as a mathematical function and square. Then we have cubic where we have three nested loops and there is something known as and log in as well as exponential that is to power. And now we have already talked about these complexities. If you remember, Constant takes less time than log in. Logan takes less time than end, and it takes less time than in Logan, and Logan takes less time than and square as well as in square. Takes less time that in Cuba on thank you take less time than to pull it. And that is exponential. Always remember that when we're talking about end, we're talking about large values off to represent the time complexity. We haven't a symptomatic notation known as big o Biggles define us FF in less than equal toe. C G. Often year F, F N and G often are two functions, and C is a constant and in his later than and of zero. We also have omega notation that is F often is greater than C of g fn, and here also if offend and Giovanna through different functions. See me the constant. Then we have a Teton rotation, which is there to constant C dash and see double ash and C dash of the offense is less than half. Offense on FN is less than equal to see double action GFF nine year. Also, if offend and reoffend are two different functions, the bigger notation works on the concept off less than equal. We'll make a notation works on the concept of greater than equal. So therefore, Big Oh rotation defines the upper barn off the function Omega defines. The lower born of the function on teeter defines the tight born off a function. Therefore, if in Alberta has n Square as its complexity, then we say that it's complex. City is big go off and square because we are always bothered about the upper bombs. That is the larger values. The omega and heat are also used, but most of the Alberta stocks about the big O notation that is the complex city is defined using big O notation. So therefore, we have seen the complex. It is earlier we have defined functions on. We have praised the functions also in the earlier sections, and now we have defined these three a center Digna additions that is big Oh, Omega Teeter