Removing nodes from a red-black tree

Использовано изображение портала

In the last article, we examined the rules for forming a red-black search tree and considered the cases of balancing when adding elements.

Now let’s talk about deleting items.
Take, for example, this red-black tree:

Recall that the main property of a red-black tree is the same black height to the left and right of each node. Therefore, in the figures, next to each node, we will indicate the value of the black height, so that at each stage we can check its stability.

Divide and rule

Removing an element from a red-black tree is not such an easy task as it might seem at first glance, so I propose to divide it into several parts and consider each separately.
First, let’s divide the task into two categories:

  • the color of the element to be removed (K and H)
  • the number of children (2, 1 and 0).

As a result, we get a matrix of 6 options: K2, Ch2, K1, Ch1, K0, Ch0.
For each option, the corresponding node of our tree is indicated.
Let’s consider the removal process for each option.

K2 – red knot with two children

The task of removing a node with two children is reduced to the task of removing a node with one or zero children.
To do this, you need to find the closest element that is less or more than the deleted one and swap them.

Please note that when swapping elements, you need to change only the values ​​in the nodes, and leave the color the same, so as not to break the tree structure and not change the black height.
After the exchange, you need to remove the item from its new location. It will be either the rightmost element in the left branch (maximum on the left), or the leftmost in the right (minimum on the right), in any case it will not have one child on the left or right. Thus, the task of removing a node with 2 children is reduced to the task of removing an element with 1 or 0 children:

  • K2 => K1 or K0

Ch2 – black knot with two children

Similar to the previous case, we will give an example of removing the black node 16.

As you can see, after the exchange, the task is reduced to deleting an element with one child:

  • Ch2 => Ch1 or Ch0

K1 – red knot with one child

If the red node does not have one child, then instead of it there is a black NIL element and the black height of the red node is 1. Therefore, on the other hand, the black height should also be 1. But since the red node cannot have a red child colors, then his other child should be black. Since the black height must be 1, it can only be a black NIL element, since in the case of a normal black element, the height will be higher.
Thus, K1 case does not take place.

Ch1 – black knot with one child

If the black element does not have one child, then instead there is a black NIL element with a black height 1. Therefore, on the other side there should be a red node with no children. To remove such an element, it is enough to transfer the value of the red element to the black node, while the black height will be preserved.

K0 – red knot without children

The simplest case. We simply remove the element, replacing it with a NIL reference:

Removing the red element does not change the black height.

CH0 – black knot without children

Removing a black node without children is also very simple: we replace it with a reference to NIL.
Do you think this is almost all? Haha, six times.

After removing the black element, the black height of the subtree changes and you need to balance it for its parent.
The deleted element in the figures is denoted by x, its height – h. When we just start balancing, h = 1, but with recursive calls it can increase.
For definiteness, let us establish that the deleted element was the right child. After removal, its height decreased and became h. Hence, the height of the left son is h + 1. We need to align the heights of the left and right subtrees and make them equal to h + 1.
I suggest dividing the task into several parts again. What options do we have? The parent can be red or black. The left son can also be black or red. And the right son is always black – it was from there that we came to balancing after removal.
There are 6 different cases to consider:

  • KCH1 and KCH2 – the parent is red, the left child is black.
  • CHK3 and CHK4 – the parent is black, the left child is red.
  • HH5 and HH6 – the parent is black, the left child is black.

We will stock up on patience and popcorn, the most interesting and mysterious lies ahead.

КЧ1 – parent red, left child black with black grandchildren

As long as we have the red nodes, we can move and / or recolor them to restore the balance of the black height. In this case, we can lower the red color from the parent to the left son, thus aligning the black height of the parent:

Be sure to double-check from the figure that the black heights of nodes a and b are preserved, and the height of the entire subtree has become the same and equal to h + 1.

KCH2 – parent is red, the left child is black with the left red grandson.

In this case, repainting alone is not enough. We need to make a small turn to the right between nodes 3-7. As a result, we can increase the height of the right subtree to h + 1:

A green node means that it can be either black or red.
Note. If node “1” is black, and “c” is red, then the problem can be reduced to variant HH5.

CHK3 – the parent is black, the left son is red, the right grandson has black great-grandchildren

Having black great-grandchildren allows you to repaint the grandson red and send him to the right subtree by making a small right turn 3-7, and don’t ask why, just trust and check that the black height has stabilized:

Note that red node 5 does not increase the black height.

CHK4 – the parent is black, the left son is red, the right grandson has a red great-grandson

Further into the red forest, there are more black firewoods, and there are less and less red ones, namely, by recoloring the red nodes, it is possible to stabilize the black height.

In this case, you need to make a large left turn, which consists of two small turns 5-3 and 5-7. Node b changed its color from red to black and thus increased its height by 1. Make sure that the black height has stabilized.

HCH5 – the parent is black, the left son is black with the right red grandson.

Fewer and fewer red elements in our subtree, repaint the last red grandson black and make a big left turn, as in the previous case.

Check that the black height of the subtree has stabilized.

HCH6 – the parent is black, the left son is black, his grandchildren are also black

And then came the moment when the red wood ran out. There is nothing to do, you have to paint the black node red and thus equalize the black height of node 7, but not by increasing the black height of the right subtree, but by decreasing the black height of the left subtree. As a result, the black height of our entire structure will decrease by 1 and we must recursively call balancing to the forefathers.

Deletion example with balancing and recursion

We looked at all 6 cases of black height balancing after removing an element from a red-black tree. To get a better feel for how this all works, let’s continue removing node 30 from the original tree.
The first step is to simply delete node 30.
The second step is to launch balancing on its parent – node 25.
The case is HH6:

With grief, we stabilized the height of the node 25 in half.
The third step is balancing at grandfather’s level – for node 20.
To make it more fun and clearer, let’s draw the entire tree before and after balancing. In the case of ChK4:

Notice how the red-black tree changed after balancing, some elements from the left subtree moved to the right, the height stabilized, the element was removed, everyone is happy!

Removing items from a red-black tree is one of the most difficult operations when working with binary search trees. On the course “Algorithms and Data Structures” we consider not only binary search trees, but also many other interesting algorithms, see the course program for details.

Read more:

  • Balancing red-black trees – Three cases

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *