2 Red-Black Tree

Widely used in engineering implementation

Course Content#

<5 Balancing Conditions>#

Nodes are either black or red
The root node is black [hair]
Leaf nodes (NIL) are black [not washing feet]
1. Usually not drawn out, and NIL nodes are not considered, default is black
Both children of a red node are black⭐
1. A red node cannot have red children
The number of black nodes on the path from the root node to all leaf nodes is the same⭐

Understanding the Balancing Conditions#

4th + 5th conditions 👉 In a red-black tree, the number of longest edge nodes : number of shortest edge nodes = 2 : 1
- Essentially, red-black trees also control balance by tree height
Red-black trees have looser height control conditions than AVL trees
- Therefore, after inserting or deleting nodes in a red-black tree, the probability of adjustment is lower, reducing adjustment loss
The top-3 conditions are basically trivial; you can color it any way you want, change colors as you wish, NIL is default black
- ❓ If there is no 3rd condition, would red-black trees not be powerful? But isn't it default black?

Adjustment Strategy#

Insertion adjustments and deletion adjustments are separate [unlike AVL trees]

#

①【For insertion adjustments, look at it from the perspective of the grandparent node】

Look down two levels
- When a certain node conflicts with its child node, that node cannot manage it
- "Distant relatives": Grandfather manages the affairs of sons and grandsons, does not allow sons to hit grandsons
The inserted node must be red, based on the 5th condition
- ❌ Inserting black — will definitely require adjustment [will change the number of black nodes on a certain path]
- ✅ Inserting red — may require adjustment
[Purpose of insertion adjustment] Resolve double red situation

②【For deletion adjustments, look at it from the perspective of the parent node】

Look down one level
Preconditions
- Deleting black [refer to binary search tree deletion]
  - Degree 0⭐: Special case [NIL is effective]
    - Will produce a double black NIL node
    - Triggers deletion adjustment
  - Degree 1
    - Its only child must be red; otherwise, that node must have another subtree to ensure the number of black nodes on both sides is equal, which contradicts degree 1
    - Will not trigger deletion adjustment
  - Degree 2: Can be transformed into degree 0 or 1 situation
- Deleting red: does not affect the balance state
[Purpose of deletion adjustment] Resolve double black situation

--> A total of 5 situations: 2 for insertion + 3 for deletion

⭐Key Key⭐ — General adjustment strategy
- Imagine each situation as a local subtree within a large red-black tree
  - The root node may have "ancestor nodes," and other nodes may have subtrees
- To avoid affecting the global structure, the number of black nodes in the local subtree remains the same before and after adjustment
- [Each of the following situations only shows part of the tree]
[PS] If the root node is not black, just color it black [not important]

Insertion Adjustment#

[Goal] Resolve double red situation

Two main categories of situations: 4 + 4 small situations

Situation One#

【Characteristics】 Uncle node is red
【Strategy】
- Modify the small hats of the triplet <15[1, 20]>
  - Black-red-red 👉 red-black-black: Grandfather takes the red hats from the fathers
  - Ensure the number of black nodes on each path remains unchanged
【Illustration】 Red floating up
[PS]
- [In the image] The color of the root node must be black; otherwise, there would be a conflict between the root node and child nodes before insertion, causing imbalance
- Contains 4 small situations: The inserted node x can be in four positions, but the handling method is consistent

Situation Two#

Example: LL

【Characteristics】 Uncle node is black, conflict occurs in LL [two red nodes in L and LL]
【Strategy】
- First use AVL tree's rotation adjustment strategy: LL [example], LR, RL, RR
- Then modify the colors of the triplet: Red floating up [red-black-black] or red sinking down [black-red-red]
【Analysis】 In the image , which nodes are certain [exist + color]? Which are special cases?
- Certain [blue frame defined]
  - LL type → 10, 15
  - Situation two → 25
  - 15 is red → 20
  - The number of black nodes on each path is the same [2] && 10, 15 are red → 5, 13, 19
  - [PS] 4 black nodes can also be NIL
