2 Red-Black Tree

Widely used in engineering implementations

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 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 smaller, reducing adjustment costs
The top-3 conditions are basically trivial; you can dye any color 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 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 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 converted to degree 0 or 1
- Deleting red: does not affect balance
[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 still 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 situation below only shows part of the tree]
[PS] If the root node is not black, just dye it black [not important]

Insertion Adjustment#

[Goal] Resolve double red situation

Two main categories: 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
- Includes 4 small situations: The inserted node x can have 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 causes 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
  - Example: [Assuming the original image] Holding the 15 node for a small right rotation
  - Therefore, small rotations will not affect balance
- ❗ The position of the inserted node x is an intermediate result of backtracking adjustment, not the state immediately after insertion
- Includes 4 small situations: LL, LR, RL, RR

Deletion Adjustment#

[Goal] Resolve double black situation

Two main categories: Brother node is black [2 + 2 + 2 small situations], Brother node is red [special situation]

Situation One#

Example: Double black child node on the right side

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

Situation Two#

Example: RL

[Pay attention to the position of the double black node x, focus on the subtree with root node 38]
【Characteristics】 Brother node is on the right + the left child of the brother node is red, and the right child must be black [otherwise judged as RR type, see later]
【Strategy】 Small right rotation, original brother node becomes red, new brother node becomes black, transforming into RR type [see situation three]
【Analysis】 Which nodes have determined colors? [Small right rotation part]
- [Refer to the original image, blue frame defined as determined color]
- RL type → 72, 51, 85
- The number of black nodes on each path in the subtree with root 38 is the same [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 root node 38]
【Characteristics】 Brother node is on the right + its right child is red [left child is not required]
【Strategy】 Big left rotation, new root node equals the original root node [the parent node of the double black node], the two new child nodes change to black, and the double black node reduces 1 heavy black [this order is not critical]
【Analysis】 Which nodes have determined colors?
- [Refer to the original image, blue frame defined as determined color]
- RR type → 28, 51, 72
- The number of black nodes on each path is the same [≈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 the number of black nodes in the local subtree remains the same before and after adjustment
- ① [2] If 38 was originally red → 51 changes to red, 72 changes to black
- ② [3] If 38 was originally black → 72 changes to black
- 【General Method】 New root node equals the original root's color, new child nodes all change to black
  - Black-red-red 👉 red-black-black
  - (or)
  - Black-black-red 👉 black-black-black
【Thought 2】 Why solve double black with left rotation?
- After the big left rotation, it can add an additional black node on the path where the double black is located [the addition of 51], so the double black can be reduced by one
  - Otherwise, reducing the double black for no reason, where can we ensure an increase in the number of black nodes on the path?

Summary of Situations Two and Three

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

Special Situation#

【Characteristics】 The brother 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 + original/new root node color swap
- The blue frame indicates the nodes with determined colors, how are they determined?
  - Special situation → double black node, brother node
  - 4th condition && brother node is red → parent node
  - 5th condition && brother node is red → child nodes of the brother node [the positions of black nodes thereafter do not need to be continuous]
【After conversion】 Look down from the original root node, perform deletion adjustment
- At this time, the brother node of the double black node must be black, allowing transition to situations one, two, or three

Code Demonstration#

Insertion Adjustment#

Manual dyeing of the root node to black
- 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 will not affect]
- ❗ Only manual dyeing will increase the number of black nodes on the path
  - When a big rotation operation occurs at the root node, the root node will become a red node, at which point manual dyeing takes effect
- Encapsulated processing through code: insert = __insert + dye black
❓ Does the lazy operation in situation one affect adjustments during backtracking?
- It will not cause conflicts on 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
❓ The 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 trees vs. red-black trees
- AVL trees are more balanced than red-black trees
- The cost of adjustments in red-black trees is lower than in 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 search may be slightly inferior to AVL
[PS]
- Insertion adjustments occur during the recursive backtracking phase
- In the insertion adjustment code, the use of 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 situation + three situations (brother nodes with/without 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 are shared in memory, their color may be double black
- 【Judgment Transformation】 Judging that the LL subtree is black 👉 not red
Add deletion operation to 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 Exercise#

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 [no laziness]
- Swap the two parts of the code, first check if a conflict has occurred; 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 determined 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 regard your time as money, it is difficult to achieve a leap in class
Preview for the next lesson: Huffman Tree [+ Huffman Coding], String Matching Algorithms [Preview KMP]