Red-black tree (a special self-balanced binary search tree)

Optimized binary search tree for efficient data lookup.

Properties of red-black trees

  1. Each node is either red or black
  2. The root node is black
  3. The leaf nodes are black
  4. Two consecutive red nodes cannot appear
  5. Two children of each red node are black
  6. Insert nodes are red by default

Red black tree play

Gameplay is introduced

  1. A node’s parent becomes its parent
  2. The siblings of a node’s parent are called its uncles
  3. The parent of a node’s parent is called its grandparent

1. Red and black color change

The initial pointer points to the local node. If the father and uncle of the node are both red, the father and uncle change to black, and the grandfather changes to red. The pointer points to the grandfather position, and the operation continues

2. Left turn (to the left)

If this node (my) father and uncle are one red and one black (father is red, uncle is black), if I am the father’s right child, then the left father and I move the first step: my left child to the father to be the right child step 2: I go up step 3: the father comes down

3. Right-handed (right turn)

If the father and uncle of this node are one red and one black (the father is red and the uncle is black), if I am the father’s left child, I will rotate the father and grandfather (the father turns black and the grandfather turns red). Step 1: the father’s right child becomes the grandfather’s left child. Step 2: the father goes up. Step 3: The grandfather goes down