[MUSIC] Balanced binary search trees are kept in balance through tree rotations when we do an insert and remove. We call these trees AVL trees named after two computer scientists, Adelson-Velsky and Landis. An AVL Tree is just like a Binary Search Tree. Everything you know about a Binary Search Tree still holds true. That includes finding, inserting, removing, and everything else. We only do two things differently in an AVL Tree. That is, we do in some extra work on insert and remove to ensure that we keep the trees in balance. And you keep the balance factors you'd be able to be computed easily, we're going to store the height of every single node in the tree. We'll see how this works through examples, so let's go ahead and look at an insert. Suppose we want to insert the node 14 into our binary search tree or an AVL tree. Just like the insertion algorithm we talked about previously, we're going to start the root, compare 14 to 18 and find that we need to move left. Looking at 5, 14 we need to move right, 10, we need to move right again, 12 we need to move right again. And here we can insert 14 as a new leaf node right at the end of this path. We do this insertion through a recursion algorithm so we can always check each thing as we move back up the tree. So lets actually look at a step wise process for doing this. The first step is to insert at a proper place. We know that the insertion happened by taking this path right here. And inserting here at 14. As we move back up the tree we're going to check at every single place for an imbalance. Rotate, if necessary, and update the height. So here, the height of 12 is now going to be equal to 1, since we have 1 node below it. Moving up to 10, we see the height of this element is going to be 2, because we have 2 nodes below it. But what happened here? We have an imbalance right here. We have one side of the tree, the right side, having a height difference of more than one, specifically a height difference of two, so we know that this tree's out of balance right here. So we need to go ahead and repair that. We do that through a simple rotation. We're going to have 12 moved up. So, 12 is going to be the top node, 10's going to come from the left, 14's going to come from the right, and we have a repaired binary search tree. The height of 12 is 1, the height of 10 is 0, the height of 14 is 0. And now, we can move up to 5, check if 5's height is still 3, it is, and then check at 18, height is still 4. So by doing an insertion and moving back up the chain, we saw we only needed to do a rotation somewhere along the path we took to do the insertion. We found we had to do one rotation this time, but we were able to insert 14, and ensure that the AVL tree was a balanced binary search tree by the time we gave it back to the user. The code to ensure the balance was added to the binary search tree code you saw last lecture, and now we have this extra helper function called ensureBalance in our AVL tree. This ensureBalance function is going to help us by ensuring that if our balance has a value of -2, we know that we need to either do a right rotation or a left/right rotation. If our balance is 2, we know that we need to either do a left rotation or a right/left rotation. We determine that by looking at the balance of the next node, so here we see the height of the cur left right, and the cur left, left. This is exactly what we saw in the diagrams that we looked at previously. So everything you saw in the last video, and this video, came together in this function to ensure that if our tree is ever out of balance, that we do the proper rotation based on a table we discussed last time to get the tree back in balance. Taking a look at the rest of this, we need a updateHeight function that simply updates the height. And a rotateleft function to do the actual rotation. And that's it. The only other place we need to do actual work is in remove. So let's look at the possibility of removing 5 from our original binary search tree. Here we're going to find 5, just as we've done before. 18 move left to find 5, and we've found the node we need to remove. Remember, to remove a node, we need to find the in order predecessor of that node. That means we have to find the node that comes just before that node or the rightmost node in the left sub tree. The rightmost node in left subtree is going to be the element 4, so we go ahead and swap 5 with 4. And then we need to remove this node we just swapped so we remove 5, we'll notice that we now have as we move up this tree from 5, we have to rotate 3 because 3 is now out of balance. There's a height difference of two, on the left than the right, rotating this we're going to see that it's an elbow. So the first thing we're going to do is transform the elbow into a stick and then we're going to raise the middle element of the stick so that we now have 2, 1 and 3 hanging off the site of the 4 element. Now we see that with a height of 1 here and a height of 1 on the left hand side and a height of 1 on the right hand side, the middle element here has a height balance, exactly right. The height has actually shrank slightly. So the height is now 2 here, we move up the tree and we see the height of the root is 3. So, just like before the only nodes we have to update is the path we took to do the deletion. When we remove an element or we insert an element, we only need to modify nodes along the path to do so. So the code to modify, the remove is just going to be simply adding an extra function called iopRemove, that's going to go ahead and remove the iop, and it's going to find out whether or not, where the iop is by looking at the rightmost pointer in left subtree. And if we have found the iop, we're simply going to swap that element, and we're going to go ahead and call our remove function to remove it altogether. You will have all this code provided for us, and we'll take a look at it in a second. So as you reflect on all of this, we know that an AVL Tree is a implementation of a balanced binary search tree. And in the implementation of an AVL tree starts with a binary search implementation and then just adds two things. We added the height of every single node to be stored with the node itself. And we maintained the balance factor of the tree after every insertion or remove. By only doing those two things we ensure that we have a balanced binary search tree. So before we go, let's take a look at the code and then we'll discuss exactly how this AVL tree runs in our next lecture. So let's look at some code. Going to the AVL directory, I can check out what's in main.cpp. You'll see inside main, we create an AVL tree, and this AVL tree is going to be a dictionary where we have integers as the keys and strings as the values. Here we insert a number of things in AVL tree, just like we did in binary search tree. The key's going to be the integer number. The value will be the string itself saying the integer number. And we'll see out a bunch of things. The first thing that we're going to do is we're going to find 51 using the code we have for our AVL tree. Then remove 11, 51, and 19, as well as 6. So 11's going to be a simple remove, where there's no children. 51 is going to be a somewhat simple remove, where there's one child. And then 19-6. Those are going to contain two different children in our AVL tree to make them more complex moves. To make sure that we handle the IOP situation exactly correctly. The very last thing, we're going to find 51. We expect you to have that to be an error because we just removed 51 earlier. Let's go ahead and run this and see what happens. Running make to compile. And then ./main. We see when we find(51), we indeed get the 51 value out. Removing 11 removes the 11. Removing 51 removes 51. Removing 19 removes 19. Removing 6 removes 6. Here, when we find 51. We find that we have an uncaught exception, key not found. This is exactly what we expect because since the first time we found 51, we've removed it and now 51 no longer exists. So, you have the source code for the AVL tree, you have all of this information you can play around doing amazing things with the AVL tree yourself. And I hope you'll spend some time doing that. So have fun and I'll see you next time.