- Special case
  - 17
    - Can be red
    - Can be none, can be black [but cannot be included in the image, otherwise it does not satisfy the 5th condition]
【Illustration】 Big right rotation + red floating up/sinking down
- After the big right rotation of the LL type, the change in the number of black nodes leads to imbalance 👉 use [red floating up/sinking down] adjustment
[PS]
- For the rotation of two red nodes, it does not affect the number of black nodes on each path
  - For small left rotations, small right rotations
  - For example: [original image assumption] holding the 15 node for a small right rotation
  - Therefore, small rotations will not affect balance
- ❗ The position of the inserted node x is the intermediate result of backtracking adjustment, not the state immediately after insertion
- Contains 4 small situations: LL, LR, RL, RR

Deletion Adjustment#

[Goal] Resolve double black situation

Two main categories of situations: Black sibling nodes [2 + 2 + 2 small situations], Red sibling nodes [special cases]

Situation One#

Example: Double black child node on the right side

【Characteristics】 The sibling node of the double black node x is black, and both children of the sibling node are also black
【Strategy】 Increase 1 heavy black on the parent node, reduce 1 heavy black from the double black node and sibling node
[PS] 95 is backtracked [the perspective of the problem needs to be broad]

Situation Two#

Example: RL

[Pay attention to the position of the double black node x, focus on the subtree with 38 as the root node]
【Characteristics】 Sibling node is on the right + the left child of the sibling node is red, and the right child must be black [otherwise judged as RR type, see later]
【Strategy】 Small right rotation, change the original sibling node to red, the new sibling node to black, transforming into RR type [see situation three]
【Analysis】 Which nodes have certain colors? [Small right rotation part]
- [Refer to the original image, blue frame defined for certain colors]
- RL type → 72, 51, 85
- Each path in the subtree with root 38 has the same number of black nodes [2] && 51 is red → 48, 64

Situation Three#

Example: RR

[Pay attention to the position of the double black node x, focus on the subtree with 38 as the root node]
【Characteristics】 Sibling node is on the right + its right child is red [left child has no requirements]
【Strategy】 Big left rotation, the new root node equals the color of the original root node [the parent node of the double black node], the two new child nodes are changed to black, and the double black node reduces 1 heavy black [this order is not critical]
【Analysis】 Which nodes have certain colors?
- [Refer to the original image, blue frame defined for certain colors]
- RR type → 28, 51, 72
- Each path has the same number of black nodes [≈2, 38 is uncertain] && 72 is red → 64, 85
- [PS] 38, 48 are uncertain
【Thought 1】 Color modification strategy
- First, because 48 may be red, to avoid possible conflicts ❗, 38 can only be changed to black
- Next, to ensure that the number of black nodes in the local subtree remains the same before and after adjustment
- ① [2] If 38 was originally red → change 51 to red, 72 to black
- ② [3] If 38 was originally black → change 72 to black
- 【General Method】 The new root node equals the original root's color, and the new child nodes are all changed to black
  - Black-red-red 👉 red-black-black
  - (or)
  - Black-black-red 👉 black-black-black
【Thought 2】 Why solve double black through left rotation?
- After the big left rotation, it can add one more black node on the path where double black is located [adding 51], so double black can be reduced by one
  - Otherwise, reducing double black for no reason, where can we ensure adding one black node to the path

Summary of Situations Two and Three

Situation Two: RL, LR; Situation Three: RR, LL
The sibling node of the double black node is black, and there are red child nodes among the sibling nodes
- RR [sibling node is on the right ➕ its right child is red]
  - Big left rotation, change the new root to the original root's color, change the two new child nodes to black
- RL [sibling node is on the right ➕ its left child is red, and the right child must be black]
  - Small right rotation, change the original sibling node to red, the new sibling node to black, then perform RR strategy
- LL, LR: Similar to RR, RL
Priority: RR > RL, LL > LR

Special Situation#

