“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Properties:

  1. The nodes are red or black.

  2. The root is black.

  3. Every leaf node is a black NIL node.

  4. Every red node has two children that are black. (No two consecutive red nodes on all paths from each leaf to the root)

  5. All paths from any node to each of its leaves contain the same number of black nodes.

Is this a red-black tree?

It looks like it’s true, but it’s not true, and the last property is that all paths from any node to each of its leaves contain the same number of black nodes. The leaf node here refers to NIL node. For example, node 30 has a right NIL leaf node, from 51 to this node passes through 2 black nodes, and the left/right NIL leaf node from 51 to 20 passes through 3 black nodes, which does not meet property 5, so it is not a red-black tree.

add

Generally, the default value of newly added nodes is red, so that the properties of red-black trees can be satisfied as soon as possible. The default value is red, except that property 4 cannot be satisfied immediately. If the root node is added, it is black, obtained by property 2.

The following new additions are red by default

Case 1: The parent node is black

Since the newly added node defaults to red, it still satisfies the red-black tree nature and does not need to make any adjustments to the whole tree.

Case 2: The parent node is red and the uncle node is not red

LL

The parent node is colored black, the grandfather node is colored red, and the grandfather node is right-handed like the LL case of the AVL tree

RR

The parent node is colored black, the grandfather node is colored red, and the grandfather node is left-handed as in the RR case of the AVL tree

LR

This node is colored black, the grandfather node is colored red, and the parent node is left-handed like the LR case of the AVL tree, and the grandfather node is right-handed like the LR case of the AVL tree

RL

This node is colored black, the grandfather node is colored red, and the parent node is right-handed like the RL case of the AVL tree, and the grandfather node is left-handed like the RL case of the AVL tree

Case 3: The parent node is red and the uncle node is red

LL

The parent node is colored black, the grandfather node is colored red, and the uncle node is colored black. If the grandfather’s parent node is red, the grandfather node is added as the newly added red node (similar to case 2).

RR

The parent node is colored black, the grandfather node is colored red, and the uncle node is colored black. If the grandfather’s parent node is red, the grandfather node is added as the newly added red node (similar to case 2).

LR

The parent node is colored black, the grandfather node is colored red, and the uncle node is colored black. If the grandfather’s parent node is red, the grandfather node is added as the newly added red node (similar to case 2).

RL

The parent node is colored black, the grandfather node is colored red, and the uncle node is colored black. If the grandfather’s parent node is red, the grandfather node is added as the newly added red node (similar to case 2).

delete

Case 1: Delete the red node

Delete directly without adjusting

Case 2: Delete the black node

It has two red nodes

Find child nodes instead of deleting

Has a byte dot and is a red node

Directly black the byte point, directly delete the node can be