Algorithms and Data Structures in Javascript (2020) | Lukas Vyhnalek | Skillshare

Algorithms and Data Structures in Javascript (2020)

Lukas Vyhnalek, Microsoft Employee, Programming Teacher

Play Speed
  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x
40 Lessons (5h 9m)
    • 1. Introduction

      1:31
    • 2. How to install Visual Studio?

      2:12
    • 3. What sorting means?

      1:13
    • 4. Bubble Sort

      5:58
    • 5. Bubble Sort Implementation

      8:44
    • 6. BubbleSort2Challenge

      2:16
    • 7. BubbleSort3Solution

      5:08
    • 8. Selection Sort

      7:04
    • 9. Selection Sort Implementation

      13:31
    • 10. What is recursion?

      1:29
    • 11. Recursion

      10:51
    • 12. Recursion Debugging

      6:32
    • 13. Quick Sort

      5:26
    • 14. QuickSort Implementation

      10:31
    • 15. QuickSortChallenge

      3:27
    • 16. QuickSort Median

      13:30
    • 17. Merge Sort

      3:55
    • 18. MergeSort Implementation

      15:46
    • 19. Time Complexity

      4:48
    • 20. Big O notation

      6:46
    • 21. Comparing CODE

      13:28
    • 22. Data structure

      0:46
    • 23. Binary Search Tree

      7:32
    • 24. BSTInsertSearch

      15:48
    • 25. BSTDelete

      23:03
    • 26. BST Fix

      4:26
    • 27. Avl Tree

      5:40
    • 28. AvlDeletion

      1:59
    • 29. AvlInsertion

      2:34
    • 30. AVLtree1 Node

      9:54
    • 31. AVLtree2Insert

      9:03
    • 32. AVLtree 3 Delete

      12:29
    • 33. AVL Tree 4 Rotations

      15:35
    • 34. AVL Tree Fix The Bug

      2:51
    • 35. Tries

      10:39
    • 36. Tries Implementation

      15:44
    • 37. Linked list

      3:36
    • 38. LinkedList Implementation

      9:45
    • 39. Hash Table

      3:22
    • 40. HashTable Implementation

      9:44
13 students are watching this class

About This Class

This course is designed to help you understand sorting algorithms and data structures. In my experience most people focus on the programming language, but people often forget about algorithms.

Algorithms are definitely more important than a programming language, you can learn a programming language in about week, but the problem-solving ability is much harder to learn. But the benefits are worth it.

When you get to interview mostly they care about your problem-solving abilities, algorithms and data structures.

To get your dream job, you need to know how to solve whatever problem they have. In this course, you will learn how to do that.

Also, I believe that nobody has time for long and boring lectures, so in this class, I try to explain the important things in a fast and engaging way, so I won't bore you to death.

We start off with Sorting algorithms:

- Selection Sort

- Bubble Sort

First there is the explenation lecture where you learn the idea behind an algorithm, then there is the implementation lecture, where we implement the algorithm in Javascript.

Then I show you how Recursion works, once again I try to explain what recursion means, then we implement some recursion algorithms and we use debugger to see how computer evaluates recursive functions.

Then we move on to recursive Sorting Algorithms

- Merge sort

- Quick sort

These algorithms are most commonly used. With each algorithm I explain the idea, then we implement the algorithm.

Once you learn sorting algorithms, we move on to Time Complexity:

- What is time Complexity

- Big O notation

I explain what is time complexity and why we need it, also, I will show you how to compare sorting algorithms, so that we can see which one is the "best".

In this section you also find an article with a lot of problems, where you can train your problem solving skills.

After that we take a look at Data Structures, I choose In my opinion the best dat structures for you to learn the important concepts.

We start of with Tree Data Structures:

- Binary Search Tree

- AVL tree

You learn how these works and also how to implement them.

Then we take a look at Linked List, Stack, Tries and Hash Tables. Once again we implement all of these in Javascript.

I believe that learning and understanding these concepts will help you solve problems more efficiently. 

Transcripts

