Better late than never, even if I am five years late. Today we're going to learn about deletion and red-black trees. If you're coming across this video before the others, be sure to watch the rest of the playlist first.
Let's do a quick review on red-black trees. First, a node is either red or black. The root and leaves, or nil nodes, are black. If a node is red, then its children are black. And finally, all paths from a node to its null descendants contain the same number of black nodes.
Let's get into it. Deletion is a little convoluted, but I'll do my best to break it down for you. There will be three main sections of the video. First, we'll cover a helper method called transplant. Transplant helps us move subtrees within the tree and is called by our delete method.
The delete method handles the logic to delete the actual node. And finally there is a delete fixup method which we'll call at the end of delete in order to make sure our tree maintains the properties of a red black tree and all nodes are properly colored. Let's take a look at transplant.
Again, transplant helps us move subtrees within the red-black tree. Here's the code for it. The first if condition is when the parent of U is none. In other words, when U is the root. The second if condition is when U is the parent's left child.
And the else condition is when U is the parent's right child. Let's take a look at the first condition. Again, this is when u is the root.
I'll demonstrate with the tree on the right. For now, I want to completely ignore the color of nodes. Also, I'm intentionally not including any nil nodes, so the slides remain uncluttered.
Let's say we want to delete 15. In this case, the calling code, which we'll look at later, would send 15 as u and 19 as v. We set the root equal to v, and we set v's parent equal to u's parent, which is none. So we remove the connection between 19 and 15. Notice there is no code for updating v's left. This is because updating v.left or v.right is the responsibility of the calling function.
Let's reset and take a look at the second condition. Again, this is when u is the left child. Let's say we want to delete 12. In this scenario, the calling function would pass 12 as u and 13 as v. u's parent is 15. We set u's parent's left child equal to v and we set v's parent equal to u's parent which is 15. Again, updating v's children is the responsibility of the calling function, so we're done.
Now for the third scenario where u is the right child. Let's delete 19. The calling function would pass in 19 as u and 23 as v. u's parent is 15. We set 15's right child equal to v and we set v's parent to u's parent. Again, no updating v's children in this function.
That covers transplant. Let's take a look at the delete function and see where transplant is used. I'll group delete into three cases.
First, when the node we want to delete has a nil left child. Second, when the right child is nil. And lastly, when neither is nil.
Let's look at case 1 and delete 19. We'll call this node z, and I'll explicitly add in the nil node, since it's important here. First, we make note of z's original color, which is black. We label z's right child x.
and call transplant, passing in Z and X. The result of the transplant is the following. Lastly, because the original color was black, we need to call deleteFixUp with nodeX.
We'll ignore the specifics of the method for now, just know that it sets node23 to black. On to case 2 where the right child is nil. For this case, I'm going to add a node to the tree, 1, and we'll delete node 5. Again, we'll make note of the original color and label Z's left child as X.
We call transplant with Z and X. Here's the result of the transplant function. Finally, we call delete fixup with x, since our original color is black.
We're back to a proper red-black tree. Let's look at case 3, when neither child is nil. We'll delete node 12. First, we'll label it z. I'm going to explicitly add nil for 13's right child, since it will be of importance later.
The first step is to find the minimum in Z's right child's subtree. We can see that this is 13, and I'll label that node Y. We'll make note of Y's original color, which is black, and label Y's right child as X. We call transplant, passing in Y and X. The result of transplant is that X moves up into Y's place, and we'll leave y floating for now.
We'll now change some pointers around, setting y's right child to be node 15, and node 15's parent is now y. We call transplant once more, passing in z and y. This time transplant sets the tree's root to y.
Upon returning to the delete function, we fix our pointers. replacing Z with Y. There's one final step since our original color is black. Notice that this is not a proper red-black tree, as the path down to X doesn't have as many black nodes as the other paths. We call deleteFixUp with X, and our coloring is fixed.
In this video, we cover transplant, and three cases for delete. In the next video, I'll unpack the delete fixup method. Be sure to look at the code linked in the description. It covers the exact cases demonstrated in this video. Thank you for watching.
I hope this video helps you on your computer science journey.