Hello and welcome back. Today we're going to look at how to insert nodes into an ACL tree in great detail. We'll be making use of the tree rotation technique we looked at in the last video. So if you didn't watch that, simply roll back one video. All right before we get too far, I shouldn't mention what in a vl tree is. An evil tree is one of many types of balanced binary search trees, which allow for logarithmic insertion, deletion and search operations.

Something really special about a vl tree is that it was the first type of Balanced Binary Search Tree to be discovered. Then, soon after a whole bunch of other types of balanced binary search trees started to emerge, including the two three tree the HV escape good tree and the abl trees main rival, the red black tree What you need to know about Next is the property that keeps the abl tree balanced. And this is the balance factor. Simply put, the bounce factor of a note is the difference between the height of the right subtree and the left subtree. I'm pretty sure the bounce factor can also be defined as the left subtree minus the right subtree height, but don't quote me on this. It will also screw up a lot of what I'm about to say, and may also be the reason why you find any inconsistent ideas about what way to do tree rotations on various Google search results pages.

So for consistency, let's keep the balance factor right subtree height minus left subtree height for clarity because people get this wrong or define it differently. The height of node x is calculated as the number of edges between x and the furthest leaf. So if your Tree only has one note, the tree has height, zero, not height one, because there are no edges. That invariant on the abl tree that keeps it balanced is forcing the bounce factor of every node to be either minus one, zero or plus one. The balance factor of a node is anything else, we need to resolve that with tree rotations. In terms of information, we need to store in each node to actually make the AVR tree work.

What we'll need is the actual value the notes stores, this value must be comparable, so we know how to insert it and in what position it goes to the tree. Then we'll also need the balance factor in height of the node as well as the left and the right child pointers. As the algorithm executes, we'll need to update these values. So keep that in mind. So a slider. So Mac, I said that the balance factor of a node must always be minus zero or plus one.

A natural question to ask is, how do we handle the case where this is not true? The answer is that if this is not true, then the factor must either be plus two or minus two, which we can easily handle with tree rotations. The rotations we need to perform depending on the structure of the tree can be broken down into four distinct cases. The first such case is when the tree is what we call a left heavy and there are two left child nodes. This is an easy case to fix because all we need to do is perform a right rotation about the yellow node to balance. The next case is the left right case, where you have a left child But then that node has a right child.

To fix this, you do a left rotation about the left child. So the green one on the leftmost image. What happens then is that this transforms into the left left case we just saw, which we can resolve with a right rotation balance. The third case is the right right case, which is metric to the left left case. So instead of doing a right rotation, we do a left rotation about the green note. Last but not least, is the right left case, which is symmetric to the left right case.

For this case, you would perform a right rotation about the yellow note on the left most image to transform this case into the right right case, and then do a left rotation apply The green note in the middle image. Next, I want to show you some pseudocode for inserting nodes into an ACL tree because it's not all that obvious or easy. This first method is the public facing method for the insert method, which returns true or false depending on whether the value was successfully inserted or not. For simplicity, we're going to ban duplicate values in our HTML tree. So if the value already exists, or the value is no, this method would return false. If the node does not know and it doesn't already exist in the tree, we call our private recursive insert method, where we pass in a pointer to the root node and the value we want to insert.

The private recursive method is also simple. If we hit the base case a null node, we simply return a new instance of the node with the value we want to insert Otherwise, we get a comparative value with the value, we're trying to insert against the current node to determine if we should go on the left or the right subtree. After that, on the recursive callback, we call the update method which updates the bounce factor and height values for this note, and lastly, we rebounds the tree with a bounce method. Now, let's take a look at the update and pass method. And what they're actually doing. The update method updates the bounce factor and height values of our node.

So to calculate the height of the node, we get the maximum height of the left and the right sub trees and then add one. Notice that I initialize the left and the right subtree heights to be minus one. This is because it will cancel out with a plus one with a max function in the case where the node has no subtrees giving the correct height of the seat row four leaf nodes. Lastly, I update the balance factor for this node. By finding the difference between the right subtree and the left subtree heights, the balanced method is slightly more involved but not too crazy. Here we check if our bounce factor has an illegal value of minus two or plus two.

If the bounce factor is minus two, then we know that the node is left heavy. And we dig further into the left subtree. To determine if we're dealing with a left left case or a left right keys, we do a similar thing if the balance factor is plus two, a set we're dealing with the right right or the right left case. If the balance factor is not plus two or minus two, then we know that the bounce factor is going to be either plus one, zero or minus one. And in either of those cases, we don't need to do anything Beside the four cases we might run into. Notice that all we do here are calls to the left rotation and right rotation methods that we saw in the last video.

Also notice that the left right and right left cases, call the left left and right right case methods respectively, since they reduced to those cases after a first rotation. In the last video, we looked at this right rotation method. But since we're dealing with an EDL tree In this video, we actually need to augment that method to update the height and bounce values for the nodes. We're moving around when we do rotations, this is a subtle detail you must not forget Otherwise, your height and balanced factor values will be inconsistent. The left rotation cases metric to this one, so you should be able to figure out pretty easily. And that is all through avh insertions.

In the next video, we'll look at how to remove nodes from an ACL tree. And in the video after that, we'll look at some source code. However, if you're keen to look at some source code right now, you can always check out my GitHub repository where I host all my data structures github.com slash bin slash data structures. Thank you for watching, and if you learn something, please like this video, and subscribe for more mathematics and computer science videos. Thank you