Hello and welcome back. Today I'm going to introduce probably one of the most important types of trees in computer science, which are balanced binary search trees. Balanced Binary search trees are very different from the traditional binary search tree because they not only conformed to the binary search tree in variant, but they are also balanced. What I mean by balanced is that they're self adjusting to maintain a logarithmic height in proportion to the number of nodes they hold. This is very important because it keeps operations such as insertion and deletion extremely fast, because the tree is much more squashed. In terms of complexity.

A binary search tree has average logarithmic operations, which is quite good. However, the worst case still remains linear because The tree could degrade into a chain for some inputs. One such input is a sequence of increasing numbers. To avoid this linear complexity, we've invented balanced binary search trees in which the worst case is logarithmic for all operations, which makes them very appealing. Central to how nearly all Balanced Binary Search Tree implementations keep themselves balanced is the concept of tree rotations, which is going to be the main topic of this video. Later, we'll actually look at some specific types of bounds binary search trees to see how these rotations come into play.

So the secret ingredient to most on binary search tree implementations is a combination of two things. One, a clever tree invariant and tree rotations. A tree and variant is simply a process property or a rule that you impose on your tree, such that it must be met at the end of every operation. To ensure that the invariant is always satisfied a series of tree rotations are normally applied. We'll get back to this concept and fitting variants in the later video, so don't worry about them so much for now. Right now we're going to look at how tree rotations work.

Suppose our invariant is not satisfied. And to fix it, we need to do a right rotation about node A. Assuming node A has a left child B, we can perform a right rotation to put B where node A was and push node A down to become B's right child. When I first learned about this in my undergrad, I was Mind blown literally. I thought it was absurd or even to the point of being illegal that we should be allowed to Do this and just move around nodes in a tree. But what I've realized since is that a transformation like this is totally legitimate since we're not breaking the binary search tree invariant in any way, if you inspect the left tree, you'll discover that in terms of ordering and placement, node D is less than node B is less than E is less than a is less than c, then you inspect the right tree and remark that well, this is also true.

A bit more detail on why performing tree rotations is a valid operation. First, you have to remember that all bounce binary search trees are binary search trees, meaning that the binary search tree invariant holds. So for every node and the values in the left subtree are less than the value of n and the values in the right subtree are all greater than the value of n. So in this sense Doesn't matter what the tree structure itself looks like. All that fundamentally matters is that the binary search tree invariant holds. This means we are free to shuffle, transform or even rotate the values and nodes in our tree as we please, as long as the binary search tree environment remains satisfied. Now let's look at how these rotations are done in great detail.

For simplicity, since the rotations are symmetric or will only do the right rotation, and you should be able to figure out the left rotation on your own. first have a look at the tree on the right. Notice that there are directed edges pointing downwards and another node p above a, which may or may not exist. This is why there is a dotted line on that edge. If a note a does have a parent node p then it is important They would take it into account when doing the rotation. In either case, we start with a pointer or a reference to note a, this is the orange arrow, then we'll want a pointer to node B.

After that set a is left a pointer to point to B's right child, then change B's right pointer to point to node A, and we've successfully done a right rotation. If we rearrange the nodes, this is what we would end up with. However, notice that there's a slight problem. If node A had a parent node then either the parents left or right pointer would still be referencing a. This is problematic since B is a successor after the rotation. So we change the link to now point to be this step is used.

Done on the recursive callback using the return value of the right rotate function. We just finished looking at the case where each node has a reference the left and the right child nodes. But in some bounced binary search tree implementations, it's more convenient for nodes to also have a reference to the parent node. This complicates tree rotations because now instead of updating three pointers, we need to update six pointers. Let's have a look. In this case, where we also have a parent link, every node is in a sense, doubly linked.

We start off with a pointer referencing a and the first thing we'll want to do is also reference node B and node p, so we don't lose them as we shuffle around pointers. Next, we'll adjust the left subtree of a to make a Left pointer reference B's right subtree. Of course, throughout this example, assume B is not null. If you're paranoid, you can add an extra if statement to check for this condition. However, it would be a mistake to assume B's right subtree is not No, we actually have to check against this before setting B's right child's parent to reference a. Next let's make a the right subtree of B.

So set B's right pointer to reference a. Now make A's parent pointer or reference B. The last thing we need to do is adjust the reference to the parent node P. So make B's parent pointer reference P. And now the very last thing I promise is to make peace Left or right pointer reference the successor node B. Notice that we need to check if p is not known because it might not exist. This will be the case for the root node. If we readjust the tree, you will see that we correctly did a right rotation.

There are a lot of steps in doing this right rotation. And it's a very error prone process, which is why I wanted to do it in such detail. In the next video, we'll look at how we can use these tree rotations we just learned about to insert nodes into an ACL tree. Thank you for watching. If you learn something, please like this video, and subscribe for more mathematics and computer science videos. Thank you