【Characteristics】 The sibling node of the double black node is red
【Strategy】 Hold the parent node of the double black node, rotate towards the double black node, change the original root node to red, and the new root node to black
【Illustration】 Big left rotation + color swap between original/new root nodes
- The blue frame indicates nodes with certain colors, how are they determined?
  - Special situation → double black node, sibling node
  - 4th condition && sibling node is red → parent node
  - 5th condition && sibling node is red → child nodes of the sibling node [the positions of black nodes thereafter do not need to be continuous]
【After transformation】 Look down from the original root node and perform deletion adjustment
- At this point, the sibling node of the double black node must be black, allowing transition to situations one, two, or three

Code Demonstration#

Insertion Adjustment#

Manual coloring of the root node
- Ensure the 2nd condition: The root node is black
- Under what circumstances can the root node be red
  - The first inserted node [the inserted node is red]
  - Red floating up in situation one
  - Red floating up in situation two [red sinking down does not affect]
- ❗ Only manual coloring will increase the number of black nodes on the path
  - When a big rotation occurs at the root node, the root node will become a red node, at this time manual coloring takes effect
- Encapsulated processing through code: insert = __insert + coloring
❓ Does the lazy operation in situation one affect adjustments during backtracking?
- It will not cause conflicts in the paths below
- Does not affect the number of black nodes on the path
- May cause conflicts in upper nodes
  - But it is a random operation; when the red-black tree reaches a certain scale, the loss can be ignored
❓ Difference between red sinking down and red floating up: each has its advantages, both have the potential for conflict
- Red sinking down: prone to conflict with newly inserted nodes
- Red floating up: prone to conflict with parent nodes
  - [PS] When the red-black tree is large, it is difficult for red nodes to float up
❓ AVL tree vs. red-black tree
- AVL trees are more balanced than red-black trees
- The adjustment cost of red-black trees is lower than that of AVL trees
  - About half of the adjustments in red-black trees can be solved by coloring [situation one]
- Suitable for dynamic insertion and deletion of nodes, while searching may be slightly inferior to AVL
[PS]
- Insertion adjustments occur during the recursive backtracking phase
- In the insertion adjustment code, using goto statements reduces code volume; using function encapsulation should be more standard
[Result Example]

Deletion Adjustment#

Added on the basis of the insertion adjustment code
Deletion adjustment situations are divided into [no double black child nodes] + [with double black child nodes (special cases + three situations (sibling nodes without / with red children <LR, LL, RL, RR>))]
In situations two and three, remember to resolve the double black issue, the order is not critical
When judging LR / RL types, do not directly judge whether the LL subtree is black
- It may be black, or it may be double black
- [Double black] Because LL may be a NIL node, and NIL nodes in memory are shared, their color may be double black
- 【Judgment Transformation】 Judge that the LL subtree is black 👉 not red
Add deletion operation in the main function
[Result Example]
- Demonstrated three situations, results see the list
- NIL is shared in memory, may all be double black

[PS] After the refinement of a generation of captains, it took less than 4 hours to explain red-black trees from scratch, with less than 200 lines of code

In-Class Exercises#

HZOJ-64: Pirate Red-Black Tree#

Sample Input

Sample Output

Based on the final code of the code demonstration part, ① Adjust input and output
② And modify the adjustment strategy for situation one in insertion adjustment [from lazy to not lazy]
- Swap the two parts of the code, first check if a conflict occurs; if there is a conflict, then distinguish between situation one and situation two

Additional Knowledge Points#

⭐ When analyzing adjustment strategies, be clear about which points have certain colors
- Its importance is equivalent to grasping the tree height in AVL tree adjustment strategies
The focus is on the thought process! Not just the adjustment strategy

Tips#

Coding skills are an independent skill set, distinct from algorithm and data structure thinking, so it is not a simple repetition of theoretical knowledge
When you do not treat your time as money, it is difficult to achieve a leap in class
Preview for the next class: Huffman Tree [+ Huffman Coding], String Matching Algorithms [Preview KMP]