Welcome back. In this video, we're going to look at how to remove elements from an ACL tree. And what you'll discover is that removing elements from an ACL tree is almost identical to removing elements from a regular binary search tree. So for the majority of this video, we're going to actually be looking at how to remove elements from a binary search tree in other theory and argument that algorithm for ADL trees specifically, so let's get started. So just for review, I want to look at how to remove nodes in a binary search tree in detail. So we can generally break it up into two steps, finding and replacing.

In the find phase you find the element you want to remove from the tree if it exists, and then replace it with a successor node. The successor node is necessary for us to maintain The binary search tree invariant, more details on the interface. This is when we're searching for the element in the tree to see if it exists. And basically four things can happen. First is we hit a null node, in which case we know that the value we're looking for doesn't exist. Our competitor returns the value of zero, meaning we found the node we want to remove, the competitor value is less than zero.

So the value we're looking for, if it exists, is going to be found in the left subtree or the competitor value is greater than zero, in which case the value if it exists, is in the right subtree. So let's do an example of finding nodes in a binary search tree. Suppose we're looking for a 14. Well, we should have a reference to the root node. So this is where we start. So we compare 20 and 14 and we know 14 is less than 20.

So we go into the left subtree. We know if 14 is greater than 10 So we got on the right subtree. We know 14 is less than 15. So you're on the left subtree. 14 is greater than 12. So the right subtree.

And finally there, we found it, the node we were looking for. Now let's see what happens with a node that doesn't exist. So let's try and find 26. So again, we start at the root node, then we go to the right subtree because 26 is greater than 20, then go the left subtree because 26 is less than 31. And once we're at 25, we would go to the right subtree and then discover that 26 does not exist in the tree. So once we find the note, assuming it exists, we need to replace that node with its successor.

The motivation for this is that if we just removed the node without finding a successor, then there'd be a gap in the tree. And when we're looking for successor nodes, one of four cases will happen. Either we're a leaf node, in which case there are no sub trees, the node to remove has no left subtree, the node to remove has no right subtree or the node to remove has both the left subtree and right subtree. We'll see how to handle all these cases. In the first case where the node to remove is the leaf node, we can simply remove it without any side effects. The successor node in this case would be simply a null node.

So suppose we want to remove node eight from this tree, the first thing we do is find out where eight is in the tree. So we go down the tree and then we've found node eight. And we discover that Oh, it's the leaf node, so we can just remove it like so. All right now for cases two and three, where there's only a left Or a right subtree. In these cases, the successor node is the immediate child of that left or right subtree. The reason the successor is the immediate node down from the node we're removing is that it is the next node which is either greater than it the case of right subtree or less than it and the case of a left subtree.

Let's do an example. Suppose we want to remove node nine, the first thing we do is find when no nine is in the tree. So start at the route and code the right subtree and find the node we want to remove which is nine. Then we inspect nine and discover that it only has a left subtree. So the successor note is its immediate child on the left, so seven. So what we do is we get a reference to seven and then get ready to remove nine And then we removed nine and then make seven, the successor by linking it back up to five.

And if we rebalance the tree, that's what it looks like, and no nine has been removed. So the last case, is when the node we're trying to remove has both a left subtree and a right subtree. So the question in this case is in which subtree will we find the successor of the node we're trying to remove? And surprisingly, or not surprisingly, the answer is both. The successor can either be the largest value in the left subtree or the smallest value in the right subtree. Once the successor node has been found in either left or right subtree we replace the value of the node to remove with a value in the successive note.

However, the story doesn't end there. We must not forget To remove the duplicate value of the successor node that still exists in the tree. One common strategy to resolve this is to recursively call the function again, but with the value to remove as the value in the successor node. Let's see an example because this isn't completely trivial. Let's remove node seven from this tree, which is the root node. So we will start at the root node and discover that in fact, this is the node we want to remove and notice that it has two non empty sub trees, so we must choose a successor.

To choose the successor we either pick the smallest value in the right subtree or the largest value in the left subtree. Let's find the smallest value in the right subtree. And to do this, you will go to the right ones and then dig as far left as possible. So now that we found successor node 11 we We would copy its value into the node we're trying to remove, which is the root node seven. Notice that now there are two instances of 11 in our tree, and we want unique values in our tree. So to remove the 11 that is currently highlighted, we would recursively call our remove method, but on the left this time and luckily for us, this will always result in a case one two or three removal.

So to remove 11 we noticed that it only has a right subtree so its successor is its immediate right child. So we stage the removal and get ready to remove 11 that we remove 11 and then hook 14 back up to 18. And if we rebalance the tree then we can see that the duplicate 11 value is gone. All right, the moment we've been waiting How do we augment the binary search tree removal algorithm for ACL trees? The solution is simple. You only need to add two lines of code to ensure that the tree remains balanced and now the bounce factor and height values remain up to date.

On the recursive call back you invoke the update and balance methods you saw in the insert video, which ensure that when the node is removed from the abl tree, that the tree remains pounce, it's as easy as that. We'll have a look at how this is actually implemented code in the next video, so stay tuned for that. You can also find some source code for the Veltri on github@github.com slash William pleasers slash data dash structures. Thank you for watching. If you learned something, please like this video and subscribe for more Computer Science and Mathematics videos.