1. Introduction: Hello. My name is you can I will be your instructor for outer scores. I have been programming for over five years. I worked in companies like ASAP and I decided to share my knowledge. In this course you will learn how sorting algorithms work. I explained the idea behind every algorithm and then we implemented in Javascript. We start with selection and bottle sword. Then I explain our courage and works on dead. We will take a look at quick sword and merch store wants you implement all of these algorithms way we'll take a look and down complexity and big old notation. We'll compare all of the starting algorithms and we will find out which one is the best. Then way. Take a look at data structures. First explain how vital research tree and 80 of tree works. Then take a look at lists and D to probably most used data structures, tries and hash tables. Ones get when implement already. JavaScript. Another thing I want to mention is that my Jack does not end by making these video lectures . If you have any questions, you can always reach out to me. Mostly I respond with a day and that is pretty much it. Thanks for your time. And I'll see you in the course 2. How to install Visual Studio?: Hello, guys. Send welcome to this lecture and this lecture. We will install the visual studio code. So this will be an I. D. Where we will coat our project. You can use whatever i d you want, but the I like D visual studio code. So averages use visual studio code, and in this video, I will show you how you can install it. So let's get started. Simply go to go, Dad visual studio dot com. And in here you can see download for Windows, and it should. It should automatically figure out your operating system if for some reason, it doesn't work. If you click on this can arrow. In here you can see Mecca, Wes and Lennox, so feel free to install whatever package you want. I will simply click on this damn world for Windows. It will take me to this page, and it will all the medical started downloading for me. So the downloading should take just few seconds because it's just it's really small file and visual studio code as a great i d. It's 100% free, so that is great. And that's unusual for Windows Bar Area when it downloads simply click on that and open it up. It should open up this dialogue in here. Click next. Once again, you have the license agreement. I will accept it because I already read this thing yesterday. And in here you can select the the folder pretty much same like every other installation. Just next. OK, on and in here you can create a disc, the back, and I definitely want to do that. You can also at this to, like, file context menu. So when you when you got a click, when you right click on file, I won't need this thing. So yeah, so it next hit. And so and it will install everything in need, and eventually the visual studio code will be installed on your computer. 3. What sorting means?: the algorithms that you are going to learn are solving problem off sorting ray inputs. In this problem is an array. It can be filled with pretty much anything object strengths. But in our examples, we will compare numbers and the out boot should be array which contains same elements in our case numbers that sorted an increasing order. So that means if we look at every two numbers in ray the right one shoot never be smaller. Dendy left one Okay, problem off. Sorting things in some order is very common in in for Matics, for example, you want to sort orders by price in decreasing order or you want to sort employees by their i. D. There is a lot off examples off task which contains sorting some data. So it is really important to know how to do that. Also, knowing these algorithms will improve your ability to find algorithmic solutions to other problems. 4. Bubble Sort: The idea behind Battle Sword is to lead the biggest element kinda bubble to the end of array. Then do it again with the second biggest third and so on. And after doing it with last element, our array is sorted. So now we have to figure out how to get the biggest element. Judy and we know that in a sorted array, every number must be smaller or equal suiting number behind it. So we look at two numbers next to each other and check that the 1st 1 is smaller or equal to the 2nd 1 If the 1st 1 is smaller or equal to the 2nd 1 we continue with the next two numbers. If the 1st 1 is bigger, we swept them and continue with next to numbers. And when we reach the end, the last number will be the biggest. And we can kind of reduced the array by one element. Because we know that the last number iss on its correct place. I think you get the idea. Let's try some example. Okay, I got here unsorted array, and we are going to sort it as a bubble sword. Would we look at first and second number. We see that 18 is bigger than eight, so that means that they are an incorrect order. So as the algorithm says, we swab them now. We compared the second and third number. We see that 18 is bigger than one. So we swapped them again. We move on to the next two numbers. 18 and 22 18. It's smaller, so that means they are incorrect order. So we just move on to next numbers. Once again, we move and compare 22 12 and once again we swabbed them because 22 is bigger. 22 is also bigger than nine and obviously 22 is bigger than four. You can see there 22 kind of bubbled Judy en. That is why this algorithm it's called double sword. Big elements bubble towards the end, and the smaller bubble stores the beginning. We just finished first round off algorithm and as you can see, the last number is the biggest. So there is no need to compare it to others because this number is incorrect place. And as the algorithm says, we continue bubbling the biggest number towards the end until we have only one number. Okay, so let's start again from the beginning. If you feel like you're understand it, I suggest you pause the video and try to do the rest on your own. When you are done, you can check back to make sure that you did it right. So let's compare eight and 18 is bigger. That means swap. Now we'll get eight and 18. They are incorrect. Order. Right. So what do we do? We will leave them alone and move on to next to numbers. Now we compare 18 and 12 and we swabbed them because 18 is bigger moving on 2 18 and nine where what is going to happen, right? We swabbed them because 18 is bigger and same will happen with 18 and floor. Now we have the second biggest number incorrect spot. I think you should be able to finish this on your own. So buzz video and try it yourself. When you do this on your own, you will understand it better. I promise you, we just go from the beginning, often array and swap each two numbers, which are an incorrect order. And after each run, we get the friendly biggest number two. It's correct spot. That means we don't need to compare it with anything anymore. And we do that until we have only one number. Because when we have only one number, it must be in its correct spot. Right? I will play the other durations without commentary. - Now , we have no numbers to swap. We have only one left, and we know that every number except this one is incorrect place. But that also means that this one is incorrect place because we have only one spot left. So there is no other place to put it in. It must be in its correct place. And that means that we are done and we just sort it. Honore using bubble sword. Now let's go to the implementation lecture and teach our computer how to do that. If you don't understand something, just leave me a question and I'll see you next time 5. Bubble Sort Implementation: Well, hello, gas. And welcome to this lecture and this lecture. We will implement the bubble sort. So let's get started. Once again, I created a new file called Bulbous or dot Js. And in here I get an array. So let's a find the function so function and let's got is one bubble sort like this it will accept a array once again I will just call it and put You can call it how whatever you want , right? You can maybe call differently than this variable bar. Whatever. So right now we need to do several things. So first of all, we need to implement the swap. Okay, so that's what's like a and B where a nbr numbers we already implemented its in the selection sort. So it should be no problem for us. Then what we do? Well, we loop fruity, fruity, whole array except the last like, except the lasts. Let's go this one like i elements because the I will represent the number off already sorted elements. I also write it here. I represents the number off already sorted elements. So basically these big elements that are incorrect place, right? So I is the number of them great. And then we need to implement the outer loop that loops. That basically takes care of the Do it all over again. OK, so let's do that. Let's in here First of all, define de Swap. So we will be looking at A and food die on index. Let's A J and the element behind will be a in booth on index J plus one. Okay, so these are the two elements that are behind each other or next to each other and in here , what do we want to do? So we swept them. If the first number is bigger than the second World, right, So we need to change this thing to this, and yeah, so in here, we implement the swap so we will create new vary vehicle temp, and we will start the value that we have on Index J. Okay, then on index shape. Well said the element on index J two element on index jape as one like this. And then we'll said the element on index shapers 12 element on index. Well, not the element on index day, but to the attempt variable. Because we already over. I d element on index J in here. Okay, It should make sense. I explain it before. So this is these swap. Now it's a finding loop that loops throughout de ho array except the last I elements. Okay, so has do that in here real to find a four loop, and it will be worried Variable called J. So it will start at the beginning, Right? We started the beginning. Always. And it will Lou while j a smaller than a and booth like this that length so except the last I elements. This will loop right now. It will loop throughout the whole array. But we want to get rid of the last I elements, and we will do it by minus I Okay, so we will step before the last I elements before the already sorted elements. So then we will just in common J So this is the cycle, okay? And this thing, we want to do this thing inside of cycle, right? So I'll just move it in here like this and do this thing so that it looks a bit better bad right now, we almost got it. But except one thing, One big thing And that is that in here, we are checking element on J plus one bad. Imagine that I zero, which will be in the first. Like it aeration, right? We didn't sort any elements, so I will be zero. And when we reach, when Jay will be a input length minus one, the J pas one will be a input doug length. So that means we will reach behind your A in here. Okay, so we cannot do that. That's that's, like, a big thing. So in here, we also have to do minus one like this. Okay, so this thing will take care of the problem in here. Okay, We can do it like throughout a bunch of different ways. We can said D j 21 and in here, Index J minus one. And in here, index only J. That would also work that Then we can get rid off this thing. Also, you need to change it in here, but I'll just keep it like it was before, because it's like, um, it's like, Come, let's set to zero. Okay, so it makes more sense about yet. Now we need to take care of the do it all over again thing. So in here I will just define new cycle. It will be a variable called I I will set it to zero. Right, So this variable will represent the number off sorted elements. Okay, off the biggest element that already bubbled towards the end. So in the beginning, it zero and it increments each time with each situation, right? So yeah, and we also need to set where to south. And it will be when I is equal to a input that length. Right? So we write smaller because we want to stop Went in this equal that we need to also define minus one in here. Because when we have only one element, we cannot, like swap it, We cannot do anything. So it's already started. So the same thing as in selection Sword happens in here basically, and I believe this should work. Okay, This should be Yeah. Also need to the findings cycle in here. Close. Close. This like outer loop looking like this. And I'll just a bit style decode so yet and okay, this should work. So let's try it out A and put well, not be right, bubble sort, but was sword. And in here we passed the in poetry. Okay. And we will also look it out. So I'll just copy based it and its control and f five that will run the gold. And let's see what happens. It should be sorted. In my opinion, if I didn't make any mistake in here and yeah, it it's 11 to the 100 days last. So yeah, that's great. This is how bubble sort works. 6. BubbleSort2Challenge: Well, hello, guests. And welcome to this lecture and this lecture we will implement. Well, you will implement the bubble sort the optimal ized double sword. So what do I mean by optimized? Well, do you remember in the explanation video debt is the array might be already sorted at some point off the of the algorithm. So, for example, we still have, like, free. It's rations to go, but the array is already sorted. Well, we will implement it and changed this code so that it can, like, recognize that and it can end the algorithm. So that will, say, save us a bunch of time because we don't necessarily have to go through the whole ray if it is already sorted. So the optimization will work same as double sword. Only this time we will check check for swap. And if no swap happens in the whole iteration. Okay, so in the whole alteration off this, if then if there's no swap, so that means this condition won't happen. Well, you want to and the algorithm. So in other words, just return. Okay? Because the array is already sorted. If there is no swap, it means that every element is smaller or equal to the element behind. Right? Because if it wasn't be if it if it weren't true, these these condition would be for some two elements. It would be true, right? But if it is false for all of them, we know the array assorted. So, yeah, right now it's up to you to implement this thing. And if you get sagged, don't worry. I will be here in the next video. I will explain how to do that. 7. BubbleSort3Solution: okay. Gas. So, as I said before, the algorithm will be same as this one. Okay, so I'll just copy and paste it and put it like, underneath these comments right here. So right now, as I described before in the previous lecture, we need to keep track weather. Dis condition was met. And how do we know whether this condition is mad? Well, let's say Dad inside. If something happens inside, it means that this condition is meth, right? It it wants met at least one time. Okay, so if we set value off some variable, for example, let's say swap happened like this to true. We If if the variable is after this four cycle, if we check this variable and it is true, we know that the array is not sorted because there waas a swap. Okay, but if it iss some other value, right? If you, for example, in here in front of these cycle if we define a swap happens and let's kill it, let's set it to false. So initially it will be false if we checked behind his for a loop, whether it is false, well, if it is still false, it means that we didn't go inside here, so that means this condition wasn't met, right? So that means we need to return. So right now all we need to do is check weather. D su up happened is equal to false. That's all we need. All we need to do and to make it look even better begins. Right exclamation mark in here, which is just negation, right? So that that is the exact same thing as I wrote before. So if it's not true, that swab happened. So basically, if there was no swap, we can return because the array, it's already sorted. Okay? And we don't need to go through, like some other situations rekindles return. And let's change the name of this too optimal ized like this. And yeah, let's let's kill this. So and here I will change the bubble sort to Baba sword optimal ized and our just Runde script. So control a five. And as you can see in here, the array is sorted. So this thing probably works. Okay, I'm not sure, because I'm not sure whether I can put a break point in here to make sure that it happens. So if you click in here. You should see, like some red button as I can see you right now and then If I randy algorithm. So just using f five not control of five, but only a five. It should start a debugging. So that means inside here, When when computer reaches this point, it will stop. Okay? And in here you can see the like, the variables that we have in here, you can see the values of them. So if you have our word, you can see the Js right now it's one. Okay, you can also see Dad. For example, I it's eight. Okay? And the inter length Istan. So we saved us because in this web happened this false. So that means it didn't go inside here. And if we look at the beret, it looks like it Assorted. 1129 10 15 23 28 36 100. So this race sorted right? And that basically means that this algorithm is working. This, like optimization is working. So that is great. You can just jump out of it using this Stop on or you can just hit shift and a five. Okay. About any way you can get rid of this now and you can run it. Why are control and F five so that will run the whole script and you can see that it works so great if you have any questions. If something isn't working, feel free to ask and I will soon exam. 8. Selection Sort: selection sword is one of these simply a soaring algorithm. That is why we're starting with the idea behind Selection Sword is simple. Splayed in padre into sorted and unsorted Bart find smallest number and unsorted part of array and swap it with the first element off unsorted barred. Then we removed the first number off unsorted part and add it to the end off sorted. Barred. We are going to use splitter, which is just index in array to split the array to sorted and unsorted barred on the left side from splitter assorted part on the right side. We have unsorted part splitter starts at zero because we didn't sort any element. And it increases when you add number two sorted part. So when you add a number, D splitter moves behind the number that you just add it, you can think of it this way. You can imagine that you have cards in right hand and you are trying to sword them so that you have them sorted in left hand. Okay, you take the smallest guard from right hand and move it to your left hand. Now, you know that every card in your right hand is bigger than the card in your left hand. So you pick another smallest card from your right hand and put it behind D card you already have in your left hand. And you continue to do that until you have no more cards in your right hand. When you have no cards in your right hand, it means that in your left hand you have now sorted cart from the smallest to D. Biggest. I think you get the idea. Let's try it on our imaginary array. Okay, We have veered an unsorted array and we shall sort it as a computer would. First of all, we are going to split the array into sorted and unsorted part. We are going to do that. Why a spreader? Let's kill him, George. Now we have to decide where to put George. Well, since we haven't sort any number yet, we will put him at the beginning off array. So on the left side of George, we have sorted part, and on the right side we have unsorted barred. Now we are going to find the smallest number and unsorted part. But computer is not a human. He cannot see that one is the smallest. So he have to compare every number in unsorted barred and then he knows the smallest and this is exactly what we are going to do. So we take the first number off unsorted part and compare it with every number behind it. If we find smaller number, we are going to mark dead number as smallest. And once again we compare it to numbers behind. When we reach the end off unsorted part, we know that we have marked the smallest number. So we take 16 and compare it to 55 smaller. So we are going to mark dad as smallest and now we will compare five with numbers behind. We see that five a smaller than 11. That means we move on to next number. Now we compare five and eight and once again we move on to next number. Now we compare five and one and see that five is bigger. So we mark one a smallest and continued towards the end. We compare one and two obviously want a smaller. So we move on and compare one and 20 and once again one is smaller and we reached D. And so we have find the smallest number and unsorted part. Now, as algorithm says, we are going to swap it with the first number. So now we have the smallest number at the beginning. And we can move George by one number and do it all over again. Accused thing that you understand it tried yourself. Once again, we are trying to find smallest number in our unsorted barred. So we take five and market as smallest and compare it to 11 five smaller. So we move on to eight. Once again, five is smaller. So we move on to 16. Now we compare five with two to a smaller. So we marked to a smallest and continue with numbers behind. In this case, we compare to with 20 and to a smaller. If there were any other numbers, we would continue. But there are not any. So we swept the small is number in this case to with the first number. Now we have the smallest number and the beginning. So we move George by one number. I think you should get it now, so I'm going to do the rest a bit faster. Basically, what we do is we find the smallest number in unsorted part and added to the end off sorted part. We compare 11 in 88 is our new smallest number, moving on to 16 where nothing happens now we compare eight and 55 a smallest. We compare 52 numbers behind and C five a smallest. We swap it with first number and move George by one number. In the next situation, we find out that eight is the smallest number, an unsorted barred, but it is already first number in unsorted barred. Well, that is just less work for us because we don't have to swap anything. We just moved George in the next round. We find Dad. 11 is smallest, and we started with 16 and move George. Even though this array it's already started. Computer doesn't know that. So he will go through one Mauritz aeration, compare 16 and 20 and at 16 to the end off sorted pot. And once we have only one number, we know we are done. So this is our sorted array. Let's go and try to implement this thing 9. Selection Sort Implementation: Well, hello, guys. And welcome to this lecture. In this lecture, we will implement selection sort. So let's get started. I prepared the new file. I called it Selection Sword. That Js You can call it however you want. And in here I just declared the new array. This a in front of the name stands for Ray. Okay, I keep track of the data type if you want. You can write it in there. You don't have to. It's up to. So then I declared some ray with some numbers and I also look out the or a so that we can see it. So right now, when we go to view and and the buck guns Oh, you can see the d back on. So you may not see this thing in here, So then you need to go to D back and start without debugging like this. It will start the program, and in here you should be able to see this array. Okay, so let's implement the selection sword. And here lies right, a function. Let's gold is one selection sort like this and it will accept only one argument, right? It will be just some array, and I'll just call it and puts again. You can call it however you want. Okay, but this argument is basically the array that where you want to sort. Okay, so right now we want to implement these selections sword that you learned in the explanation video before, right? You learned the idea. So the idea set When? When we implement some problem, The good thing to do is to break it down into sub problems. Right? Or when we implement algorithm, break it down into, like, sup algorithm, or like small parts of the AL A Great, um, so one we did in the selection sort algorithm. Well, we found these smallest number, right? So that's a big part. So we need to find smallest number. Then we need to implement the swap. Right? So we swept the smallest number with first number behind our wall, and then we need to live through it, right, so there will be like outer loop. But let's in here first defined the find smallest number part. So we expect that there will be something called Wall which will be just an index and and will be remember the wall from the explanation video. It will be just the same thing. Only this time it will be just index. And in WellPoint at first number behind wall. Okay, behind the wall from, like the explanation video. Okay, so right now we can define the cycle. So we need to loop averages, use a for loop, and I'll create a new, very ever got J. And it will be equal Teoh, right, Because we don't have to go through the whole array. All we need to do is go from the wall to the end of the array. Okay? Hope that makes sense. So right now we need to check for the end of the array. Right? So we loop while Jay is smaller. Dan de length off array and the length of a ray is just a in boot that length like this. Okay. And we will increment j each time like this. So Denver kind of take care of the problem of going from the world to the end. So right now, when we index a input on Index J in here somewhere, it will be just the element that we luv for. Okay, Hope that makes sense. So right now, what we need to do. Well, we need to somehow keep track of the smallest number right off the smallest element. So let's do that. We need to define a variable in front of the loop, because if it would be inside a loop, we would override it each time we it's right. Okay, so we need to define it outside loop and inside Alu we can change the value, So let's call his one index off. Smallest. So this is just the index off smallest element. And in the beginning, well, said it too. Oh, so remember in the explanation video when we said the first number behind our wall as a smallest, this is exactly this is this is the line that does that. Okay, so we set as a smallest the first number behind our wall because this wall points at first number behind our wall, okay? And right now, inside as well. And inside this four cycle, we need to check weather d element on index off smallest. So this element So basically the currently smallest element in the explanation video, it was the brew element. Ok, IHS, whether it is bigger than the element that we currently are looking at. So that's the element on index J. OK, so that's the I think it was yellow, right? Somehow yellow color. So the element that we currently compare it. Okay, so right now, if these if the smallest number is bigger, we know that this is our smallest number. So how do we kind of changed this value? Well, we know that inside is variable. We keep the index of smallest element. And we know that on index J is the new smallest element. So we simply change the value off index off smallest to J. Okay, so did basically, this is remember in the explanation video when we change the color of some elemental blue. This is exactly the line. Did does that. Okay, so right now, after this four cycle, we have the smallest element. This on index off smallest. Okay, so end is variable. We have the index off smallest element. And all we need to do now is swap it with the first number behind our wall. And how do we know the index of first number behind our wall? Well, this world variable that we have in here points at first number behind our war, and we didn't change it inside the cycle. Okay, so all we need to do now is said the the number on wall index to the number that we have on index of smallest. Okay, that would it work? Well, we still need to swap it the other way to right. So we need to set the element on index of smallest to our wall. Okay. Like this. Right? Bod what? This work? Think it through. If we set the element on index wall to this, we override whatever it's in here. So then when we set this this side, we basically said it to this thing because we said the element on index wall in here. Okay, so imagine that this is seven. Okay, so we set this element to seven, and then when we are setting this, this element is already seven. Right? So we lost the information, so we need to take care of that problem. So we will define new variable, and we will start the information that we have in here. Okay, so let's go. This one temp is a temporary um, it will be equal to devalue that we have as a first number behind our wall. Then we can override this value and in here instead of setting it too. This will set it to D temp, because that's the value that we want to set it too. Right? So that's the swap. Okay? And right now, all we need to do is Lou Prudence. So So average is defined a cycle, and it will be in here. We will define the ball wary about, and it will started zero. Remember, Dad, In the beginning we put wall in front of the array. So that means in here, right, that means zero. And we luv, I'll war IHS smaller then a and boots that length minus one. Remember, as when I set in the explanation that when we have only one number in unsorted part, we are down. Well, that's this thing. Okay, Minus one means that we are not looping This this loop stops before the last element. OK, so the last element will be the same hope that makes sense. Okay. And in here real, just incremental wall. And this, while increment ation basically means the movement of war by one number, remember? Remember, when we add D element. We moved our world by one number. That's that's it. This thing does that. So right now we basically need to move this thing inside here. Okay? Like this apologised, debit out, so you can see it better. Bad. Right now we loop through the whole race. So this this will take care off the do it all over again. Thing ok. And another thing that we can do in here It said this Jay to wall glass. Wanna? Why? Well, in here we compared the index of smallest to J, right? And if index of small is his wall, there's no need to compare it to well again. Right? So we would compare these same elements. And why do that? We we don't have to do that. So in here the plus one will take care of that. We compare only the elements behind. Okay, so yet is it safe? And let's try this thing out. So in here I will just go selection sort, whether the a input and then I will look the input again. Okay. Like this. And if I run this using control and five, you can also go to D back and start without debugging. As you can see in here, there are D array. There is the you're a but it assorted So this thing works right now let me also check a few extreme cases. So when you test a algorithm well, afore first, This is not the right way to test algorithm. But if you're not a tester and you just want to like know that it probably works, you need to take care of the like, most extreme inputs that you can get. And these will be, for example, that the first and last number is the smallest. So if I run this, there should be like one Wana Wana There is 111 and the array is still sorted. And if I, for example, put in here like some big number at the beginning, let's see what our dead works. And it should be like 11 and last element is 100. So did works. Great. This is the selection sword. If you have any questions, feel free to ask and I will soon. Ex im 10. What is recursion?: What is Rick Ergin Recur? Shin is very, very useful and powerful thing in problem solving. It is one of these central ideas of computer science, so every programmer should know how this works. You can see Ryker Shin in this picture where inside every picture there is the same picture but smaller. When I translated to computer science, it basically means that function goes itself in most cases with smaller argument. As you can see in this example, we have function food, which girls itself. If some condition is met, this condition is really important. Without this condition, we would end up in infinite cycle. And we don't want that for simplicity. You can just imagine that the condition is for example, Arc is greater. Dan zero. If the ending condition isn't mad, we recursive Lee call full with some argument. Usually this argument a smaller or simplified that the initial argument. This is not a simple topic, so don't worry if you don't understand it. Now let's try to implement some rickerson problems and hopefully you will understand Rikers in 11. Recursion: Okay, guys, the first recursive algorithm that you are going to learn is the factorial. So let me explain the factorial. If you're not sure, if you're you maybe know it from, like your meth class. But if you don't, it's OK. It's something that looks like this. So some number and an explanation Mark and it is basically equal to the number times D the all these smaller numbers basically all the way up. Teoh. Wanna Okay, so this is great for Rikers in Okay, I will explain in a minute. Why? But let's first of all, ride Iago to them. So pictorial. Oh, well, function factorial. Okay, So function and called his one of factorial and it will accept just, um And okay, so this and basically stands for this six in here in our example, and it will return. Well, first of all, let me just do the algorithm. Dad is imperative. So it's It's not like recursive. So in here. Let's write while and is Grazer den one. What do we do? Well, we just defined and we will set and to end times Well, no, no, no, no. Was defending the area month. It will be easier. So variable called result. We will set it to end right here and in here. Or do we do? Well, we first of all d Crimmins n okay. And then said the result to result times And Okay, so this is basically while do we wrote in here, right? We just multiply it all by all the numbers that are smaller than an all the way up to one. Okay, great. And after this cycle, Wilders returned to you. Result. So let's check out that it looks it. It works. So cons are that Locke and in your let's write factorial off four Okay, like this and for understanding, it should be four times free time. Suit suit as 24. Yeah, it's 24. I'm not sure where you can see it, but it's just 24 in here. So yet, and let's changes algorithm. So that iss it is recursive so in here. Let's change this to bacterial. Or let's write this one recursive factorial like this and let's do it. So we need to define the ending condition. So if and IHS equal to one, we can say also smaller than or equal to. But that's yeah, That's okay. We can do it like this. But if n is smaller than or equal to one, we return one. Okay. Like this. But if it is not, we we can write in here else. But it pretty much doesn't matter what we writing here else or reaches right underneath. So yeah, but if it is not, we return and times the recursive factorial both and minus wanted. Okay, so yeah, this is diva cursive version off this algorithm. It definitely make take some time to understand rickerson. So don't be too hard on yourself if you like. Don't understand it right now. So what do we do? I try to explain in the best way I can. So let's say Dad and is six. So the computer value is dysfunction like this. So it goes in here into this if condition and end its six. So it's not smaller, so it jumps into this Els branch, okay? And in the year it returns six times the result off recursive factory off five. Right? Because six minus one is five. Okay, but computer doesn't know what the result off this iss. Okay, so it gills back in here and goes it with five. Okay, so we need to return six times. Recursive factorial. I'll just write f That will be faster off five. Computer remembers it, but it calls the factory off five. OK, And in here in D Ennis. Five. So it will just go inside here. Five is still bigger than one. So it goes once again into this else branch and in here it will return five times the result of six. So the factory off five will return five times the results of factory or four. OK, does that make sense? Right? Remember that this is just a function call. You can imagine that you have a different function defined in here. The opening differences that this function does the same basically and calls itself. But anyway, the factory of five will return five times factory or four. But we still don't know what factory or four s, So we'll go once getting here. So, Ennis four it's bigger than one. So we go once again in here and defector of four like this vector or four. Well, be equal to four times the factorial off free. I forget about the times and we will do runs again The same. So if free is greater, it iss we jump into this else branch and in here we can see that and we will return. Defector or free will return. Okay, So defect Toral for free will return this thing So an which in this case is free times the factorial off to Okay, we call this with two. So we call this Rikers defector with two. And once again we jump into this else branch and the victory off to will return to times factory off one. And right now you need to be be aware of this. So when we called the recursive factory or with one, let's see what happens. The if condition will be true because one is smaller or equal to one, it is actually equal, right? So we will return just one. So that means the ending condition is met. So if f f of one will be equal to one vector of one is one. And it also makes sense because of this thing, right? We multiply it until we reach one and 11 times one is just one. So yet But right now what happens is computer knows what sectoral of oneness. So instead of dysfunction, call in here. It says the result of this. So in here it will get rid of this thing and based one in here because the this returns one . So it knows that defect Cherie off too. It's too, And right now it can confuse the factory or free. So inside here. It doesn't say Freetown's factor off to It says just free times, too, because factory off to is too. Okay. And that's just six. Okay. And in here, once again, we already know defector off free. So we just say, four times six, which is 24 right, So 24. That's why we get 24 in here. Okay? And once again, in here, we can see just say, five times 24 which is 120. I think it should be. And in here we just write six times 120 that is just who? 720. I think so. This is the actual result of this. So let's see, if I write in here console dot lock and in here I just ride to Riker's effect. Ariel, Both six and run this program. It should say, 720 and it does. Okay, so this Asai right in the Komen in here, in the comments that was actually Howdy, computer. Find it out. The result. Okay, that was actually exactly how the computer computes this. So I hope that makes a bit of sense. You may need to watch this lecture again, or if you just don't get it after, like, free time to just write me a message. I will try to explain it somehow differently and hopefully will understand it. That Yeah, that's pretty much it for this lecture. If you have any questions, feel free to ask End al soon exam. 12. Recursion Debugging: Hello guys. Since rickerson can be really complicated topic, I decided to spend one more lecture about it. So let's see whether I can make it clear. So in here, let's do something like bring the end so that you can see what happens. So console that lock. And in here let's bring something like Compute sing sectorial off and in here let's write d n so devalued and let's also said a new variable. And in here let's said it sued the result of the recursive call so you might be confused by the recursive call being in the return statements. So I will just put it before it. And in here I will use the temp variable. This is exactly the same thing as before, But this might give you a bit off more sense, right? It might be better for you. So right now, in year after this, I will also Brende the for example, the result off factorial off in mind. Swan IHS, I may be need to put it in Saudi parentheses like this will be, well, ISS and in here will be the actual results. So that's in the attempt Variable. Okay, so this will print of stunned some stuff into the council. Hopefully, you will be able to see it. So if I it the control and five you're not, you probably cannot see it, but in here it says computing factor or five 654 free to end one. And then it says the result effect. Torrio is 126 24 and 120. And why's that? Well, remember dead when we compute this in here. Computer wants to set the temp variable to something, and that's a result of function goals. So computer evaluates this functions as a cause dysfunction, basically, and it weights what dysfunction returns. But in our case is just the same function, right? So there's just a coincidence, but it works just the same way as if you call, like normal function somewhere in your code. Okay, so there's like, not any magic behind it. It just only this time you're calling the same function. Yeah, but but there's no magic behind it. So let me get rid of these locks and let's put a break point inside here and debug nesting . So click on the F five on your keyboard and all we can see well, the recursive factorial. It's called with an equal to six. That makes sense. That's the initial call. Then D computer checks whether six is smaller or in cultures to one. And using these arrows, you can just step in your cold, right? So we will step as the computer evaluates it. So I will just step to the next step. Hand in year is the next line. So in here, D Computer says the 10 variable is still undefined, right? Because we didn't actually set it to anything yet. It's only result off some function call, and we don't know what that is. So if I click on this step into, we get back in here, okay, but in here it's five instead of six. So that's the recursive call off. Six man is one. So right now it's five and we runs again. Go inside here and once again go back again. So right now it's four and same thing will happen a few more times. There's two, so to a still bigger than one. So we will do one more Ryker sickle. But right now the end is one. So when I click in here, we will return one. And that's the end of dysfunction. Co. Okay, bad. We will get back in here and see the temp is equal to one. Because we finally got the result off some of these calls. Okay? And we know dead weekends returned two times one. And if I step next step, we know that in here. Let's see what's happening. Yeah, and it's free. And the temp is, too, because temp is what we got. Wendy, when we call Rikers a factory off to OK, so then was free in this case. And if I go back again, yeah, I will go for right. So we will get four times six, because that was the result. And then we get five times 24 right? Hopefully that makes sense. Because the Indus Stem variable it's the result of a function. Call off n minus one. Hopefully did make sense. And last night we get the final result. And that's the end of this in consulate sprinted 720. So yeah, this Hopefully this makes a bit sense. You can put a break point somewhere in your code and let the evaluation off. Decode stop and check out how the variables looks like. How do you function calls like works? You can even step throughout how the computer ever evaluates these expressions, right? Whatever expression you have in here, you can stop it and see how the computer works. So you can use the burger to understand Ryker Shin, and that's pretty much it for this lecture. If you have any questions, feel free to ask, and I'll see you next time. 13. Quick Sort: Quick Sword is recursive sorting algorithm, and the idea is to grab the last number in our unsorted array. We call it pivot and move every smaller number to the left side of pivot and larger number to the right side off. Then we are done with it, and Deep Evil is incorrect place and we call recursive Lee Quick sort on numbers on the left side and on the right side from Bill, the recursive girls will stop when there's only one number left in the array. This may be confusing to you. Let's try it on our imaginary array and hopefully things will clear up. Okay, I got here in array and as algorithm says, we graft a pilot which is last number in our array in this case, eight. As I said before, when we are down, we want these smaller numbers to be on left side and the bigger numbers to be on right side . So we get this wall which represents the splitter between left and right side and also pointer, which indicates what number we are currently comparing. So we compare pointed number with If it is smaller, we swap it with the first number behind our wall and move our world by one number. If it is bigger, we just move on to next number. So let's Judas to a smart in eight. So we swap it with first number behind our wall. But in this case to hiss first number behind our wall. So we just move. Our war five is smaller than eight. So we swept it with first number behind our war. Bad ones again. Five us already. First number behind our wall. So we just move our wall. Then we continue comparing 22 our favor. Well, 20 is bigger. So s algorithm says we move on to next number 15. It's also bigger. So once again, we move on now one, It's obviously smaller. So we stop it with first number behind our wall in this case, 20 and move our wall. Wait five and one are clearly in incorrect order. You might say Yes, they are. But they are both smaller than our pivot and dentist. All dead we care about. We continue back and bearing 11 with our peeled 11 is bigger. So we move on. Now we know that on the left side off our war are numbers that are smaller than our pivot. And on the right side, there are bigger numbers. So where should be our pills? Well, it should be. Where are Wallace? Right. So we swapped Deep devote with first number behind our wall. And that means our people is incorrect place. Now we recursive we call quick sort on left and right side. Let's take care of the left side. First we a glass number as our pills in this case one and we do the same trick as before. So we compared to and are pivot. We see that to his vigor. So we move on and compare five with one Once again, five is bigger. So we move on and we reached our pivot. So once again we swap it with first number behind our wall in this case too. Now we know that one is incorrect place. Let's do this. Same 40. Right? Part 15 is our pivot. We compare it to 20 20 is bigger. So we move on to 11. 11 is smaller. So we swept pit with first number behind our wall and move the whoa! Okay, Once again, we have reached the end So let's put our people in its correct place by swapping it with 20 . Okay, now we know that 15. It's also in its correct place. Now we're cursive. Lee called Quick soared on left and right side off our pivots. Once again, let's take care of the left side. First, let's pick our pilled In this case, Sue and compare it to five. Five is bigger, so we do nothing. And once again we have to put pivot in its correct place. So we swept two and five and we are done. Okay. Now we need to take care off. 11 25 bar. All of these are only one numbers, right? So we know that they are sorted because the ending condition off Quick Sort says that if the part that we are sorting have only one number, we are done. So that means the array assorted and that is pretty much it. If you don't understand something, feel free to ask and I will soon exam 14. QuickSort Implementation: guys and welcome to this lecture. In this lecture, we'll create D Quick sword algorithm, so we will implement it and let's get started. So let's defining function and let's go it Glick sword. Same as in merch, sort. The quick start function will accept a beret that's input and then two indexes that defines the part of the array that we want to sword, including both elements on decent indexes. Okay, so from and to and let's do it. So first of all, let's to find the recursive condition. So if right now we need to decide went to end. So we want to end when from its equal to two. Right? So, in other words, we don't want to end it from it's smaller than two, so that will look better. So if from its smaller than two, we do something out of why, sweet end. Okay, So if from is smaller than two, we called the partition function that will return as the index off built. Okay, so, Algaze, right in here, index off, put like this and I'll set it to the result off partition function that we will define later on. Okay. And it will accept a beret in boot. And what else? Well, we also need the firm and two indexes, right? And that's it. This function. Well, return the index off. Okay, so the place where our people ended up. And as you might remember from the explanation video, when we get the index of private, we call quick sort on the left side, from it and on the right side, because we know that the people is incorrect place. Right? So in here, I will just do that. So I'll call Quick Sword on the left side. So a input from and the left side means index of beveled minus one. Right? Because we don't want the bill to be in there. B, we want only the elements that are in front, off build. Okay. And we also do that 40 right side. So quick, sword. Once again, we passed the array and in here we ride index of people, but plus one. And we are starting to index too. Okay, like this. And that's about it for the Greek sort function. So let's right now defined e partition, so function, partition and in your ego, except day array input and then the from and to indexes like this. And we will do exactly the thing that we did in the explanation video. So what did we do? Well, we kept our private in some variables, so I'll just go by what? And it will be the last element of the part that we are sorting, and we know where the last element this write its own index to. Okay, so that said, we grab our private right now. We also need to define the wall, right? That splits the smaller number and the bigger numbers. Okay, so was define it. So whoa, and it will be equal to what? Well, we need the world to be in front, off the part that we are sorting, right? So whoa will be just index that points to the first number behind our walls. So in this case, we will initialize it to from, and I'll just put it into the command. So points at first number behind our wall from the explanation video. Okay? And right now, all we need to do is go through all the elements from wall or from from index duty to index and check whether there are small and if they are, we swabbed them. So let's do that for cycle and ill defined variable called I and II initialize it to from Okay, Now I want to end when from IHS Smaller Dent or actually only smaller Gentoo. Because we don't want to compare the private right because private is on to index. And why would we compare private to Pilot? Right, That doesn't make no sense. So we want to stop in front, off the pilot. Okay, So while I it's smaller than two and we will increment I So that means we will move into your A from left to right and for every elements, what we need to do while we need to check weather, D and boot on index I a small island in or equal to our private. And if it iss we swap it with first number. Behind are wall. So thankfully, we have the index off first number behind our wall in the wall, very about. So right now we need to do is swab them. So you probably already know how to do that. I will create a temporary variable, and I will set it to a input on Index. Let's say wall and sorry like this. And right now I can set the element on index well to the element dentists own Index I right , So the currently compared element that is smaller or equal to private? Okay. And right now I need to do a said the input on and excite to the temp variable so that we don't lose any numbers. And another thing I need to do right now is move the wall by one number. So movie wall, I'll just do it like this because when we swept the numbers, we know that this number iss these smaller dinar, period. Right. So we need to move our wall, as in the explanation video. Right? So we will simply do that by incremental NWO. So world plus plus then will add one to devolve variable, and we will actually kind of move our war. Okay, I hope to make sense. So right now, when this cycle is done, we have reached our devote and we need to put him in its correct place. So we need to swap it. Swap built with the last number first number behind our wall. So thankfully, once again, we have it in our world. Variable. So all we need to do now as said the A and food on index to to our A input on index wall and also said the A input on index wall Su What? You might think that I would do this and that I made a mistake and forgot to like store dis . But actually we already store d private in here, right? So private equals a in the to. So we can simply just override it and don't worry about it. And in here we can just set it to our private like this, so simple as that. And yeah, that's that's about it. That's the swap. And when we scrubbed them, we know that our pilot is incorrect place and we can return the index of pilot. And in this case, it's the It is starting to you. Oh, variable. Right. So, Algaze, right to return wall like this and that's about it. This this should actually work. So as you can see, the quick sword is kind of fast to implement. Like like there's only problem If you want to really understand what is going on about the Ricker Shin you need to understand the Rikers in in order to know what's going on in here. But the partition function is fairly simple, right? And yeah, The only complicated thing is the quick sort. Rikers in calling body yet let's tried out with water. It works. So if I butt in here Quick sword. Yeah. Quick sword. And in here, 18 foot. And we started in the zero. And we go to index Teoh length length minus one. Because that the two is the last element that do you want to sword? Right? And in here, we can just go and write council death lock and the input. So in foot like this and this should work. So let's try it out. If I had control and a five, as you can see in here D or a assorted, so that's pretty cool. We have successful implements. Quick Sword and yeah, Wasn't that Howard? Right. So that's it for this video. If you have any questions, feel free to ask. End out soon. Exam 15. QuickSortChallenge: Hello, gas. And welcome to this lecture and this lecture. I will explain the challenge for you. So what do you will do? And it's basically the problem with Quick Sword is that sometimes can happen, Daddy or a is, for example, already assorted. So in order to get the best time complexity, right? We want the private to end up somewhere in the middle of the part that we are sorting. So, for example, when we are sorting right disarray, we want the pirates. So in this case, the last element to end up somewhere in the middle off the sordid array. Okay, I hope that makes sense. Because when it ends up in somewhere in the middle, we can leverage the recursive calls. We want the recursive girls to be called over the bridge in that same sized race, right? So we don't want a case like this one where the diver ends up at first place, right? So it ends up right here. We don't want that because then we cannot leverage the full power off off Ryker Shin. Right? And the time complexity goes to oh and squared. But you will get to it later on so right. The point is that we want the Bible to end up somewhere in the middle. So there are some techniques, like how to do that, how to pick pilot so that it ends up somewhere in middle. Because right now we are picking the last element. Simply, it's it's simple solution, but there might be a better one. So, for example, the commonly come solution that this might be used is to pick Medin off free values so you can either bake like free, random values, free values on the random in Texas. So, for example, like on index zero aids, 20 whatever. Or you can pick like free numbers on indexes from then from plus two, divided by two and then to right, so in your there should be parentheses. This so we picked the first, the middle, the last element, right? So we big free elements and we check and try to find D middle value writing. Marien value Saudi the middle one, and when we find the middle one, there's a pretty good chance that it will end up somewhere in the middle of the array, right, so that might give us some leverage on the time complexity. So your task now it's to implement this solution. So when you are picking a private, you should pick the Bible it from free values and the buyer. It should be the the Madden value. Okay. And then you also need to change a bit of code in here so that it actually works. But yeah, your task is to implement Met in off free values, 40 partition function. 16. QuickSort Median: Well, hello, guests. And welcome to the solution. Gonna thing kind of video kind elector. So, anyway, and this, like, try will talk about how to implement the Madden off free values. So let's get started. Well, first of all, let's look at the partition. So, Al, just create new function. Well, actually, let me just copy paste this one because there are not so many changes in there. And in here I'll just call it Partition Median like this. So it, except same number of arguments. Everything stays the same. Except this part. Right? So we don't like pick pivot, Just just as a last number. So what do you? Well, as I said before, we need medicine off free values. So I will create a variable. Let's call this one index soft Vibert. And in here I will set it to let's a result off a function call. So I will defining function later on. And this function will accept the array and free indexes. So from then, the from plus two divided by two. So basically the middle index and dandy to index. Okay? And I also to parse this thing to in teacher right, because the middle value. We don't want the middle index to be like free 0.5. Right, So in here, I'll just write bars and like this. Okay, so this function will return us the index of our pilot, right? And what we need to do now? Well, we send the Bible to the value on the index, right? So it except private And right now, this well work if the index of private is equal to two, because in here in this cycle we can count on the fact that the private is on index to because we don't compare I to next to and we in here kinda you spy, but as a temp variable when we are swapping the two and you All right, so we need Teoh. Change that. We need to check the fact that the Bible is actually on index. Ooh, Right. So, in your we right, if the index of private is equal, well is not equal to to. Because if it is equal to two, we are good to go, right? This this killed will work just fine. Bad if it is not equal to two. What do we need to do? Well, that means that the value of our private it's somewhere in middle of array. Right? So we also need to sort the last element. But what if we just swapped the last time and with the with the with the value where our index is well, with deep, I've it with our current private, somewhere in the middle of a ray, it would work, right? So if I just say the a input on index index of our private like this, we'll be equal to a input on index to, and we kind of moved the last value. That is not our pilot currently, and move it override the value of our pilot. But the over the store, the value of our private in here, and we don't compare the value on index to anywhere in disco. Right in here, we kind of work under the Burma's dad on index to is our private and we have the private sore in our variable. Right. So we don't work with the a input on index. Do we work with this variable? So that is great for D change of in this killed. Also, we need to check in here whether this will work. So we over i d last Selman with the first number behind our wall so that its cool And then we said a to private. So we also don't use the A input on index to to kind of assign value to some other some other value, right? Some other variable or something like that. So this should also work. So that school Okay, guys. So let's to find imagine that many and function not variable. So it will be a function median and it will accept for arguments. So the first is the ray than the first index t second and the third electors, and we need to pick the middle number. So was the find a variable and it will be a 1,000,000,000 variable and houses, right. Like first smaller than a second. You should never name your variable like there's bad. 40 teaching purposes destroyed works So in here I will just ride a input on index first IHS smaller Dan A and boot on index second like this and also define a second variable. So I'll just copy based it in here and it will be second is smaller Dan third like this. So in here will be second and in here will be third. Okay, so right now what we need to do? Well, we need to check 40 cases. So if if First if the first is smaller than second and the second is smaller than third, we need to return the second right because well, first, this smaller 12th and second this more than third. So the second is actually in the middle, right? And yeah, let's do another one. So and if de first is bigger, so that means negation off this. So the 1st 1 is bigger than the 2nd 1 and the second the the 2nd 1 So the 1st 1 is bigger dense Second Guan and 2nd 1 IHS Smaller Dent. 3rd 1 So dead means the 2nd 1 is the smallest. Right? So the 2nd 1 is the smallest, and we'll just return the smaller value off thirst and third. Right. So we just check f d. Well, in here we can write, like, if that will, maybe we make more sense. So if the first is smaller, den third, we return first, and otherwise we will return third right there, so return third. So these are two cases that can happen. There are only four of them. I believe so. Yeah. Let's do another few of them. So in here. Let's check if the 1st 1 is bigger than 2nd 1 And the 2nd 1 is bigger, Dan. 3rd 1 that means the 2nd 1 is once again the the middle element. Right? So because if the first is bigger, biggest second and second is bigger than third, the second must be in the middle. Right? So if first is bigger Dan second sold. It means this. And if second is big well, yeah. If second is bigger than 1/3 we returned second, right? And yeah, the last condition will look similar to this. So that will be like if first this smaller than second Bob second is bigger, Dan Third. OK, so if first is smaller than second, so second is big in this case, and second is also bigger than third. So that means either first or third are one of the like, smallest, right? We don't know which one of this about one of them it is. So we check in this case whether the element on index first, it's smaller than the third. And if fair days, we need to return third. Because we are actually looking for the bigger element right now, because we know that the two is the biggest. So we know that this will be the extreme value and we need to find a median values. So if we find the smallest, so that will be, for example, the first in this example because it's smaller than third. We know that the third must be in the middle, right? And if it is not the if it is not this case, we can simply return first because we know Dad. Well, we know that thirst is bigger than third, so that means yet thirsty. We know that thirst is smaller, Dan Second, right, So we know that second is the biggest. And in here, we also know Dad first is bigger than third. Right? So we simply return first. So this might be a bit confusing to you. Yeah, I This might not be the best explanation off this. It's though it's the fastest I believe implementation off the Madden. You can also do a thing where you just simply create new array that contains the free elements that we passed, right? So the free values and you simply sorted using, sorted using, for example, merge sword okay. Or you can started using the A selection Sore right it's up to. So it's a aerated that is containing free elements. These sort will be extremely fast, right? So when you sorted, you simply look at D at the middle element. So de tous equal to element on index one and you check what index? Well, you check the values whether they are the same. So if if the element on index oneness same s the element on index first, you know that the first is your median value, right? If you're not sure about what I mean, I can implement it. Just write me a message in the question section. OK, so right now we got the partition Madden, and we get the many and function. So all we need to do now is defined D Well, the quick sort, right? So did quicks, ornament and function. So I'll just copy and paste this one and put it like underneath so in here. And I'll just call it Quick Sword Mehdi in like this and we also need to change this to partition Madden. And in here we also need to change it to quick certain median and same in here. Okay, so right now we can does this thing and hopefully it will work. So Madden and let's see. So if I run this as you can see the ray assorted correctly and in the comparing off the race, you might see that this one is actually faster. So yeah, that's how we can solve the problem that we that I explained to in the previous lecture. And that's pretty much it. If you have any questions. If something isn't working, feel free to ask end l soon exam. 17. Merge Sort: merch sword as sorting algorithm based on Rikers in the idea behind Mercer is to split the array into two smaller arrays than split these two a race into four, even smaller erase and counting in splitting until we have only one number in array. And in second part of the algorithm, we will merge these race into big around. And while we are merging these race, we are sorting them. I think you will understand it better on an example. So let me show you. Okay, I gather you're array and we are going to split it into two parts until we reach a point where there's only one number in every split it, Ray. And here is how it works. As you can see, we split it the initial array into two. Now we are going to recursive Lee do that to our to split it race, and we get this. So we are splitting every array that we split it instead before, okay, and we still have two numbers in a tray. So we are going to do the Rikers in once again and get this. Now we have reached de borned where every array have only one number inside, so we will start merging. I am not going to explain how the merch function works. All you need to know is that when we merged to sort it erased together. We also get sorted gray. So we apply merge on every to a race, starting with one and 11. And as I said, the merch always returns sorted. All right, that is containing all the numbers from these two input race. So we will merge once again and we will get this. Now we are getting closer, but we still need to do one merge. And here is our sorted Ray. Now I am going to show you how d merge function works. We get to a race and we will merge them in one so that the output or a is sorted. We are going to use these two pointers and ensure they are pointing at the first number off each. Right, since both of these race are sorted, we just compare the point in numbers and add the smaller one to out with Ray. Then we move our pointer to the number behind the number that we just added in this case. Remove it from 1 to 8 and do this all over again. So we compared. He pointed numbers in this case, eight and two. Then we add the smaller number two our output array and move pointer from two to number behind it. Now we compare eight and 55 a smaller, so we add five to our out Padre and move our pointer from 5 to 16. Now we compare eight and 16 and at smaller number to the end of our output and move our pointer and we do the same until we reach the end off one array. When we reach it, we add to our out betray the rest of the second array in this case only 24 and that is it. I hope you understand this idea. Let's get to the implementation and show compete or how to do that 18. MergeSort Implementation: Well, hello, gas. And welcome to this lecture and this lecture. We will implement the merch sort. So let's get Saturday. First of all, I got here a all right? First of all, Ray, And in here I did. I do something like slice. So what it means. Well, this slice method basically basically only grabs some part off this ray off this ray. Okay, so it grabs from element zero on index zero to element on index five. But it doesn't like contain the element on index five. The last amended. Its in this array is the element on index for From Desert. So it will grab 012 free for so these numbers. Okay, I hope that makes sense. We will use it. And the Mercer. So let's define the march short solos, right function merge, soared and is well, except they argument. First of all, for A and Abel, except multiple arguments. So we also need to define 40 recursive calls. What part of your a r re sorting? So we need to define like we will do that by using two indexes. So Darabi first index that will be caught from and it will define from what index we are sorting, okay. And then will be the second index that will be called to and that will define do what index we are sorting. So for example, in the initial call, the from will be zero. So we are starting the element on India zero all the way up to the element on index input that length minus one. So to the index off the last element. OK, I hope that makes sense. So yeah, let's do T Mercer. First of all, let's define the ending condition. So will you want to end when the from well Wendy Tu minus from he's smaller than one? Why not equal? Because we want only one element right? When we have only one element, we end so return. So why not equal to one? Well, because to is the index of the element that we want to sort So when from is equal to zero and two is equal to zero, then we have only one element. And this part of the array, the element on in the zero right. But when from is equal to zero and two is in equal to one. We have two elements the Elemental Ninja zero and the element on Index one, right? So if if two is one and from zero, we don't want to end right, we only want to end of these are equal. I hope that makes sense. It should. So if we don't want to end, what do we do? Well, first of all, it's defined. A variable called Middle and this variable will be equal will be basically the middle index . So remember when we split the D array, we are calculating the point where we want to split the array. Okay, I hope that makes sense. So the point is just to bless from divided by two. Right? So because let's take an example like so let's say we starting from zero and two, it's 10 or are from five. And to extend. Okay, so in here we got 15 and we will divided by two sold at 7.5. So that's exactly the middle index, right? 7.5 is not an index bad. It's like the middle. So that reminds me another thing we need to do and that's like are said to Indy, Jer, because we can get like 7.5 in here. So we need the index. We don't want, like, 7.5 and stuff like that. So then we do the recursive calls. So we split the or a, and in here will be the first. Well, actually, we need to as the or a so input, and then differs. Recursive calls basically splits the first part. So the first part starts it from and ends at two. Well, no ends at middle. Okay, So from and middle and the second bar starts at middle and ends at two. I hope that makes sense. It's exactly the same as in the explanation video. So from and end said Middle, including the middle element and the second goal. So merch sword, a input will started middle last one. Because we don't want to sort same elements multiple times, and it will end middle class want, sir, and it will end at index too. Okay, so these two lines will take care off the splitting. So that's how we spend the array to multiple multiple times. So until we get on Lee, one element, that's exactly what these two lines does. And when we are done with these bidding. We need to merge them together. So we were called a merch function. That's not defined yet, but we will call it a well past D input. Then we will pastie from middle and two indexes. Okay, and that's it's for the March sort function. Let's the finding merge function so dysfunction, we'll take care of the merch. As I explained in the explanation video. So it will accept the input from middle and two indexes like this. And as in the explanation we took to race so technically, we are not taking to a race, but like we kind of do, because the first array is defined as a from 222 Sorry to middle Index, and the second Array is from Middle plus 1 to 2 index. Okay, so we are kind of taking to race in here, and it will be clear after I do this so left will be equal to a and boot that slice. So we basically guppy the in padre from index from and to index middle plus one, because the first array started from and ends at middle right a D middle element. As you can see in here. But the slice function, as I explained in here, grabs the the last element that the slice function have is the element on index four in here. Right. So we need to write in here middle plus one so that we can get the element on index middle into the left array. Okay, I hope that makes sense. And we will do the same for the right. So basically, the left and the right are actually the race that we are taking, so this will be middle last one. So that will include the element on index Middle plus one. And it will end at index to also plus one because it's containing the to bless one. So Samos in here. And yet these are basically the to arise that we want to sort merge. Sorry. So let's also define de Pointers. So d left point there little fine, that the beginning Same as the right pointer, right pointer. And then also point at the beginning. And what we want to do now Well, we want to do the thing that we pick always the smallest, and put it into the out batory. And in this case, the out betray is the A input. So maybe changed it. I will change it to a output so that it maybe makes more sense for you. Okay, So instead of input, it will say out output. So this actually the output of dysfunction. Okay, So from we started from index, So for it was defining very difficult I and start a d from index while I a smaller or equal , we need to be equal to two. Because on index to is the last element that we want to merge, right? That's the last element that we want to merch. So why did the smaller week or equal re incremento I and basically in here what we need to do? Well, we need to pick the smallest elements. So if left on index left pointer is smaller, then right on index. Right pointer. Sorry. Right pointer like this. So if we go in here, that means the left number that's currently pointed to its smaller. So we will set it as a as a output. Right? So a outward on index, I is equal to left. That left left on index left pointer. Okay. And we also need to move the pointer. Remember in the explanation video, when we move the pointer to next number, that's exactly what is happening in here. And this is the part where we grab the smallest number and move it into our out buttery. Okay? And let's also the find the else branch because we need to take care of the case Where the right Reyes smaller. Right? We need to put in here equal. So did the algorithm is stable, right? That's that place a he draw in the stable of the algorithm. And if you don't know what stable algorithm stable sorting algorithm means, don't worry about it Now, I will explain it later on. Okay? So if we go to the else brains, that means the right the the element in the right Reyes smaller. So we need to set it as a output and income nd right pointer. So right, pointer, plus bus. And right now, what we also need to do so that we don't compare with undefined because sometimes can happen, Dad. Well, always happens dead in the left array or in one of these race, we ran out of numbers, right? So we get all the numbers from left Array. But in the Ryder A we we still have some numbers. Okay, so we need to take care of the problem. Because if we renowned of the numbers in left array, we would compare the undefined value in here because the left pointer would move to the behind the end of the array. Right. So we need to take care of the problem. And we will do that simply by writing in here. If the left pointer IHS IHS equal Sudi left that length. Sorry. Let the good like this. And if it is equal to left that length, we need to move all the elements from right away to the Alfa Toray. I hope to make sense. So in here. All right. While you can also use for a loop that's up to you that I'll just use the while loop. And in here we write while d right pointer is smaller than right that length like this. Wow, the right point or a smaller we will said the out vittori on index I to right two element in the right part of the India right away. Okay? And we also need to increment the right index, and we also need to increment the I Index. This is important, because otherwise we would just override, uh, the same index. Right. So So we need to change it. And yeah, if we get too deep on where we ran out of the numbers in right away, we can return because we we ran out of all the numbers because we don't have any numbers in left array. Otherwise you wouldn't get inside here. And when we get outside the wild cycle, it means that we don't have any numbers in right array. So yet, right now, let's do the same 40 right bar. So we don't write else if Oh, also we can. But yeah, let's just copy Basit And in here, let's take care of the running out of the right. All right, so if we take all the elements from right away, we need to move all the elements from left array to the out for Trey. I hope that makes sense. Same as the explanation So in here will be left in here, will be also left in here, will be also left and in here will be also left. And in here will be also left, so yeah, and I think I think this should actually work. This should work. Okay, so let's try it out. Let's does this thing. So I'll just get rid of this stuff. And in here, I'll just write a input and I'll sort it. So Allergies, right? Merch, sword and up as D and blunt array. And in here I will bast d from index. So that zero and the two index and that will be a in boot. Dad length minus one. Okay, so let's see what her dad works or control at five. Well, around the code. And as you can see in the output, it actually works. So that's pretty cool. You successfully wrote the merch sword, So yeah, that's it. That's it for this video. If you have any questions, feel free to ask and I'll see you next time 19. Time Complexity: So what a Sam complexity. And why do we need it? Well, time complexity basically describes the amount of time it takes to run an algorithm. Because how do we decide what algorithm is better? Well, we can either look at how much space it consumes. Then we would look at space complexity. So basically how much base in memory algorithm needs, But mostly we don't care about dead. Mostly we care about time. So obviously faster I'll go to them is better. Now, how is it computed? Well, the one thing you can do in order to measure efficiency off algorithm is to simply start stopwatch at the beginning off algorithm and then nd self watch. And you have your time. Right? So would this work? Well? No. There are a couple of things that will change your value. For example, if I run the algorithm on my laptop and FBI runs the same algorithm on their supercomputer , we would get different results. Right. I know this is extreme case, but I hope this makes sense. The device on which you run your algorithm matters that also the sides off in put matters right. Imagine that I have a function that will sum up all the numbers in array. But obviously, if you call this function with 10 elements, you will get smaller time than when you call this function with 10,000 elements. So D input length also matters. So the approach of measuring time just doesn't work. What we need is some way of representing a complexity, and it should be able to take these sides off input into consideration. And it should also get rid off the difference between devices. So we need a bit more mathematical approach. We need function and what dysfunction? Duhs? Well, it takes the length off input as a argument and it returns a number off operations. But what do I mean by number off operations? Well, it is just basically every operation you do for example, the assignment operation the plus operation, the compare operation, and so on and so on. So, for example, if I have here this algorithm, you can compute the time complexity like this On first line, you can see assignment operation, So that is one. Then in the for loop, we initialize I 20 So that s suit. Then we repeat these four instructions 1st 1 is that we check whether I a smaller than at 2nd 1 is this plus operation. 3rd 1 is this assignment operation and last one is this increment operation. So these are for instructions that we do and dives, right? Because we do this while I a smaller done ad. So the time complexity of this algorithm is four n blast to plus two. Because we have to assignment Operation One here and second here. And these are happening only once, no matter what the length off input s. And then there are these four instructions and these are happening end times each. So if the input length ISS, then we get 42. If the input length is 100 we get 402 because the overall time complexity is for an plus two. Now I want to leave with a little bit of teaser for next lecture. Imagine that I have discovered. So the only difference is that now the plus an assignment is in one operation, right? So is the complexity of this free and plus two, or it stays for and plus two. And the answer may surprise you a bit. It pretty much doesn't matter. But I will talk more about it in following lectures and with that being said, if you have any questions, feel free to ask and I will soon exam. 20. Big O notation: Do you remember what I said At the end off previous lecture? I said that these two time complexities are pretty much the same now. Obviously they are different. But as far as big O notation is concerned, these are the same. So what Big O notation iss. Well, do you think that this plus two it's important? Imagine that and is a 1,000,000,000. So you pretty much don't care whether you need to do a 1,000,000,000 operations or 1,000,000,000 plus two, right? So what Big O notation does is it kind of hides the unimportant and leaves the important, because if we ignore the unimportant, that means this plus two and times free, we get the important, and this is how we get big o notation from time complexity. So let's take a look at the definition F Off X is in the big o of G if, and only if there exists key and X zero, such as that for all X greater than or equal to eggs. Zero. The F off X is less or equal to k times G off X, so you can think of big off and as a big box that contains all the algorithm that have a linear time complexity. So, for example, this algorithm that takes an array and if these size of array is greater than 50 it returns true else, it returns false. Pretty simple, right? What will be the time complexity off this algorithm? You can pause the video and try to figure it out. So the precise time complexity would be to read because we need to check for length and either return true or return false. So what can we figure out from this? Well, it doesn't matter how big the input is. This algorithm would still have constant time complexity. And in big o notation, all the constant algorithms are in this class or box if you want, and it is the smallest box possible. You cannot get algorithm that is faster than big off one. Now, let's take a look. Get this algorithm. What bigger box it will fit into. Well, first of all, let me compute the actual time complexity, and then we can move on to big Oh, so we have your two operations before the first cycle. Then in the first cycle, we go from zero to and and what do we do Well, we check whether the number on index I a smaller or equal to 10. If it is we at this number to result variable. And then there's this inner cycle, and this one moves once again from zero to an, and it basically brings every number in array. Phil free to pause the video and computer D time complexity on your own. So I will start with the inner cycle. So initializing 20 that is one instruction. Then for each element, we check whether Jay is smaller det en, Then we increment J and brained element on index J. So this inner cycle will have time complexity off free and plus one. Okay, now let's take a look at the rest at D beginning there is the initialization off result variable, and also we initialize I 20 So let's right plus two than for each element. So end times I check whether the or a own index I is smaller than then. But I don't know whether this is true or not, right. It depends on what elements are in array. For example, if all the numbers in Ray are greater than 10 we need just one instruction, because this line will never happen. But if all the numbers are smaller than 10 we need free instructions because of the plus and assignment operation. So what do we do? Well, we need to count with the worst case scenario because we want to know the complexity off. Worst case. Okay, so we get free and plus n times the complexity off this four Roop and we computed the complexity of this inner loop before and it was free and plus one. And by multiplying it, we get the final time complexity and that it's free and squared plus four. And because by multiplying, we get n and we already have free end and plus two. This is the time complexity off this algorithm. So what is the big O complexity of this? We can get the big O complexity by just taking the biggest term. So in this case, it will be free and squared because if, for example and it's a 1,000,000,000 we get free times 1,000,000,000 times been in, and that is greater than four billion, right? So free and squared is the largest term. Now all we need to do is get rid of the constant, and we get our big bo complexity. So this algorithm have time, complexity off big O off and squared, and this approach works for every time. Complexity. For example, if I take the time complexity from previous case, the big O complexity will be the largest term from this expression, and that is just free and without d constant in front of it and that it's just end. So we get big O off Ed, and that is pretty much it for this video. If you have any questions, feel free to ask, and I will soon exam. 21. Comparing CODE: Well, hello, gas. And welcome to this lecture. In this lecture, we will compare all of the sorting algorithms that we implement. So if you, for example, I get them all in here, right? So there's a bubble sword, right? And they're all of them. So let's actually compare them to see which one is the actually faster Not by big o notation faster but in, like, actual example, faster. So let's do this. First of all, we need to define a function that will kind of 40. Quick sword merch. Sword Andy Quick sword Medin that only takes, say, include array and its kind of calls quick, sort and compute the from and to indexes. So it will be just cool like function And in here Let's right, Quick sword. And that's called is one like execute er like this And it will be It will take the array only we need that because when we will test them, we will just get generate only the your a. And then we will sort it by all of the all of these algorithms, right? So we know that. So we need so that every function takes only the array not any other arguments. So in here we will just Grady quick sword on the and put so a input. And the first from a zero. And the two is a and put that length minus one. Right, So like this. And we will define it for D merch short and quick. Sword median. So quick Sword met in will only call quick sort Madden and Murder Sword Well called merch Sword like this. So yeah, that's it. Right now what we need to define also. Well, we also would like some function that checks whether the you're a assorted correctly right ? If we have some buck in these algorithms, we can figure it out. So in here I'll just write Function dead will be called assorted and this function will return a Boolean. Well, first of all, Israel accepted array and it will return a Boolean value then will represent whether you're a assorted or not. So when do we when is dear? A sordid Well, when for each number it's true that the number behind it iss bigger right or are equal. So yeah, we don't just live through D Hall array except the last element and we'll increment I So we live for the whole array and in here we check. When did he element on Index I A smaller Dendy element on index I plus one like that. So basically the element behind it. And if it Well, actually, we need to check whether it is bigger, because if it is bigger, we know that the array is not sorted. So we just returned false like this. But if it is smaller weekend, just continue. And in here we will return true likeness. So, yeah, we need to put in here D minus one. Because in here we use plus one, right, So that we don't gonna go behind your A. We need the minus one. Okay, but this or dysfunction should work. So let's right now, define a few constants. 40 testing. So I'll just write var. And in here, let's ride the number off race. So number off race. So they will be just a number over race that we want to sort. So for example, 100 array and then was to find another variable. And in here, let's right elements for Harry. Right? So this will define how many elements in array we want, Right. So in each ray, we will have, like I had no 1000 elements. Let's see. Okay. And yeah, this will be the two constants that we will use for testing. And we will also need a array off the sorting algorithms, right, So that we can loop through them all. And we don't have to, like, necessarily write them out by hand. There will be a huge pain in the A. So we'll just put them into array and then we'll be We will call them from array. So, yeah, let's start it. So the first round will be babble, sort Dan. We'll do like selection. Sword often Eyes double sword, merch, sword So much. Start, execute er and also the quick sword execute er and also the quick sword Mehdi and execute er like this I forget about come in here and yes. So this will be the array off the algorithms off the sorting algorithms. I will just put a and of lining here so that you can see better. And yet So right now we need to live through these algorithms and test them. So far, let's say war and in here to find a K starting at zero, while k a smaller Dendy length off are sorting algorithms. So in here, Liz. Right length. We will increment k. So the a sorting algorithms on index K is one of these sorting algorithms, Right? So in here, let's define a variable called start, and it will be a time off off the stand. The start time, basically. So we will measure measure the algorithms, right? The how fast they are. So in here, we'll just write gates, get time like this, and this should return us a time. So in here, we'll test it. So we will sort number of race and each. Yeah, well, sort the number off Ray race like this. So let's ride war and let's say I starting at zero while I a smaller dandy number off a race like this and we will increment, I okay. And in here, what we need to do Well, we will create a new array. So let's go. Does want a input, and we will set it to, like, empty or a and in here we will fill it with a random numbers. So for a very abou let's say J equals zero while Jay is smaller, Dan. Elements for array. Okay, well, incremental, they so dead means for every element in disarray, we will set it to something. So a and put on index J sorry will be equal to, like, some random number. So meth, that's random. And, yeah, this but this random returns us a small number, right? So we need to do a meth floor so that it is in danger. But yet it's not necessarily bad. I will do that anyway, So we will have array off indie jurors, and I also multiplied by 100 so that we have a range right forms euro 200. So the array will be filled with numbers from 0 to 100 they will be indeed yours. Okay. Yes. So right now all we need to do is sort it. So the array sorting algorithms, likeness on index, gay writing here we have decayed to find. And we all started with D. All right, so in the year, a input. So we Saudi a input array using these sorting algorithms on index case of one of these and yeah, then all we need to do is check whether you're a it's actually sorted, right? So if is sorted the array, so if it is sorted, everything is okay. But if it is not sorted, so help with a explanation marking here. So if it is not sorted, we need to, like, let us know debt something when runs. So console that lock and algae is right in your error like this. Let's see. Something like Ray is not sorted. And we can also bring the array. So plus a infant like this. Okay, so dead. Well, that doesn't know if some of the algorithm is not working. And yeah, then only need to do now is at the end. We can define a variable called and so the ending time basically, And then we can just print out how much time it took. Okay, So in heroes, right, council that log and let's right. First of all, D index of the algorithm and then we can write like something like souk A some middle seconds. Right. So it will be just a and and minus from right, so and minus from time. And this will return us a time in milliseconds. So in here, our plus and in here, m s. And I'll put space in there so that you can see better. But I Yeah, this iss howdy algorithms should be this it so yeah, for well, test them on 100 erased, and each ray will have 1000 elements. So let's Rhonda's by is in control and a five and in Here's something went wrong. So what's that? Well, not from but start. Sorry. I'm confused from the all of the from indexes of her own quick sword. And Mercer Yeah, bad as you can see in here and work so and the first. So that means the bubble sort sorted in 275. But as you can see, the fourth Juan, which is the e quick sword, is much faster. Actually, then the merch sword, right? It's like four times faster. Almost. And the quick sort median does not kind of make ups and us any time. So it's barely better to pick the last number as our pivot, right? Not the madden off free. But let's ride, for example, 1000 race and each one will have only 10 moments. Okay, so is Ron distinct? Maybe I could put 10,000 like this so that you can see the difference right in here right now. The fastest. It's actually the optimal eyes. Double sword. Okay, so as you can see the second so which is optimized? Battle Sword is the fastest. It takes only 23 milliseconds. And then the quick sort is the 2nd 1 But we had just proved my point that even though the bubble sort should have, like, worst time, compact time complexity, right, it's big. Go off and squared and emerge, sir, is only end times again for, like, small inputs. The big connotation doesn't kind of matter too much because, as you can see, the bubble sort is actually faster for a raise that have only then elements. But right, if I switch it up So if I will sort only 10 arrays that have 10,000 elements and run this thing it make take some time. Hopefully it will be fast. Bad? Yeah. The bubble sort took free seconds, right? The selection sort waas quite faster. The optimized bubble sore didn't help so much. But as you can see the quick sore, it's only 59 minutes seconds. So it's like I know a 70 times faster. That's a huge difference, right? So you can play with the number of elements and number of race and find out which algorithm actually works. The best 40 input right? And that's about it for dis lecture. So if you have any questions, feel free to ask, and I'll see you next time. 22. Data structure: and computer science. A data structure is a particular way off organizing and storing data in a computer so that it can be accessed and modified efficiently and by efficiently, I'm infest. So you already know some ways of storing data. You know, erase maybe some list. But these ways are pretty inefficient. For example, if we want to find element in Ray, we need to go through every number and compare it. So we have time, complexity off big, go off. And and Dad is bad. In the next few lectures, I will show you how we can improve it. 23. Binary Search Tree: first data structure that we will talk about is binary search tree. This tree is made up from notes and edges. Since it is treat, it, have something called route root is just the note on top. Every note can have left and right child, but this is not a rule. Notes can also have only left or Onley, right Child or note can have no child's, for example, the right child off rude have no left child it have on Lee right child. The notes that have no child's are called leaves. Another word I will use its Saptari sub tree means every note in some part off this tree, for example, left sub tree off route are all of these notes and right sub tree off route means all of these notes. Another important thing about binary search trees is that in the left sub tree off, every node are smaller elements and on the right sub tree are bigger elements. So, for example, binary search tree can look like this. As you can see in the left sub tree of route, every number is smaller than 28 and in the right sub tree, every number is bigger Let me show you how you can insert. Let's say we want to insert two. We compare it to root and since it is smaller, we know debt. It has to be in its left sub tree. So we follow pointer to its left child and we do the same here. So we compared to and 10 and since it is smaller we go left Now we compared to and six to a smaller. So we go left. About six have no left child. But we can set its left child to to that way this tree will still be binary search tree. Let's at 30 we start from route and we are comparing number We want to add to note value If it is smeller with your left If it is bigger, we go right. We stop when we have no note to compare. Then we create new note with the value that we are adding. And we said it as a child off the no dead we last compared hope that makes sense leads Judas 30 is bigger than 28. So we go right 30 is smaller than 36. So we go left. But there is no note. So we said 30 as a left child off 36 we are done. Let me show you how the search works. Once again, we start from route. We compared the surge value to value of note. If it is smaller, we go left. If it is bigger, we go right. If it is equal, we found our element. We do this until we find our element, or until there is no child. When there is no child surged, value is not in the tree. Let's find 30. We started route and go right Then we go left and we found 30. Let's try to find eight. Once again, we started route and Geo left. Since eight is smaller than 10 we go left again. Eight is bigger than six. So we go right. But six doesn't have right child, so eight is not industry. Let's try to delete some notes. There are free cases that can happen. The simplest is that we want to delete a leaf note. We just find the note and deleted. We find it the same way as when we are searching. For example, let's delete 30. We searched 30 industry and find out that this note is a leave. The no debt compares 30. And as I said before, we can just delete it because after delish in, we still have small numbers and left sub tree and big ones in rights of tree off every note . Second case is that denote we want to delete have one child. So let's delete 14. We find 14 and as you can see it has on Lee Bright Child. This is also pretty simple. We just said the pointer from the node that we want to delete duty on Lee Child. In this example, we said the right child off, then to 18. The last case is that d no dead. Well, you want to delete, have to child's Then we have a choice. We can replace this note with the biggest number from left sub tree, or we can replace it with smallest number from writes up tree. But we are lazy programmers, so we just implement, let's say, biggest firm left sub tree. So let's say we want to delete 28 the route So in this case we replaced the 28th with 18. Now, for every note is true that in its left sub tree are smaller numbers and in its rights, up tree are bigger numbers, but sometimes can happen that the biggest number in left sub tree or smallest number in right sub tree have a child like in this example. But that is not a problem. We do the same. So we replace 28 with 18 and now we need to take care off that 18 missing. Okay. And since it f only one child, we do the same as when we deleted node with one child. So we said the right child off 10 to 12 and that is it. The time complexity of search, insertion and elation and average is big o of luck at because when we go to lefts of tree, we kind of get rid off all the notes and right sub tree and an average case. Both trees have pretty much same number of notes right on. The way to look at it is that we care about the height off our tree and the height off our tree is luck off and an average case. Okay. And that's pretty much it for this lecture. If you don't understand something, just ask me a question and I will see you next time 24. BSTInsertSearch: Well, hello, guys. Send welcome to this lecture and this lecture. We will implement the Byner search trees. So let's get started. First of all, as I set in the explanation video, the tree is made up from notes and edges. Right edges will be just a reference to some note. Right, But the note we need some kind of object to represent it. Okay, So let's to find a construct er for that object. So function, let's go at node and in year, what Every node will have well, every note at a value, right? So I just write Indeed your value then what? Also every note can have Well, it can have left or right child right? Or both. So left and right. So object left an object, right? Okay. And will basically said it as a properties off this note. So this value will be equal to even you and this dot left will be equal to left like this and this doesn't write will be equal to all right likeness. So this will represent our node. Now let's define de bine research tree so out zoos A variable like this sentence will be a object. So what a Byner searched 3/2. Well, it have root, right? So let's right in here. Property route and as a default, it is undefined because we don't have any values in these search in the search tree, right? So it will be under find. Then what? Also, what we also mean? Well, we need to be able to insert, so this will be a function, and this function will take some value, right? So devalued that we want to insert. And we also need to search and delete. But let's take care off the insert first. Okay? So what can happen when we are inserting? Well, first of all, we need to take care of the case when a route is undefined, right? So if this that route, it's undefined, We What do we do? Well, we just create a new note that were contained this value and said it is our route, right? And that's it. So this is pretty simple. So does that route will be equal to new node, and we passing there I value. Okay. So devalued. Did we want to insert now? You might think. And Wade Verity other to pyramid years. Well, we don't have to specify them. We just They will be just under find as a default. Right? So that's all right, Because the note the route grand route have no left or right child. So there is no left or this. If there is no left child, the left property will be undefined. Okay. Same for right. So does will work. And let's also, for example, return True, so that we know devalue was inserted correctly. Now, let's do D cases when the root is not under fight. So we have already some value in the in the tree, and we want to insert a new one. So what do we do while we trade through the tree? Right as the explanation video. So as if any variable and I'll just write old current node. So this is what beating? No, Dad, we are at okay. And from start, it will be route like this. And while the broker and node s equal to is not equal okay, not equal to undefined because we want these. We want the Oakland note to be undefined, right? Because when it is undefined, we know that we reach the place when we want to insert the I value. Right. So we need to create new note and inserted as a ocurre en node. Okay, I hope that makes sense. So So in this wild cycle, we go either left or right. So if the oh Quran node, Dad, value is smaller than the value that we want to answer, We need to go. Right. Okay. And how do we go? Right. Well, we just said the current node to the right child off green note. So, like this. Okay, this is basically this line. Does the going right in the exponential video okay, I hope that makes sense. And if the value well is right, also else, if out and else if the the okra node value IHS greater than the value that we want to insert, we go left, right. So statements, the explanation video, and yeah, And also, what can happen is that the value that we are inserting, it's already in the tree. And that means that we go into this else bridge because when something is not smaller and it is also not bigger, it's must be equal, right? So if it is already in the tree, we just returned false because we don't want to insert, like, multiple that use. Okay, so yeah, after days Weil cycle, we need to go. Can go back and find out the baron off the grand note. Right. So that's the kind of thing that we want to do in inside his wild cycle. Right? So what do you want to do? Well, we need to keep track off the parent of the Okrent note. Okay, Does that make sense? Because in the end, we will sending you note as a child off the Baron note. Right. So let's do that was to find a new variable and let's goalless. Oh, note before something like that. Okay. And from start, it will be undefined because we when we have when we are in the route, there's no note before, right? Bad Inside his wild cycle, we were always a d beginning. Said it, Sudi Oh, current node. So after days, well, cycle in the own owed before we have the Oh, the the note that was that its parent off the Oakland node. Right? Because when we jump out of this cycle, that means okra notice undefined. And that also means that this was undefined in the previous situation, right? Or this was undefined in the previous situation. So we want to go back to the point where this was still a node. Okay? And to do that, we simply refer to this own old before. So what we need to do now? Well, we have the only old before, so we just need to check whatever you should create new new note as a left child or as a right child. Right? So that is spread a simple We just do it like that. So if the own note before that value is greater than or smaller Dent e value like this, I will just create a new node and said it as a right child. Okay, because this value is greater. So let's do that. Oh, no. Before that right will be equal to new node. And this note will only contain the value that there will be no left or right child. Okay? And singles in here. So in here we write else if or we could be just writing else, right? Because in your we return, we automatically return, so it must be either greater. The value must be either greater or smaller. So yeah, Lizzie, just if so, sorry. It was do just else. And if we get to this branch, it means that it must be the left child. Okay, so I'll just copy paste it. And in he right left like this. And when we get in here, we can just return. True, because we know that the value us and started. So yeah, this is the insert function. Let's write also the search function, Okay? And then we contest it a bit. So search and it will be a function that that takes some value, right? So devalued that we don't assert. And inside dysfunction, we just define pretty much the same route as in here. Okay, so I Well, I want coffee based it. So let's defining new variable and gold is one currin node. Seems before and by default, we can set it to root. Okay. And then, while rude, well, while the current node is not undefined, so that means we still have notes to follow. We will just follow the pointers. Right? So we do the same stuff as before, So if all current known that value IHS smaller den the I value like this We g o right. Okay. So old Quran node will be equal to okra unknown that right? Like this and else if the okura node value iss greater than the value we go left. So statements in the explanation video Samos When we are inserting, we just go left bad right now it becomes interesting. Maybe a bit if the if we go into the else branch, that means the vanity off the Oakland node is equal to the I value. So that means we found the value so we can just return. True as a this value is in the tree. Yeah. Also, I forget about comma in here and yeah, and if we break out of this cycle So that means we found a leaf. So that means we cannot go anywhere else. The value cannot be in the tree. Rydzyk value is not in the tree, so we can just returned. False. Okay, so this is the search and the insert function. So let's test them a bit. So in here, let's define a variable, and it will be a ray. I'll just call it input like this, and I will insert to it like some numbers. So for I will be equal to sue zero. And, well, I smaller than 100 for example. So let's insert 100 numbers. I will insert a new, like, random numbers. So first of all, I will start the random number number. Okay, so into disarray. So it will be just math that random And in here we can multiply it also by 100 so that it's a number between zero and 100. And let's also around it so that we don't have their like a decimal point, and we don't want that. So right now we have a random number and you want to insert it into the tree. So yeah, I forget how it, Scully rBST and in the rewrite insert and we fastened there devalues So a input on index. I like this, and this will hopefully insert all the values in the array. So now what you can do is simply test whether day were inserted. So in here, we just get rid of this line because we already have the values that were inserted into in this array. And in here we just check whether they were inserted. So if search, we try to surge them. Okay? And if it is true, well, if it is false, that means it is not in the tree. So that means there's a problem somewhere I will just gone. So that Locke a error message so ever value isnot in the tree. And I'll just also add the value so that we can take a look like this and let's run this thing so control and five. And actually, if it rights, nothing, we are done. So Al, Al, just look in here something like guns, council lock, something like end. So did we know we successfully inserted and searched? And if I run this thing once again, it's this end. So that's cool. We successfully inserted a huge array of numbers, and we successfully found them. If you want, you can take a look at how the how the tree looks. So, for example, if I put a break point in here or somewhere in the search function, for example, like, right here and then hit the five if five key on my keyboard, I can take a look how D tree looks like. So if I hover over this this route I can see the left and right child. So left child is a no that have very 2026 the right child is no Did have value 45 then there is no love child from this note But it have rights half off 64. So yeah, you can test it a bit. You can see how the tree looks like You can even print it out bad. Yeah, that's it for this video. In the next video, we will do the deletion And yes. So if you have any questions, feel free to ask End at will soon, Next time. 25. BSTDelete: well, hell, guys. And welcome to this lecture and this lecture We will add delete method or function if you want. So let's get started. Let's define a delete. Well, the lead note, for example, Or value whatever you want. And in here, right function. So once again we accept the value that we want to delete. Right? So I value like this And let's also add the races. And right now what do you want to do? Well, first of all, we want to check whether there are any values in the tree. So if this dot route is undefined, we just returned false right, Because we cannot delete anything if there's no value, right, So like this. And then we need to check whether we want to delete the route. OK, so let's Judah. So if these this a route that value is equal, Sudi I value what do we need to do? Well, first of all, as I said in the explanation video, there are free cases that can happen. The 1st 1 is dead. The route is leave so it have no left nor right child. The 2nd 1 is that it has one child either left or either right. And the 3rd 1 is that it have both, child. So let's do it. So the 1st 1 is the most simply around. So if this route left is equal to undefined and this route Reid is equal to undefined. So that means it is a leaf. It have no child. We simplest set this route to undefined because we just read it. This this note, right? We need to delete the root note. And that's the only know that we have in the trees. So yeah, meaning to delete it this way. And the second case is that it has either left or right child. OK, so was right. Deaths route, for example, left iss under fight. So in this case, it have only right child. So what do we do? Well, as in the explanation video, we said the this route to the right child right through the only child that it half. So let's do that. This route will be set to this route. That right? Okay, so we said the route to write child and that way we kind of get rid off the route before because there there is no reference to it. Okay, so yeah, let's do to sing 40 right, child. So in this case, the route have only left child. So this and that ruled that right? It's equal to under find. Yeah. And how do I know that it has only left child? Because in here I check only that the right child is undefined. Well, I know that the left child must It's not equal to undefined, because if it were under find this condition would take place. Right? Okay. I hold any sense and yeah, So let's set the brutes Sudi left child. Okay, so this route left like this. So these are these simple cases that can happen, OK? And right now we need to deal with the kind of worst case. Okay, so that is that route. Have both left and right, child. And as I said in the explanation video, we kind of big the biggest element from left sub tree. OK, so l said this that rude to a new node new node that will contain well, the value, so I will define a function for it. So it will be something like find biggest in the left. Okay. And it will be a function that takes Oh, node. Okay. And it will return as the value, right? So only the value, the indigent value and, ah, in here were I d find biggest and laugh So that will return us the value. And we also need to said to There's no D left and right child. Right? So the left child and the right child stays the same. We only want to delete the route. So what do we do? Well, we just as the reference to them. So in Hero BD left child, and then we will best the right child. And we said this note as a rude bring a simple right. So, yeah, that's the case when they know that we want to delete is rude right now let's take care off the like average case where the where the notice Somewhere in the tree. And we don't know where. So we need to find it and then delete it. So we do the same trick as in the search, so I will just coffee based it. Well, not search insert. Sorry, Al. Just coffee based it because we still need the note above. Okay, so this will find as the note above off the know that we want to the lead. Okay, so if I just based it in here underneath I have the owner before too undefined. Then I said the current No, too rude. And while well I cannot luv while under find I can move while the value right So while the value is not equal to I value like this when in the sequel we know that the Okura note is the no dead we you want to delete, right? So wow, it is not equal We just move the owner before So we said the owner before and then we check right? So sing way in here So if it is smaller Rego right if it is bigger if it is smaller we go left If it is bigger we go right like this and else we just returned False Because we cannot delete some Well, not we don't return falls because else we found the elements so we don't return falls We want to delete it, okay? And yeah not a thing we wanted we want to do is check whether it is undefined So if the own owed before No. Oh, Krenn notes. Sorry. So after we set it to right or left child, there's a possibility that the know that we devalue that we want to The late is not in the tree. Right? And if it is not in the tree, the value will be under Find one off one of the the value of the current node will be under . Fine. OK, so if it is undefined like this, we want to return false. Because we cannot delete something that is not in the tree. So, like this. Okay, I hope to make sense. So after this cycle we have in the Oakland note, we know. Did we want to delete and in the O note before we have the parent off this note and we know that the owner before is not undefined because we know that the route is not the know that we want to delete, right? That's why we Canada, all of these stuff in here. Okay? Yeah, And we also need to return true in here. So if if one of the cases happens, we need to return true so that we don't go into this wild cycle. Okay, Grade. So right now, what we want to do. Well, we need to kick the care off all of the cases that can happen. So in here we just ride the first case. So if own Corin Node that left it's undefined and the O Corin node Dad's right, it's undefined. What do we do? Well, we just set the We just don't get the node right. It's a leaf. So we delete the reference in its parent, and the parent is stored in the owner before variable. So that's cool. So in here we right. If the owner old before we still need to figure out whether the Okura note is a left or right child off the old note before, right, hope that makes sense. So we simply do that by checking the values. So if the on load before that value is smaller than we can write, either okra and no doubt value or I value because they are the same right. We wouldn't jump out of this while cycle if they if they were different. So if it is smaller, so if the value is bigger, we need to like said the right child, too undefined. Okay, so Oh! Oh, no. Before Seoul, right child of the Baron will be equal to undefined. So that way we will get rid off the O Corin note. Right? And in here, we can just write else. Because if it is nuts, not bigger, it must be smaller. Right? So in who? Angel said it to the left child. Okay, like this, so does the first case. Right now, let's take care off the second case. So, Algaze right in here Else if And else if the okura node that left this undefined. Okay, So that means one off the child is still their rights in this case, the right child iss dino that we want to delete half right, child. Okay, I hope makes sense. So same Indy. The same as the explanation video says we just said the right child off. These known as A is a like successor of Dino that we want to delete. Okay, so let's do that once again, we need to check where we want to set the right child. So I'll just copy Basit. Hope that's ok. And in year, I simply right. Okra node. That right? And in here, same thing. So Right now, we are not setting the reference in the parent to under fun because we still have the value in the right child. So we are setting into the right child. OK, so that makes sense, right? We don't lose any value and in your lives, right? Pretty much the same thing for the left child. So, Al, just copy based all of the code in here so that this video is faster. So if the right child is undefined, that means the O Corin node have only left child, we want to check the value. And in here we want to set. We won't said the left child like this because the right child, this undefined, okay? And the Yeah, it's going to add this. And the last case is that we have both child's. Okay, so the no did we want to delete have both child, and we can simply delete it. So once again, I'll just copy based this thing. And in here we are not setting Itsuki left child. But we are finding the successor. So in this case, the biggest value from left sub tree. And we said it as a new kind of node, Right? As as the reference in this parent. Okay, so, you know, and in here I will pass this dad find biggest in left sub tree off the current note. Right? So old car endo like this and the left child will be the left child off the current node. Right? So the child stays the same, so left, and the right child will be right. So current node, I'll just put it on different lines. Okay? Like this. Oh, current known that left and in here will be okura note dot Right. Okay. So the child's will stay the same about the value will be different. I forgot Like this and same thing in here, right? We don't want to change anything. This the difference in here is only in the reference in the parent. Right? So this thing stays the same like this, I'll just dab it out so that it looks kind better. Okay, so that's it that we also need to return. True, because if we get through one off this case, we know that the value wasin the tree, so return true and we deleted it. So let's ride the fine biggest and left Okay, so I'll just go up to the function. Here it is. And how do we find the biggest note in the left sub tree? Well, first of all, we need to go to the left sub tree. So we grabbed the left child of Dino that we best into dysfunction. Okay. And that reminds me something I forget in here to past the rude. Okay, this that rude? Okay, so change this, otherwise it wouldn't work, right. This will be undefined. And we get an error in here, so I'll just check quickly. Yeah, these are all right. So yes, sorry about it. So we get the left child. So that way we go to the left sub tree and in here, we know that the most right child must be the biggest right, because in the rights of tree are always the bigger numbers. So once the right right child off some note is undefined. We know that the note is the biggest from left sub tree. OK, so let's do that. So let's to find a new variable is the Okura node and I'll set it to o note like this. And let's also defined the well Yeah, let's also define the owner before because we still need the the reference in the parents so that we can change it, right? So Oh, no, before Same trick as before. And it will be the Actually, it will be the O note in this case. And the Oakland node will be Oh, note that left. So this means the okra note. It's the left sub tree. Okay. And what do you want to do now? Well, one extreme case that can happen is that there is no right child. Okay, so the biggest number from left sub tree is just the left child off denoted we want to delete, right, because there would be no child off in the right sub tree off this note. So we need to take care of the problems. So if the okra node that ride, it's undefined like this, we What do we do? Well, we know that this node is the is the biggest from life tough tree. So you're a turned the value of this note, but we also need to change the reference. So the left child off this node will be said as a left child of the node before. Okay, so Oh, no, before that left will be equal to old Quran node. That left Because we need to delete the value that we are passing. Okay, so yeah, Right now we just return the oh, crane node that value like this. So dead was the extreme case. Right now we need to take take care of the average case. So that means there at least one. All right, child. So while the okra node that's right is not undefined, we just go right. Okay, so we go right. So oh, no, before will be equal to oh, Krenn node And the Oakland node will be equal to O Corin Node. Dad's ride. We are not checking any values. Anything in here, we just simply go right. And we also said the no before. Right. So we just go like this. And after this cycle, we know Dad and the owner before we have the value, we have the successor. Okay, so yeah, we need to check what we need to check. Well, no, no. In the owner before we don't have these successor. If if something is straight in the okra unknown, we have the successor because the right child is undefined. Okay, so the Oakland note is not undefined. Okay, so we need to check the value of the okra node. So if the Oakland node dad left, it's undefined. So that means the Oakland notice leave. We just simply said the reference in the on load before, so Oh, no, before Oh, node before like this. And we know that it's a right child. So, like this. And we said it too undefined. So that way we delete the okura node and reaches returned the value. Okay, so return okra and no dad value like this. And yet another thing that can happen is that there is a left child, but that's not a big of a problem. We just said it instead of undefined. We set it to the left child, right? So Oh, Grant Node That left And that's it. That's it. That's how we find the successor. And, yeah, I think this should work, So yeah, let me just write a function. Well, not a function, but some cycle that will test it. So in here we will delete some values. OK, so for where you are I equal to zero Let's delete a 50 values from the tree. OK? Like this And in what do you want to do? Well, in the a m poor, we have some baddies, right? So let's said the well said the 1st 50 values to undefined. Okay, well, sir, let's delete the 1st 50 values. And an in year we will search only from 50 behind. Well, maybe from 0 to 50 and then chick, because it should not find the element at the 0 to 50. So, yeah, let's do that. So BSD that delete that you and we will delete this value, and we can also check whether the lead was successful. So if it is not successful, weekend just burned out some error message because it should always be successful because we just inserted this values. Okay, so in here, I would write, bring error, cannot delete this value. So a and booth on Index, I like this. Yeah, I forgot about the bus. So this, But so that means we don't leave the 1st 50 values, and then we will surgeon. So if the well, first of all, let's just change these two cycles. So in here I will just defined two cycles. That will be easier. So from 0 to 50 we'll check whether devalue its not in the tree. So dead means if it returns true. So that means if we found the value, we didn't believe that successfully. Okay, so I'll just write error. Very value. It's still in the tree. Okay, but in here we go from 50 to 100 and check whether the value is in the treat because we don't want to. Dili. We deleted only the 1st 50 values. Okay, Hope that makes sense. So, Al, just save it and run this using control and f five and yeah, in here, it brings some errors. So first of all, it writes, like cannot delete some values, and then it prints value is not in the tree. Okay, so Al just spas video. And in the next lecture, I will fix all of these problems. 26. BST Fix: Well, hello, gas. And welcome to this lecture. In the previous lecture, we kind of figure out that something is it's not working. So in this lecture, I will show you how to fix this. So as you can see, it's a skin on. Delete some numbers. Okay? So in order to figure out what went wrong, what I did Waas find out. So dead means we end out ended up in this condition, right? So I thought that the problem was in the delete value function bad. In order to check that, I can just write console deadlock and in here I will look out whether the value is actually in the tree because I believe that the search function, as you can see in in In here, it must be wrote like correctly. There's there's not not much that can go wrong. And I double checked it. And I am quite sure that this works. The search function works. So in order to figure out what went wrong, I checked whether this might be my not be a problem, right? Did the lead value might not be proud of. So what I did is that I checked better devalue. It's actually in the tree. So I searched this value. Okay, like this. And so this will look out. The weather devalues in the trees, so if it is false, the value is not in the tree. And if it is true, the value isn't a tree. So was just control and a five under stink. And if I move it up, as you can see, it's always false, false, false, false, false, false fulfils. So that means that there's no there's no problem in the read van function whatsoever. The problem isn't in the search function, either. The problem is any insert function. So I went up and once again double checked whether I'm doing something wrong in here and I figure out that I'm not the d Gold is correct. So then I kind of thought, Well, if the value is not in the tree, how come this not be? How can devalue cannot be in the tree. And then I figure out that I generate the random numbers. So that means that the there is a possibility that some numbers will be generated Even though they are run them, they will be the same. Okay, and we cannot insert same values into the tree. So that means we in here. We inserted same values, but the 2nd 1 was never inserted. And then when we deleted these values, the 1st 1 was successfully dilated. But when we reached the 2nd 1 in the array, the value was not a tree. Right? So that means there was this this error. So if I get rid of this this thing in here and in here, I need to check so that we don't insert like, double valleys. So the same values again. And how do I check it? Well, I know that this function returns false when the value is already in the tree, right? So I can do something like this. So in here, right, While it's not true that we inserted So that means we didn't insert the number and didn't The number must be the same as well. The that means the number is already in the tree. We just said the a input to new random number. Okay. And we kind of Lupin here while we find don't find any number that will match this. And since there's 100 numbers, there will be a number, so eventually we will find the number. Okay. So, yeah, let's run distinct and see whether this works now. And as you can see, it wrote only end. So I didn't diss lock. So that means all of these functions are correctly and diviner search tree works just fine . So I'm story about him steak I made in here and yeah, so that's pretty much it for this video. If you have any questions, feel free to ask. 27. Avl Tree: The problem with beina research tree is that it can be unbalanced and that makes the time complexity. Bad. Aviall Tree solves this problem. Aviall tree is same as binary search tree, so it have root on. Let's that off each note are smaller elements on the right side, bigger elements but every note as something called balance factor. It is just difference between the height off lefts of tree and height off right sub tree, where hide ISS number of notes to most further leave. So, for example, if we count the balance factor of route, we count the number of notes two for just leave in left sub tree and then do the same for rights of tree, so balance is equal to one. Let's try this again For the left child of rude, we count the number of notes suffered as leave in lefts of tree and then do the same for rights up tree and balance is equal to minus one. Yes, balance can be negative. The important thing is that balance have to be bigger. Den minus two and smaller den to. But sometimes when we add or delete note, tree becomes unbalanced. For example, If I delete 48 the balance factor of rude will be, too. So we need some to to renew D balance. And these tools are called rotations, so we have basic left and dried rotation. When we do the left rotation, you move the duck note to a place where it's left child should be, and the other two notes guilt to a place where their parent used to be. Basically, the same thing happens with Reid rotation except D Tub Note moves to its right child. These are D simply, er, rotations, which takes place when the balance off top note and it's child node are both negative or both positive. But when these balances have different science, double rotation takes place. As you can see in this example, DEET up note. Have balance off minus two, but the note under have balance off one. So we apply right rotation on second and third note that will result into this, and we will solve this by simple left rotation. And the last rotation takes place when the top note have balance of two and denote under have balance off minus one. This rotation is gold. L R. Left right. So first we rotate to and free to left. Get this and apply right rotation. I skipped over the cases where these notes have child and the left rotation. It's pretty simple. We just take the left child off to and said it as right child off one. Every other sub tree stays the same. Pretty much the same thing happens with Reid rotation. Only now we are talking about the right child off to, and we said it as a left child of water. Now let's look at the double rotation as before. When we do left ride rotation, we first rotate note to and free. And since it is just simple left rotation, the be sub tree will become the right child off No to and after Dad, we have Onley simple right rotation to do and I already show you before out. It works the right left rotation as the same, just in different directions, so we rotate to and free to write. In this case, right sub tree off free becomes left child of No. Two after days rotation only need to do is apply left rotations and I already show you how to do that. So these are all rotations that we can do in order to make the tree balanced. And the effect that the tree is balanced means that the time complexity off these operations are look and so in. In worst case, right? Not the average case, as in binary search tree. But in worst case, because the tree is balance. Okay. And another thing I skipped over before is that the search works exactly the same as in Byner surgery. And the insertion works also exactly the same as in Byner Search Tree. Only after we inserting note, we also need to take care of the balance factor. But I will talk more about that in the implementation videos. So yeah, that is pretty much it for dis lecture. If you have any questions, feel free to ask and I will soon exam. 28. AvlDeletion: Okay. The leading in a VL tree is similar to deleting in binary search tree. The difference is that after deletion in a bl we update bounce factor from dilated note to root let me show you how dead works. Let's daily 23. From this street we find 20 free deleted And since it have left and right child, we replace it with biggest number from left sub tree in this case 18 and move 17 to where 18 used to be. Now we update balance factors balance off 17 0 bounds of 15 It's also zero balance of 18 is zero and same goes for route. Let's dilly to you find two and since it has no child, we just deleted. And now we also need to update d bounce factors balance off four is minus two and since balance off seven is one we do right left rotation after days, rotation balance off. These free notes will be equal to zero that we still have to update balance of route which will be now equal to minus one. So to sum things up, when the leading we find, you know that we want to delete, then we delete it. Same way s in buying a research free. Then we update bounce factors and we are updating from no dead. We delete all the way up to rude. And if balance of some note ISS managed to or two, we have rotations to take care of that and Dad is pretty much it. If you have any questions, feel free to ask and I'll soon exam. 29. AvlInsertion: with a VL tree. We are inserting numbers same way as we Byner Tree. But after inserting, we have to re compute balance. Factor off every note in Beth from inserted note to root When bounce factor is equal to two ar minus two, we use corresponding rotation so let's add to as I said before, we are inserting same way as in Venera Tree. So we compare inserted value to notes value. If it is smaller, we go left. If it is bigger, we go right after inserting, we re calculate bounces off all the notes dead for you. Is it it? Balance off to will obviously be zero balance of six s one because it has only left child balance off 10 0 and balance of roots states one. Let's add 44 will end up as an right child off to and since it is leave, the balance factor will be equal to zero. Let's re compute other balance factors. Balance of two will be mine is one bounds of six will be too and we stop right here since to have negative balance factor and six positive, we do left right rotation and after Diz rotation the bounce factor off D's will become zero . Let's insert eight. We do the same as before and end up with eight as a right child off. Six. Let's re compute bounce factors. Six. We'll have balance off mines. One four we'll have balance of mine is one. Then we'll have balance off. One and 28 will have balanced off to since 28 10 have both positive balance factors. We do right rotation and get this. So we are adding the same way as in binary trees. After adding the value, we re compute balance factors off all the notes that we visited. If some balance Fechter is equal to two or minus suit, we do corresponding rotation and Dad, it's pretty much it. If you have any questions, feel free to ask, and I'll see you next time. 30. AVLtree1 Node: Well, hello, guys. Send welcome to this lecture. In this lecture, we will start implementing the Aviall Trees. So Well, let's get started. First of all, I copy and paste the part of the Byner searched everywhere. We just gonna test it, so you should do the same thing. And yeah, So let's start by defining the node off Aviall tree because the note off in a VL tree is a bit different. Andy, note in Byner Search Tree. Okay, so let's do this simply write function, node. And in here we passed the value. Then we best a parent. I will get to it a bit later. And then we passed the left and right child. So what is the parent? This the second argument? Well, parent is just the note about So why are we adding this Well? Do you remember in the binary search tree that we indeed, when we are inserting or the leading we need to keep track off the note before, right? We have the variable own owed before, and we kept track of the only old before, and in order to make tea Aviall tree a bit simply, er we are adding the old parent as a property to a VL tree node. Okay, so that we don't need to keep track off the note before we will just have it as a property off the note. Okay, so that will hopefully make things a bit simpler. So in here we will just said the value to I value and same 40 baron so barren will be opened. The old the left will be equal to go left like this and deed right will be equal to Oh, right like this. So yeah, that's pretty much it If this were binary search tree But this is Aviall tree. So the node has a bit thing a bit more right and have a method For example, a method debt computes the balance factor. Okay, so let's define so this depth get balance will be equal to function. Dad doesn't take any arguments. Why would it? And it will return us the the result off basically the height of the well, basically the balance factor, right? So if Derris d if there is left child and right child so if this left is not equal to under find and this right is also not equal to undefined We simply return the height off left sub tree miners the height of rights up tree Ok, same as statements in the explanation video. So return the this left duck Get height minus this right that yet hide like this and the get Hyde will be a method over the note that we will define later on. Ok, and let's take care of the other cases. So, for example, if the left is not undefined, we need to return. What do we need to return? Well, there's a left sub tree so we just returned the height of left sub tree. Right? So this this death left dad get Hi it. And we know that the rights of tree that there is no right sub tree because if there were rights of tree, we would end up in this condition. Right? Okay, so let's do the same for the rights of trees. So if this dot reid is not equal to under find on, uh, find like this. Ah, I will return the height off left sub tree. In this case it is zero minus the height of rights up tree. So this right that get hide Same as in the explanation video. We are just writing the explanation into the cold. Okay, that's all that we are doing. No magic. So else if there is no left nor right child, we just returned. True that story return zero. Because there's, like, zero. The balance vector is zero. Okay, so let's the find you get hide function. So this that get hide will be equal to a function that tips no arguments, and this function will be recursive. Okay, So what do we need to write? Well, it will be kind of equal to this one. So, Al, just copy based it to make things a bit more fast. So what is d hide? Well, if it have left and right, child, the height is one plus the maximum. So meth max. Oh, the height of the left child and off the right. Chad. Okay. Does it make sense? It should. So this that left that get height and this that right that get hide. Okay. So if there are two childs so we compute the height is a one plus the maximum from the height off left or right, child. Okay. If there's only the left child we compute. The result is a one plus the height of left child. And if there's only right child, we computed same way. So one plus right child. And if there is no child, the height is one. Okay, Because they're still we still computing know that we are currently in Okay, I have to make sense. So another thing that we want to do have something to do with the with the parent. Okay, we have the additional property car called parent, and we need to define a function that will set this note as a parent to another note and will then use the function to set the parent property off other notes when we are setting the left or right child. Okay, so let's do that. Simply write this. And in here we will write this sign that will kind of tell the user that this is a private method and he shouldn't call it. Okay, So I'm not sure what you are familiar with it, but that's how you kind of defined private function in javascript. Okay, so this function will be called set s parent and it will accept one argument. So d child object and what it will do Well, it will check whether the child this child is not equal to undefined. If it is equal to under find, there's no point offsetting. It's Baron Dried. We would get error message. So if it is not undefined, we said the Baron. So, old child, that parent will be equal to this. So basically this note. Okay, great. We will use this function in these said let and said Right. Okay, so let's define these. So this and set left this. This will be also a function that accepts the left child. So all left and what it will do. Well, first of all, it will use the set as barren function, and it will set This node is a parents too. The old left. Because when we are setting the left child, we know that the left child should have this note as a parent, right? And so that we don't necessarily have to think about it when we are doing the rotations and stuff like that, we just kind of simplify it in here. OK, so this that left will be equal to your left. Okay. And another pretty much the same thing for the right. Okay, So set right. Will the equal to function that accepts the Oh, right. And in here we will said this as a parent to all right. And we also set this that right to Oh, right. Great. So debts all 40 Aviall tree Note. As you can see, it's kind of more complicated than the banner search tree node, because the binary search tree node was just a node having a few properties. But this one also have a methods and they are not so easy to understand, right? Especially this Get height. You need to understand Ryker Shin in order to understand the get height function. So if you have problem with that, feel free to contact me, okay? And yeah, that's pretty much it for this video. If you have any questions, feel free to ask and I will see you next time 31. AVLtree2Insert: Well, hello, guys. Send welcome to this lecture and his lecture. We will start creating the A V l. Glass and yeah, that's the Let's get started. So right function. And in here, a VL like this and into Alex had no arguments. Rivaled it, and it will have a property cold route that will be set to under find as a default. Then it will have the inserts search tenderly. So let's start by insert. So it will be a function that accepts the high value. And in here, we still need to check whether the route is undefined. Okay, so we need to check whether there are any values in the tree. Okay, so let's do that. If this that rude is equal to undefined, we just creating you knowed said it as our route and then return true hope that makes sense . So this dad route will be set as a new no, Dad, we will pass their I value right as a as a only value. Other properties will be undefined. Okay. And then we will just return. So, like this. Okay, if the route is defined, if there is at least one child at least one node. We do this so we cycle fruity Aviall tree. So said the old car end Very able to this that route And in here we will go while and let's actually do it this way, while true. So this would mean an infinite cycle. But we will break out of it in some cases. Okay, so So while true will psycho and check heredity ocurre end whether we should go left or right. Okay. So oh, current dad value It's smaller den this more than I value like this. If it is, we need to check whether the ocurre en Well, if it is smaller, we go right. That should make sense already because of the minor surgery, Right? Bad. When we go right, we need to check whether right? It's undefined. So if right is not equal to undefined, we are good. We just said the ocurre end as a ocurre end that right? Simple as that. Oh bar. If the right is undefined, that means we can insert right here. So we just said the current ocurre end that said right like this and we will set a new node and that will have the I value. Okay? And we can also pass in there D ocurre end. But since we are setting right, it it will be The Oakland will be add as a parent Sudi, you note. Okay, so we don't necessarily have to put it there. And if we go in there, we break out. So that means we successfully inserted the value and you want to break out of this infinite cycle. Okay, Another case that can happen is this else if and basically the value will be bigger than sorry Bigger Dendy I value so dead means we need to go left. Okay, so we do the same thing as in here, So we check better d left. There's not equal to undefined. If it is not. We just said the ocurre end as a left child of it. Okay, So current left. Basically, we followed the pointer, as in the explanation and Samos in the binary search tree. And else so did means if left, it's undefined. We set the right job. Buf child. Sorry. So ocurre end dot said left to said left to mu node. And this note node will have the I value. Okay. Other properties will be under find the parent will be said by this. Said left. Okay, great. So we also need to break out of this cycle like this, and yeah, we also need to define the else so else. If the devalue is already in the tree, we return false like this. Same as in the banner, sir. Street. Only this time after this wild cycle, we need to re balance the tree. So this re balance. And do you know that we are inserting, so oh, current likeness and yeah, we can then return True yet, So that's cool. That's the insert function. Pretty much road in here. And let's also define the search function. So D search is quite simple. Well, actually, it's it's It's exactly the same as in vinyl research to you. Okay. So, as a practice, you can write it yourself, simply pause the video and try to do it on your own. You can check back with me to see that you did it right about There's nothing complicated about it. So yeah, just create a new variable ical current, and I'll set its route. And while the oh, current is not equal to undefined, I followed the pointer. So if fork or end Dad, that you a smaller dent, I value I will set it two Able said the old grand to its left child. Well, yet to his right, John. Sorry. A trend that's right. And else if the O Corin Value IHS greater than I value so that means it must be the right child. Okay, the sorry in the left sub tree. So we just follow the left pointer. Okay, So ocurre end will be equal to ocurre end that left like this. And if we get to the else branch, the basically we found yalman. OK, so we just return true like this. And at the end, if we get to a notice undefined, we return false like this and nothing that I want to mention is why am I writing these conditions in this border? Because somebody might want to road. Like if the okra and value is equal two I've value and then go like else if this thing and else of this thing Well, the thing about how computer evaluates these things, this is like just a tiny thing, but it can save some time. Is that the computer evaluates this by looking at the first condition, the first F condition. And if it is true, it evaluates this gold and he doesn't even kind of considered this code. It just jumps over. And the probability that the value will be smaller than the eye value is much bigger than the probability that devalue will be equal, right? So dead way we can going to save us a bit of time. And yes, so that's the only reason. But it's just a, like extremely small thing, right? So, yeah, that might be just good thing to know, maybe something interesting. But yet, so there's the surge world. That's the insert world. So if you have any questions, feel free to ask in. I will see you next time. 32. AVLtree 3 Delete: Well, hello, guys. And welcome to this lecture. In this lecture, we will write the delete function. So let's get started simply right in here this dub delete and it'll be a function that will look pretty much same as thes search. So I will just copy and paste this like this. And the only thing that we want to change is that right now, when we find a note, we want to delete it. So this and in your allergies, right? Delete node and I'll Basson drd notes. So old current like this And that's the only kind of change that we did. So it's it kind of makes sense, right? Is in the explanation. We we always finding old that we want to delete, and then we delete it. Okay, so this is the part when we find a note and this is the function where we deleted. Okay, Doesn't make sense. I think it does. So let's right the part where we deleted. So this that daily note we'll be once again a function that except the note that we want to do it. And in here dirty free cases that can happen. So case one is dead node is a leaf. So if the note is, how do we know that notice a leaf. Well, it have no left nor right child. So if no Oh node that left is equal to under find and oh, node dot Right, It's also equal to undefined. If they are both true, that means there are no chap. That means there are no child's and we can just set it. So yeah, we can We also need to check whether we are do dealing with a route. OK, so if o node IHS not equal to root So this route weekend simple set it. So we just said the baron to a variable. So oh, parent will be equal to oh no doubt Baron like this. And then we will check the values. So if the old parent value IHS smaller dandy own node value like this, that means we have the Baron note and the note under Andy Note ISS. Because it's bigger. It's in the right is it's the right child. So all we need to do in order to the lead the note is to set the right child off parent to under find. Okay, so old parent. That set right? All right, like this Too undefined. And in here we can write else. Because if it is not right, child and must be left child, right? So I'll just copy based it and change the right to left like this. And there should be Vic l likeness. So, yeah, that's the case. Where d the note is in the somewhere in the tree. It's not the root. And we also need to re balance. So there's that rebalance, and we re balance deep parents. So old parent like this? No. Okay, like this. And if the note ISS route So that means we go to this else branch. We simply set the the dis Route two undefined that way with the lady note. And since it has no left, no right, child weekend said Hebrew too undefined. Okay. And we don't necessarily We don't need to re balance anything because it's just it's just that how can a tree with no notes can be unbalanced? Right, So in here, we can just return. Okay, let's go to the case to so case to means that No, I have one child. OK, so if the note left is equal to undefined. So did means Derris only right child. So in here should be Oh, node, I believe. Yeah, it should be Onoda. So if it have on Lee, right, child, we once against set check whether d oh, node IHS this equal Too rude. Well, not equal to that will be better not equal to this that route. So if it is somewhere in the tree we just said the pope arond same stuff as before, so Oh, no parent. And in he recheck the value of the parents. So for parent don't value if it is smaller than the own old own note that you we said the right child off parent too. The left? Well, no to the right child of note because left child this under find. Okay, so let's do it so oh, barons, no doubt. Right, child? Well said right to the owner. Is that right? Like this cool in here is the else branch And in here we are setting the left child, so oh, parent, because the value must be smaller. Ok, so parents set left to the O node That right like this Because the left child is undefined . Cool. So in here, we need to take care once again off the case where the where the note is a is a root. So if the notice a rude we simply right D note. Right, Baron. And we said it too. Undefined. Dead meat. Sorry. Oh, no. What's right, parent? And we said it too undefined because the right child will become the root and the rude have no kind of note above because it's a route. So the parent is undefined. Okay? And we also said this route to oh, node, that right like this So simple is that and in here, which is re balance the trees so key this this that rebalance. And we are re balancing from the o node Done right. Okay, like this and we once again return. So right now, let's take care of the out of barred. So in year, let's write else, and I'll just base that. So if the right child is undefined, we check whether d oh, no does the route. Otherwise we get the Baron. And in here we said the left in here. We said the left because the right child is undefined and the left child cannot be undefined because otherwise you would end up in this first condition. I hope that makes sense. It should make sense after the binary search tree. Because what we are doing here is basically a Byner search tree. OK? And in here we said the left parents too undefined. And we said the left as a new route. And in here we re balance d left. Cool. Cool. So right now we need to take care of the third case, the kind of worst case to implement, as I call it. But yeah, it just code. So if the note half both Childs So if you know what have both child's, we don't necessarily have to ride. Well, we need to ride because yeah, so let's write it. If this dot left is not equal to undefined and and this cannot write today is dead, right, IHS also not equal to undefined like this. So right now what do you want to do? Well, we will create the successor so like this and it will be a no dead. We will get from the biggest, so I will just write a function later on. But it will be the biggest from left sub tree. Okay, Like this. And yeah, we also need to passing their denote. So from the left sub tree off this note, and yet that's about it. So right now we have the successor, and we just said the left and right child. OK, so successor doubts set left. So this will be just a note. And the owner old dad left king. And we also said the right so set right, and then will be once again the owner old. That's right. Okay, so once again, we keep the child's We only change the value in there. Okay, Cool. Now what we need to do. Well, we said the Baron. So by all parent and we said it too. Oh, known. Oh, no, Dad. Parent So to the current parent. And we also checked whether this is a route. So if node is not equal to this, that route and I once again forget about e o oh node likeness. And if Onoda is not rude, we once again check the value and then said the right or left. So I'll just copy based it in order to safe sometime. And we said it to not own old left back to these successor? No, Kenny. Same in here. Successor. Great. Now let's also define the else branch where we just if even the note have no parent. So it is this route. OK, so Al just go successful and said the parent Teoh undefined, right? Because it will be the new route. And this that route not random but route will be set to successor like this and we will re balance it. So on this that re balance and will be as the successor in there. Great, great, great! Great. So right now we can either ready Get down, get biggest from lots of tree. But I will leave it to the next lecture. So great If you have any questions, feel free to ask and I will see you next time. 33. AVL Tree 4 Rotations: Well, hello, guys. And welcome to this lecture. In this lecture, we will write d get biggest from left sub tree. So let's get Let's get into it. And I'll just write this that get biggest from left sub tree and it will be a function. Dad will accept a note who note and wrong. That was wrong. That was Staple another table and it will return the note. It will not return just a value. It will return the actual node. Okay, so let's define it. First of all, let's call de very about and however you want to call it, I'll just call it result and it will be a left child off new off note. Right, Because we need to go to left sub tree and then in the left sub tree we go right, right, right. As long as we can. And ones right, it's undefined. We return it right, But we need to first take care of the problem if there is no right. So if result that right IHS undefined. So that means we have problem right away and once get a roadie. Oh, my God. Kindelan! Right. So yeah, we got a problem right ones against. So there is no right child. When did happen? We just said the O node d left so said left as a result result Dad left Sodi left child of a result means this one will be set as a left child off the note. Okay, that way we get rid off the off the successor. Okay, great. And we will also return the result Still return result like this great right now is get into the wild cycle. So if we go if we get to this point, that means there is a least one right child so we can do it while resolved. That right is not equal to undefined. We go right so result will be equal to result that right grid after the cycle we found DBS number and we got it in the result. So all we need to do is chick said the left child of the result as a right child off the Baron off result. Okay, So resolved. Ducked. Baron said right, Because we are setting the right child. Sudi resolved Dad left. So there are two cases, right there can be there either lefts of tree or the left sub tree is undefined. If it is undefined, it's OK to said the right child too undefined. Okay, but if it if there is some note, we simply said the rights child to this node dead way, we get rid of the result and then we can just returned two results. So return result. And that's it for the get biggest from left sub tree. Right now, let's ready re balance for function. So this that rebalance will be called to function. That except the note that we want to re balance. Okay, so oh, node like this. And first of all, let's compute the balance, so balance will be equal to own owed dot Get balance like this and in here what we need to do. Well, we need to check whether d balances to r minus two, right? So if the balance if the balance is equal to to that means the the hide off left sub tree is bigger by two. So if that happens, we need to use the rotation about which run we can either use right rotation or left to right rotation. So which one do we use? Well, we need to check 40 left child off the o node, and we need to check what balance? Ed half. So let's do it. So Oh, no, that left dot Get balance. And if it is equal to minus one, if it is equal to minus one the we need to use the left right rotation. Okay, so Oh, this death left right off. Oh, note. So we pass into the left, tried rotation, the Onoda as a argument. Okay. And we said the owner old to the result off dysfunction. Because this function will return as the current no debt is being on the top. Okay, great. And in here we write else. And if the balance is one, we just do the irregular wrote. Sorry. Right to rotation. So Right, Right. Great. So this is not the hay like double right rotation or something like that is just simple. Ride rotation cool in your weekend, then check 40 other other tree. Other sub tree being unbalance. So if the balance is equal to minus two, that means the height off rights up tree is bigger by two. So if that happens, we need to do but in my same thing, isn't here I'll just copy based it if you don't mind. And in the right, the right child. Because we need to check in the rights up treat. Okay. And if it is equal to one, we do right. Left rotation. Okay. And if it is equal to minus one, we redo. Left, left, left rotation. It's not like double left. Only left, okay? And yeah, once again, we said it is an old same thing as before, and after this, we just call the rebalance on the parent. Okay, So Well, we need to first of all, check whether we are not at the root. Right. So we are calling until we reached the root. And how do we know that we reached the route? Well, if the own owed the Baron is equal to under find, we are at root. Okay, So if it is not equal to undefined, we are not at the root, so we can call this rebalance on. Oh, node. That parent little note that parent. Legless cool, cool. We have roadie re balance function. So let's define the East rotations. Okay, this left and right. So let's start by a left rotation. This duck l l will be equal to function and dysfunction will accept the note. Okay? And we will keep track of the right and the parents so right will be equal to note that right? And the parent will be equal to note that parent like this and we just how do we just imagine the rotation in your head? And how do we set d? How do we do the rotation while we just said the right child off? No, to the left child of right. Because that we need to set the sub trees. Okay, So noted that set right, we'll be equal to right. That's left So left sub tree off right note will become the right sub tree of note. And also we need to said, D right, well, you need to set the left sub tree of right to the note. Okay, So right, that set set left some tree and we'll set it to note like this. Okay, Right now we need to check whether we are at the root. So we are. We just said the parent body is so if the node is not equal to this route. Simple. Agnes, we check 40 parents So we check the parent value. And if the baron value is smaller, Dendy right to value like this, we know that we need to set the right child so barren that said right said to the right child like this. So this is pretty much the same thing that we did, like already five times. So I'm quite sure that you know what I am doing right now, and, yeah, I'm just setting the right as a child. So I'm fixing the parent. The the reference in the parent. Okay, cool. Right now, I also need to check 40 case where we are at the root. So if we are at the root I just said the parent off rights too undefined like this and said the route to you right like this and return right because we are returning. Do you know that is currently being on the top? OK, and that's the left rotation. Quite simple, right? And let's to find the right rotation this dot are are will be equal to function that accepts denote once again. And in here we do similar things. So you will create a left. We give you a child, right so no doubt left and we also keep the parents of parent will be equal to know that parent likeness. And once again, we said the left We in here should be note Sorry. Bad. Once again we take the right child off left and set it as a left child off note. Okay, so let's do that. So note that said, left to the right child of left. Left that right that sounds finally left dead. Right. But yet I I hope that makes sense. It just the same thing as in the explanation video. Only this time there is no animation is just a goat. But we do exactly the same. S is down in the explanation video. Okay, cool. So right now, we also need to set the right child off left to denote. So left dot said right to the node like this. And right now we need to do pretty much the same thing as in here. So I'll just copy based it. I hope that's OK. And in here we just check if the note is not equal to root. We checked the left value and he said it to left in here. We also said, It's the left and in here if we are at the root We said the left barren, too undefined. And in here we also said Left and in here we also said, Left cool. So that is the right function now is defined the double rotations. So the right left and left right. And since we have the left and right rotation defined, we can find them quite simply so. This, that right left will be equal to function that once again except a node. And we just do the right rotation on the right child of notes. So no, that's right. And after the rotation is done, we do the left the rotation on the note that it's in here and we return it as a result, because the left rotation will give us the no debts on the top, and we want to return denote on top. As a result, off this all rotation off this whole double rotation. Okay, I hope that makes sense. So in here I will just write this that l l and out passing there just denote like this. Simple is that and let's also define the left right. So does it'll be once again a function that except a note. And in here we just write this and we do left rotation on D left child like this. And then we do ride rotation on the note. Okay, so and we also return it as a result. So same as before this death error. And in here we write note node like this and yeah, that's it. I believe that's it. It's also right now we can run the test. So let's tried so control and a five and hopefully this will work And it doesn't. I makes a mistake in here. So war tree is new. Avio is not defined. Why save e l not defined? What did I May? Who him hit small L So, Yeah, that's embarrassing. Okay, so let's around this again and there's another mistake, So Oh my God! Another typo Undersigned! So let's give it 11 more shot and yeah, there are some problems with this, so I will just examine the next video 34. AVL Tree Fix The Bug: Well, hello, guys. And welcome to this lecture and this lecture. We will fix this problem. So let's get into it. As you can see, it says ever value is still in the tree. So we didn't delete some values. OK, so in order to fix that what I did waas candy back the values that we didn't delete. So I wrote in here else. And if we delete the number so that means this waas true, the negation of true is false. So that means if we get to the else branch re deleted the number. But if we delete the number and we can find it, that means the number was not deleted. Right? So I just put this code in here and then I put a break point in here and when I randy program Sorry, I ran into runway only a five. And when I randy program, I always sick What was the problem? So, in a input we tried to delete then and 10 was still in the still in the tree. So then I take a look at how the tree looks like. So I took free and in here's route. Then I went to left because we are trying to find 10. Then I went to left again. And then I need to g o right, and then once again left. And in here we have 10. And as you can see, it have to child. So it have left child, which isn't dine and into have right child, which is 12. So I knew that the problem must be in the case when we are trying to delete the two Childs , right? So if we try to delete a node that have to child So that means this barred Sodi case free. And then I take a look at this gold and right away I figure out what was wrong because we are trying to delete the Onoda. But in here we are checking whether this left is under FIDE. So obviously I made a mistake in here. It should be Oh, node, Right. So just changed this to own owed. And in your the same. And when we change it and run this again, it should be just fine. Ok, so as you can see, it's a send in here. So all of the test were successful and yeah, I'm sorry about the mistake, so just change the this to own owed and everything will were just fine. So there's great if you have any questions. If something isn't working, feel free to ask end, I'll see next time. 35. Tries: Hey, every noticed that if you write something in Google, it automatically suggests you what she might be looking for. Well, this thing, among with others, is based on tries. Try is a tree lag data structure, so and have something called route, which it's at the top. Yes, and in for Matics, roots are at top. Also, every note can have something called Child Child is the note directly under its parent and child. Node can also have Childs, for example, the first note in second row have to Childs. And if node have no child's, it's guilt. Leave. Now let me show you how dese notes look like inside every note. Have references in its childs, and since every note represents some character prefix to match the note and character, we will use something killed. Matt. If you don't know what that IHS, imagine that you have table, and each record contains character and corresponding note. Also, since the its word that also can be briefings off there, we have to be able to decide whether this word it's in our tree or whether it is just a prefix. That is why we have Boolean variable, which indicates that. Let me show you how you can add words I got here my root note and words I want to add. So let's at car to our tree. As I said before, note represents one character off some prefix. So we split this word into characters and at to our tree prefix for every word, starting with C. Now inside his note, we won't add node that represents all words, starting with C A. So we at a into its map and create a new node. So this new note represents prefix. See A And, as you probably figured out, when you add to its map, the our character and create a new node. This note represents all words starting with car. And since we want to add this word, we said, it's it's word indicator to true. Let's try to add done. So once again, we start at root and look at it stable and see that we don't have any note representing deep prefix. So we create one, and at new record two routes map now and this new note we look for oh, since Derris no. Oh, in our table, we added, and create new node which represents do prefix and this note we continue with and where the same thing happened and we create new note for Donna Prefixed and this note we at e and once again creating you note. And since we have no other characters and done, we said this note, it's worth indicator to true and we are done. Let's try to try Once again, we look at route and try to find T in its map. Batty isn't there, so we create new record 14 and add to it corresponding note. We moved to this node and continue with next character in this case are since this notes map is empty, we add, there are and creates new node representing t r prefix And we added his note. Why prefix and ones get we create corresponding new node. This note represents prefix try. And since this is the word we want to add, we said, it's it's worth indicator to true. Now let's add get to our tree So we look at Trude, but we find out that see, it's already in our roots stable. So we just moved to note representing si prefix, and in this note, we look at a once again A It's already dare. So we move to corresponding note In this note we look 40 and we find out Daddy is not in this note stable. So we at ti and create new note and because we have no other characters in cat we said the s word indicator to true. Let's add try We look at rude, stable and find record 40 We continue with corresponding node and this note we find our and move to the representing t r prefix. Now we're looking for I in this note. Since it is not there, we create new record for I and new note for try prefix. Since we still have one character left, we create a new record for E and new corresponding note And this note we said the s word in the gator to true. Now let's add our last word. Do we look at root and see? The D is already in its stable So we follow its pointer. Now we try to find O in this note Oh, isn't this note So once again we follow its pointer and get to this note Since we have no other characters to follow. We said the s word indicator off this node to true and we are done. Let's try to find some notes. First word is see a remember age note represents prefix So we started route and look for brief exceed We fellow sees Pointer And in this note stable We are trying to find a because in order to find see a we need to find see a prefix Well, in this stable well a it's in the stable So we follow its pointer and get note which represents See a prefix So we look at the S word indicator and since it is false this word is not in our tree. Even though we found corresponding prefix let's try to find zebra So we look at routes table and look for Z Since Z is not in there there is no way that zebra is in this tree Actually, because he is not in rude, we can say that any word starting with Z is not in this tree. Let's find try and rude stable We found t record. So you fellow, it's binder And this note we continue with our since our as in this note stable we follow its splendor and get to note we tree presents the R prefix and this note we look for last character. Why? Why isn't this note? So we fellow it's Pointer and since we have no characters left in our word, we look at this notes. It's worth indicated and since it is true, we can say that try, it's in this tree. Let's try to find card. We started route and follow. See? Then we follow a. We still have two characters to go, so we continue with our We get to note representing car prefix and look for D. But de is not in the stable, so guard is not in this tree. Let's try to delete some words. We are the leading by finding this word. If the word have child notes, we cannot delete it. So we just said the S word indicator to false. But if there's no to have no child's, we can delete it and then check if we can also delete notes above. Let's try to delete some words. We are the leading by finding the word and if the word have child note, we cannot delete it. So we just said the is worth indicator to false but if the word have no child's, we can delete it and then we can check whether we can also delete the notes above. So let's delete Do we look up, Do and see that denote representing do prefix have child So we just set the is worth indicator to false. Now let's delete try So we look a try and see that try is a leaf In other words, it have no child So we deleted and also the lead the record that points to this note and note above Now we see that denote above also have no child notes so we can remove it to and once again we also removed the reference in note above Now we try to delete the note above but it has a child so we cannot delete it. That means we are done Now let's try to delete see a we look up, see a and see dad The is worth indicator off This prefix is false and we cannot delete something that is not in the tree. So we are done Okay. You have learned how try works. If you don't understand something, please just ask me and I will see you next time 36. Tries Implementation: Well, hello, gas. And welcome to this lecture In this lecture will start implementing the try. So let's get started. First of all, let me just define d note. So I got here once again the testing and it's a bit different because I put in here the strings. So some words, we will insert them. Then we will delete half of them. And then we will ones against search them. So yeah, And in here we will once again the fine denote so function node. And that will be accepting no arguments right now because the try note it's a bit different , right? It represents a prefix, so it have, like, hidden value. So and this note, every note have a map so that it will be just a object. And also every note have the s word indicators. So that will tell us whether it s a word. So I'll set it to false by default. Great. Right now we will also use a few methods. Dad will help us like to write decode in the try a bit simply er so and more easy to understand. So in here we will define a method called hath have record, maybe. Yeah, have record. You can also quoted, like have Childs. That's also a good name. So if it have a record, it will be a function that except Snow argument. And if it have any record in the map, we will return True and if it has no record, will return falls. So in order to do that, there's a method in the object prototype and its gold entries like this. And basically, when I passed some objects into it, it will tell me the number off properties, right and the values. But mostly we care about the length off the array, right? So I will call this with the map and I will ask for the length off the array. So that means how many properties are in this object. And since it is map, it have, like character and note, right? So if the length is greater than zero, it must have, like, at least one record. So that means it has at least one child, and we will use that when the leading notes. But if it f zero right dealing, if the length zero it have no record, so this will return false, great Now let's also define a ed record function, so at record, and then we'll basically at a record so function and it will accept a character key. And what did Will do? Well, it will just at a new record. Two D maps. So this map on the Sea Key like this, so we'll be corresponding with a new note. It's a new node and yeah, that's it. Right now we can just return, and I'm thinking that I will return D. No, because we will use it. Yeah, that will be better. So this ed record will add a new character to the map, and it will return the no did we just created right? So it will also followed the pointer. Cool. So this is basically the note glass. Nothing too complicated, I think so. Let's define the try. So function. Try and it will accept once again, no arguments, and it will have a route. But this time it won't be undefined, because it will be. It's not the try as a bit different than some binary search tree and the Aviall tree. The try from the beginning have a route OK, so it will be a note that have, like, no nothing in the map, but it will be a note. Also, let's define the insert function. So, like this and it go insert some value. So string value and the in here, what do we need to do? Well, we need to keep track of the Korean node, So oh, trend And well, said it to route from the beginning grade. That makes sense. And right now, for every character in the string input So four for I equal to zero until D while the I a smaller dad s value that length, we will increments I So we'll go through each character Same in the same as in the explanation video. And for each character we will check. And what are we checking? Well, we'll check whether the map of the current node have the reference to debrief IQ. So we basically check whether there is existing prefix. Okay, So if ocurre end dot matt have a s value, so s value on Index I. So that means the character. So if the Oakland map So if the map of the current know that we are add, have a prefix off this character, so have note that corresponds with this character. We will follow it. But if it iss under fire So if it iss let's say not equal to undefined we will just follow d character. So we said Okrent to ocurre end Nah, map. And in here I'll just write s value and I okay like this so cool bad if we get to the else French that means there is no corresponding note with this like characters. So we need to create it and we get the function add record for that. So I said, Oh, current to the result off old grand add record And in here I will add record 40 as value on index I for the character that we are currently at Cool. So once we get out of this four cycle, we can said the is word indicator to true So ocurre end I doubt his word will be set to true And you can also check in here whether the word boss already in the tree And if it do us, you can return false, right? So something like this. So if Oakland is worth, you can just return bulls. So that is up to you and that means like the word it's already in the tree and we don't want to insert it second time. So if you want to let the user know, you can just return False. But otherwise you can just said the s word to true and then return true like this. And it's the insert function. Quite simple, right? So lets her I d search function This one will be even simply are so function that accepts the value that we are searching And I will just got be based it to save some time and in your we'll get rid of this stuff. And so what do we do? Well, we start at the root and we are trying to follow the character. But if it is not equal to under find we follow the character. And if it is undefined, we return false because it is not in the tree. Right? And in here once we once we go through, all of the characters reaches returned the Israeli indicator. It's ocurre end. That is word. And that's the search. So search is quite simple. I believe you should be able to understand it. It works exactly the same as in the explanation video. And it's not so complicated in my opinion. So let's right the delete function. This one will be a bit more complicated as usual, Like the delete function is mostly the most complicated in, like, pretty much every day to structure. So yet let's do it. So we want to delete the value. So in order to delete the value, you first of all, I need to keep track off every note from the path to from the route to the note that we delete it. Because then when we try to deleting, note that we don't need any more, we will use that. So I will keep a array. So I'll just call it like Bath. And it will be a ray containing notes that are on the path from root to the know that we delete it. Okay, and I'll also keep track of the current, and I will set it to dis route from the beginning. And right now I am finding the elements so I can just grab this thing because we are doing exactly the same right? We're just going through the word, trying to find the element. If the element is not in the tree. We return false. But if we end up after this four cycle, we will have the in the okra and we'll have the word that we want to delete. So in here I'll just said the Oakland up his word two falls like this. And we right now we have the leader denote right, so that was quite simple, but yeah, I forget about something in here. We have the path variable. So we need to keep track of the bath. So in here, whenever we go to next node. So whenever we followed the pointer, I will push the Oakland to the path variable. So Bush and in here I pushed the Oakland likeness. Cool. So right now we have deleted this word using this line, and we have the bath in this variable. And like, we have the path except the last note, but the last notice in the Oakland. Okay, so right now we want to delete the notes that we don't need anymore. But in order to do that, we want to keep track. Well, we still need to go a Zaid as the input, but we go from the behind of the input. Right? So we follow the pointer, but off the input from behind. Okay, so I will just keep a index off inputs. So, for example, like care index. So this will be the index of the character from as value and as the initial value, it will be said to the length of red minus one because we start from the back. So we go from the back and follow the characters and delete every reference that we can. Okay, cool. So right now all we need to do is just Ah, right, the cycle that does that for us. So we were Luke. Prudie Bath. But we will look from the back to the front. Okay, So I'll set in I variable to the bath dot length minus one because the last element in this path variable is on index path. Ling, that my minus one and I will move while I was small, bigger than zero, and I will decry meant I So that means we kind of followed the pointer and go up. OK, so we kind of Joe Beck, Sooty bath, cool. And right now, for every note, I will just give the Quran note in the Okura and very but once again OK, so right now 40 every note we check whether we can delete that. So if the node have no record So if ocurre end dad have record is not true so negation So if negation of have record that means it have no record and And if the node half is not a word So if Mulcair end his word is not true So negation of the s word If it is, if this whole condition is true, we can delete the note. Okay, so how do we delete it? Well, we just go to the note above and that means we will said the Oakland to the note above. So that means the note in the bath on index I okay so fast on index I And in this note, we'll delete the reference. And that way we were kind of the led O Corin node. Okay, so how do we delete the reference? We will just delete the property. So in here I write delete and from the Oakland dot map I will find the character right. So we need to the lead The last character that is pointing to the Oakland So Oakland, on index car index. Okay, so we are indexing from behind in here. I will make it bigger. And so we are indexing the word from behind. And as we go up, we always move the the car index. We will always Deke amend it. Okay, so car index will be the CRA meant it like this. So as we go up, we move and we move one character to the left, and we try to delete the record and the note above kinda. Right. So in the Oakland, we will have always Do you know that we try to delete and yeah, the Beth the I will be always recommended for us where this four cycle. So that school and we also need to decry Mandy Character Index. So move one character to left each time we delete a note, OK? And if we go to the else branch So that means the notes cannot be the leader. It also means that every note, every note above cannot be deleted. Okay, so we can just break out of this cycle so break and in here we can just then return true because we don't see that the value So like this. And I believe that this should work. So let's give it a try. So control and five will run this killed. And it's this end, so everything will work just fine. So I inserted some like strings and in here I deleted and and find it so cool. That's pretty much how we can implement. Try in your code in your JavaScript And yeah. So if you have any questions, feel free to ask End. I will see you next time. 37. Linked list: Ling Bliss is a data structure that starts with add and can contain several records where every record have value and pointer to next record and the last one points at now. The insertion have constant time complexity since when we are inserting, we create a new record, said it's pointer to Current had and said this record as a new hat. So let's at ball we create new record which burns to now since there was no record before and we said this record as new had let's add nickel. Once again we create new record, pointed to Paul and said it as new head and last record. We want to add ISS Adam and we do the same as before. So we create new record points it at Nikko because Niko is our current had and set this new record as our had. So let me show you how the search works well, we go through every note and compare it to value that we are searching. If it is not equal, we follow the pointer and if the pointer is now this value is not in the list. Let's find Paul we go from had since Paul is not equal to Adam. We followed the pointer. Then we compare Paul and Niko and move to next record and we found ball. Let's try to find Fred. We do the same. So we compare. Fret to every note. And when we reach record with ball, we can not counting you because there is no pointer. Ball points to Nelle. So dead means Fred is not industry. Now let me show you. How did a leading works? When we are deleting, we find the record dead we want to delete. And we said the pointer of a record before to whatever points the record that we want to the lead. So, for example, if I want to delete nickel, I find Nicole and said the point of a record before that means Adam to record behind. So to Paul. So Adam will now point at Paul and then means we will kind of get rid off Niko. So the only difference is when we are deleting had So let's say that we want to delete Adam . So we go from the start and we right away, find Adam. So what do we do? Well, we just set D note that Adams pointing to as our current had okay, doesn't make sense. So when we want to delete Adam, we just get rid of Adam and the record debt. Adam Point Sue is our new hat. So in this case, ball is our new hat. I hope this makes sense. It should make sense because linguists, it's not such a complicated data structure. You should be able to understand it. If you have any problems, just write me a message and I will see you next time. 38. LinkedList Implementation: Well, hello, guests. And welcome to this lecture. In this lecture, we will kind of create dealing list. So let's get started. I already created the testing. Well, I just got be pasted from the the Aviall tree and yeah, it's just stayed the same, so you can also copy and paste it and let's define dealing Klis. So first of all, we will define the note. So the every note and linguist have a value, so I value and it have also a reference sooty next child. So oh, next. Well, not a child, but just the next node. Okay? And we'll just set it a see value. And we also said it as a next. So there's that next is equal to go next. Great, and that's it. The notice. Fairly simple. Right now. Let's define the link list. So function linked list So constructor for it and it will accept no argument, no para meters, and it will have a route, so this route will be equal to under find from beginning once. One thing that I want to mention is that you can just pause the video and try to implement linguist on your own. You should be able to do it, I believe. And if you get stag, don't worry about it. I will be here and I will still implement it so you can check back and see what you did wrong. But yet, but that being said, let's start deep. Let's right the insert function. So it will be a function that except a value that we want to insert. And do you remember from the explanation how we insert it? We just said the rude as a new no. We said we create a new note and said it as a route. Right, So this that rude will be equal to new node that have the value. And it also points Studi grand route. Right? So this that route and that's it, which is great that we just insert it, so I just can I can just return true likeness. And yes, so this line does the inserting. Don't worry about using the this route in here. It's okay because we override it after we read this. So after we read this route, so that's OK. And with that being said, let's write the search. So this debt search once again it will be a function Dad will accept the value that we want to search. And as in the explanation video, this one is quite simple. We will just create a variable. So trend said it to root like this And while de ocurre end is not undefined So that means this we will just check whether we are where we found the value. So if ocurre end that value is equal to I value so if it s we can just return well equal, we can just return true because we found the element And if it is not, we said the ocurre end to the next note soaker and dubbed next and And when we get out of the off this Weil cycle, that means no grand waas undefined. So that means there was no next. So that means we reached the end. So we return false because the value is not in the list like this. So yeah, pretty simple so far, right? So let's ride the delete function. This one will be a bit more complicated, but it it's still okay, so this delete will be a function debt, except that except the value that we wanted to lead like this. And what do we do? Well, first of all, we check for the road whether the values route, but about we first need to check whether is root defined. So if this that rude is not equal to undefined. So that means if there is a root Yeah, And in the else branch, we can just return because if there is no route, we cannot delete anything. So we just write the return false. And if if if it is rude, we just check if there is route, we just check for the whether the route is enough that we want to the lead because from the explanation video, you might remember that we delete that route differently than we believe that the other notes so denotes in the middle. So if the value of route is equal to I value, we want to the lead route. So how do we do it? Well, we just set this route to the note that the root is pointing to So that means the this route that next and that's it. We just believe that route and we can return true. And what does work if there is only route in the list. Well, it would, because this route is pointing to the next is undefined. Right? So we said this route under fight, and that's okay because we had only one note in the year. Inglis. So there should be no note. So great it works. And if it is not rude, So that means we need to take care of the average case. And we will keep a track off the note before once again because we need to set the reference from note before to the note behind. So oh, note before will be equal to under find and ocurre end well, the equal to this that route. And while the ocurre end that you is not equal to I value so until we find the until we finding No. Did we want to delete? We will. What do you will do? Well, we will just go next, so Oh, no before will be set to ocurre En right. So we need to keep track of the node before. And we also said the grand 20 trend that next like this and another thing we need to check is that the okra and that next is not undefined because sometimes can happen that we reach the end, right? So if the ocurre end so that means this one, it's undefined. So it's equal to undefined. We want to return falls because we reach the end of list and we didn't find the value right . So return, return, false likeness. And yeah, So after this vile cycle, we will have the the ochre and node. So the Okura is We know that we want to delete. And how do we delete? Well, we said the pointer from note before to whatever the Oakland is pointing to. So let's do that. So oh, note before that next will be equal to ocurre and that next. And even though if the Oakland that next is under Fang, that means the Oakland Waas the last note off the list, we will, said the owner before to next to undefined. So that means it will still work great. And when we do that, we can then just return true because we'd earlier the number and yeah, so that's it. But right now, on thinking that these tests won't work because we can insert same values, right? We don't check whether we are inserting a value that is already in the tree, right? So if we don't want to insert same values multiple times, we can ride Just if this dot search. So basically, we check whether the value is in the list. If it is so, we return false. If it is not, we inserted. Okay, So if we search the I value and it is true, that means it this indie vist, we just return false, and that's it. So if I run this using control and that five, as you can see in here, it's a end. So that means all of the deaths were were completed. And if you want a linguist dead, you can have, like, same values multiple times. You can just commend us out, and it will have seen values multiple times. So yeah, that's up to what do you need, bod? Yeah, that's pretty much it for this video. If you have any questions, feel free to ask end. I will soon. Next time 39. Hash Table: Hey, stable ISS, Probably most used data structure. Basically, it mentions the key with value. The most important thing about s table is hash function. This function basically takes some value and returns index within certain range. This range is set by us by users and it is just size off the array size of the hedge stable . So if we want to add some values, we pass them to hedge function. This function returns us some index, and we just put our value and corresponding index. The hedge function returns same index for same input. So, for example, if I pass Joan, I get six. And if I pass John again, I still get six. Okay, I cannot get like, some different number. I always gets the same index. That means in average case, we insert search and delete and constant time, which is great, which is awesome. But there are some problems. For example, if we want to add a me, the hash function can return index six bad. We already have John in there, so we cannot put Amy in there. Very spread is simple fix. We can just increment the index until we reach to an empty field. Yes, debt will work, but we still have limited size off our array, so eventually we would fill it all and there would be no place to put any other values. The solution that we are looking for is linked list. Basically, every field in array is pointing to a head off some linked list. And when collision happens, we just add this value to this ling list. This way we have the time complexity off an divided by these size off our array and Dad is great as a hash function, you can implement something like this. We start with some prime number. This makes it more likely to generate unique hashes. And for every character, we multiply our hedge by other prime number and at to it the value off our character. And we will get the final index by hash module sites of our hash table. Another commonly used to hedge function is the Jenkins, which takes provided string, and for every character it does some binary operations. These operations are actually faster down multiple ag, so when you insert thousands of values, you probably should use this hedge function. But it is same as with sorting algorithm. Just get some data and tested, and that is pretty much at these are hash tables. If you have any questions, if something isn't making any sense, just asked me and I will see you next time. 40. HashTable Implementation: Okay. Hello, guys. Send well, Come to this lecture in the lecture, we'll implement the hash table. So let's get started. I already imported the Linge list so that we can use it in the S table and I already copy and paste the tests from the tribes. Okay, so let's do that. Simply defined a function. Hey, stable. And this constructor will take a argument so it will take the size so I size and they will have a It will have a list, right? It will have a array of linguists, So let's define it. Let's go. This one, for example, content And it will be equal to a array and we will initialize it in cycle. So variable I will start at zero and we will initialize everything list. Right? So I size I size and I'll increment I So we'll go through every linguist and we will said the discontent on end exciting You list linguist. So let's do that. This content on index, I will be the new linked list like this. So cool, because we will use the insert search and delete methods that linguist half and if we didn't initialize it, we would call a insert over undefined. Right, So we would get an error. So we need to initialize the array off linguists right now. What do you want to do? Well, we want to define the insert, sir. Generally the right. So Algiers, right? This insert And it will be a function that accepts the value that we want to insert. So s value and the what we need to do. Well, we need to compute the index so variable index, and this will be equal to a result off hash function. So this dad hash function and we will define the head function later on. We are bad there d the values so as value. This will return us some number and we will do just module oh, over the size. So over this that content that length. Okay, so that we don't go like behind the content or something like that. Cool. So then when we get the index, we just call this that content. So we pick the correct a linked list. So in here will be index. So we big the correct ling list and we call their inserts so insert. And in their rebounds, DS value like this, and that's it. Also, we need to return the value that this method returned us. So when we insert dealing list, the linguist will tell us whether we inserted correctly or not. Right, So cool right now was to find the search and delete. And in order to do that, I'll just copy and paste these because they are pretty much the same. So in here will be searched. And when we are searching, we once again need to compute the index of the of dealing list, and we will do it the same way, and then we just go search instead, of instance, ERT and we search it and this will return of some bullion value and we will return the value as a result. Cool right and singles for delete. So the lead will be a function that accepts a value. We compute the index and we call the lead over the corresponding linked list. OK, cool. So that's pretty much all the logic behind the hash table. So let's define the problem most important part, which is the hedge function. So I will just write this that hash function. And as I said before in the explanation video. It's a function that takes a some value, and it returns us some index bad. The index must be same for in each case, right? So allergies, right, variable, and I'll call it Ash and start. I will set it to some Brian number. So, for example, seven And now for each character so were wary about I equals 20 and we will go while I a smaller debt. That's value Dad length. And we will increments I each iteration cool so well for every character, basically will. This thing says what we will do. Well, well said the hash to some hash operations. Right? So we were multiplied the hash by some other prime number. So, for example, 31 and we will add to it devalue off a character on index I. But in jazz grade, B cannot just right in here the s value on index I because that would return us a string well and character and And it would return as the whole function would return us a string. Right. So we need to write something like, as value that car at guard code at. Okay, This will return us a number like the the represent, the number representation off the character at index I. Okay, so yeah, but that's about it. That's that means we go through all of the characters. Do we multiply the edge by some prime number and add to it the coat off the character, And then we can just returned the hash. So this thing should work right now, and yeah, this would be like to simple. So let's also implement the Jenkins inch function. Okay, so this Dad, let's go a Jenkins hatch like this, and it will be a function once again accepting a string value. And oh, and we will do Well, not exactly the same thing, but something similar. So we just I'll just copy pasted that in here. We won't start with seven. We start just with zero. But we still need to go through all the characters. But in here we will add to hash A. Firstly, we add to hash the logical end between the code of the character and the the FF, right? Basically, basically, we do decode of a character. Okay, then what? We will do Well, we will run to get ad a binary shift so we will shift it binary by 10. That's OK. And then we will shift it once again that this time we will do it like this and it will be a hash shifted the other way by six. Cool. So, yeah, you might not understand all of the binary operations. I won't explain them right now. Basically, it just moves the number binary. Okay, It's not too complicated. But if you don't understand it, that's OK. And once we are down, we just add to the house. So we do once against some operations with the hash. So I will move it, move the hash by free, and then I will just do this operation over cash that we will be moved by 11. And then we once again add the hash. There was moved by 15. So yes, this shoot this should mean like you shouldn't yet you should use this function when you care about D time. Complexity, right. So because the disease function uses the multiplying and the mood of blank is not such fast operations, the binary shifts are much more faster because computer really knows how to do that. Well, processor really knows how to do them. And yes, So if you out inserting like a huge number off off records, you probably want to go with the Jenkins Ash about. For our per teaching purposes, the disease function is just fine. OK, so let's try it out. Okay. I in here create the new hash table with the size of five suited. We have some collisions in there, and then we just tested sing way as before. So if I hit control and a five, it should run the goad. And as you can see in here, it's us end. So everything works just fine. And, yeah, so Dad is pretty much it for this video. If you have any questions, feel free to ask in. I'll see you next time.