In the last video, we talked about the balanced factor of a binary tree. Now, we're going to talk about the balanced binary search trees, which are trees or a height-balanced to ensure that nearly half the data exists on that left half of the tree, nearly half the data exists on the right half of the tree. Here on the left, we see a very balanced binary search tree. On the right, this binary search tree is far out of balance. Let's analyze the substructure of this tree and develop an algorithm to ensure that we can turn a binary search tree that's unbalanced into a binary search tree that's completely balanced. There's two substructures that we're going to identify in a graph. We're going to identify as substructure that we're going to call a mountain, which a node that has both the left and the right child, and a substructure called a stick, which is going to be a node that has two children in the same direction and no children in the other direction. The stick is going to be something that we're going to want to transform into a mountain. By transforming sticks into mountains, we're going to make sure that our binary tree stays as balanced as possible. So, let's consider a binary search tree in a pretty simple example. This binary search tree was initially balanced. We know it's balanced because you can check the balance factor of every single node, which is the height of the right child minus the height of the left child. The height of the right child into the original tree is simply going to be one. The height of the left child is zero, and doing one minus zero, we see the balance factor of the root node is one. By adding a new node to the end of this tree, now the height of this right subtree is two, two minus zero is two, and because the magnitude of the balance factor is greater than one, we know this tree as a whole is out of balance. So, when we look at this tree, we want to consider where the deepest node that is out of balance. So here, this new node added, it has a balance factor of zero, we have the same number of children on both sides. Its parent has a balanced factor of one because it has one extra height on the right side over the left side. Next tree has a balance factor of one. Again, left side having a height of one, right side having a height of two. Only here at the root node do we see that the balance factor is two and that's the deepest point in the tree that we're out of balance. Once we've identified the deepest point in the tree, we're going to identify the stick that causes the node to be out of balance. Here we've done just that. Notice the stick running from U an unlabeled node. It's three nodes that make a stick is the reason this tree is out of balance. Let's try and transform this into a mountain. To do that, I'm going to pick up the middle node on the stick, right here this V, raise it up. By raising up this middle node, by pushing this whole node up, we see that this node is going to become a mountain. This mountain, then we simply repair all nodes, notice to the left of U, there's a pointer. The node that was off the left of Y is now going to be on the right of U and the right of Y is going to be untouched. So, what we've done is we've created a tree that's going to maintain the factors of being a binary search tree. So, all of the order here is maintained and we've decreased the balance factor of the root node. So here, now the balance factor was two, and you've transformed it into a balanced factor of zero through using a simple binary search tree rotation. So, if we consider this arbitrarily, we can talk about generic left rotation. The idea of a left rotation is we're going to consider the deepest point of the tree that has an imbalance to be node b. So here right at the top, this is the node, this may be somewhere deep inside the tree, all we know is this node B is the lowest or deepest point inside of our tree where we detected an imbalance. An imbalance is a balance factor that has a magnitude greater than one. So here, the balance factor is two. When the case is the balance factor is two, we need to look at this next node. So, we look at c, given that we found B, we now look at c and see the c's balance factor is. If c's balance factor is one, we know that b is out of balance heavily to the right, and c is also almost out of balance to the right. That means our tree definitely has a terrible slant to the right. What we can do is we can do what's called a left rotation to solve this. Doing a left rotation, this means bringing c up and making a tip to the mountain and rotating everything to the left. That brings b down and attaches c to b. So, looking at t_1, t_2, we see t_1 and t_2 is attached to b; c is attached to b and d, and finally, t_3 and t_4 remains attached to d. We call this rotation left rotation, and this rotation occurs whenever the deepest point of imbalance has a balanced factor of two and the balance factor of the node that follows has a balance factor of one. Anytime this occurs, we can do a left rotation to repair this imbalance. Let's consider a second example. This can be very similar but instead of having a node added to the left, we have a node added to the right. If we identify the substructure that has the problem, the deepest point of imbalance is now here. It's no longer the root node, but this node has a balance factor of two. Notice that the height of the right subtree is two, the height of the left subtree is zero; two minus zero is equal to two. This, unfortunately, doesn't fit our cases that we've looked at so far. Instead, we've identified a structure looks more like an elbow than a stick. This is indeed our third structure. This is a hybrid between both a stick as well as a mountain. What we need to do whenever we identify an elbow is actually fix the elbow to make it a stick. We do that by doing a rotation about the bend of the elbow. Notice here, we have an elbow; we do a transformation by moving this yellow node up, then transform this elbow into a stick. Once we have a stick, we know exactly what to do. We consider this a right-left rotation because what we're going to do is we're going to do a right rotation about d, to place it in place, and then a left rotation about c to fix the stick. So here, this right-left rotation is going to be required whenever we identify the point of imbalance in the tree b, the balance factor of b is two, and then the balance factor of the node that follows b is going to be a negative one. Insert at t-2 or t_3 is going to cause this point of imbalance, and we simply need to do two different rotations to fix this imbalance. Seeing this completely, we notice that we first transform this elbow into a stick, and once we transform the elbow into a stick, we raise up the center node of the stick and make it into a mountain. So, here we go from an elbow to a stick, into a mountain. At the end, we know is we take a tree that's completely out of balance and have a nice perfectly balanced binary search tree at the end of this process. So, we can look at all of this rotations and think about how we can just flip this idea that when we have a left rotation, if we consider a tree to be out of balance entirely opposite direction, we simply need to do right rotation. Look at the balance factor of the deepest node of imbalance in our tree. If it is two, we start with a left rotation. If it's negative two, we start with a right rotation. Only then when we look at the next node can we identify whether or not it's a single rotation, so if both of the signs match, we say we only do a left rotation, this transforms a stick into a mountain. Just like negatives, we transform a stick into a mountain. When the signs differ, we know we have a case of an elbow. When we have the case of an elbow, we need to do a double rotation or a left-right rotation or right-left rotation. This unbends the elbow and then does the simple transformation to transform a stick into a mountain. So, I introduce these things in really simple terms. So we can talk about sticks, mountains, and elbows. We saw visually how this code is able to transform an out of balanced binary search tree and bring it into balance at the moment we detect the imbalance. So, as we insert nodes, we're going to want to ensure that we're keeping the binary search tree in balance every single insertion. When we complete an insertion, we're going to ensure that by the time we return it back to the user, that binary search tree is going to be balanced. BST rotations or binary search tree rotations is the mechanism to restore that balance. We know there's four different rotations, a left rotation, a right rotation, a left-right rotation, and a right-left rotation. These rotations are all local operations. All we're doing is changing the point of imbalance, rearranging a few pointers. Because of that, we can say this runs in constant time. The code we're going to write to do these transformations are going to be as simple as four lines. The last thing to mention is this algorithm actually has a name. This is called an AVL tree. We're going to dive into all of the details of an AVL tree and talk more about it in the next lecture. I'll see you guys then.
