I. Core Characteristics
- Node Color Characteristic
Each node is either red or black.
Example: A newly inserted node is red by default (to reduce impact on balance), and the root node must be black (to ensure the basic stability of the tree).
- Leaf Node Characteristic
All leaf nodes (NIL nodes, i.e., empty nodes) are black.
Example: For a node in a binary search tree that has no child nodes, the NIL nodes pointed to by its left and right pointers are regarded as black, avoiding rule confusion caused by the “empty” state.
- Child Node Characteristic of Red Nodes
If a node is red, both of its child nodes must be black (that is, there are no consecutive red nodes).
Example: If a parent node is red, its left and right child nodes must be black to prevent the tree from tilting due to an excessively long chain of red nodes.
- Characteristic of Black Nodes in Paths
From any node to all its leaf nodes, the number of black nodes contained in the paths is the same (referred to as “equal black height”).
Example: If the number of black nodes in the paths from the root node to all NIL nodes is 3, the tree satisfies this characteristic, ensuring that the longest path does not exceed twice the length of the shortest path.
- Self-balancing Characteristic After Insertion and Deletion
Through rotations (left rotation, right rotation) and color adjustments, all the above characteristics are maintained, ensuring that the height of the tree is always O(log n).
II. Examples Illustrating the Role of Characteristics
Suppose there is the following scenario in a red-black tree:
- After inserting a red node, if its parent node is also red (violating characteristic 3), adjustment through “color change” or “rotation + color change” is required:
- If the uncle node is red, change the parent node and the uncle node to black, and the grandparent node to red (upward transmission may require further adjustment);
- If the uncle node is black, make the parent node become the grandparent node through rotation (such as right rotation) and swap colors to fix the problem of consecutive red nodes.
Through these operations, the red-black tree always satisfies the balance condition that “the longest path does not exceed twice the shortest path”, thus ensuring that the time complexity of search, insertion, and deletion operations is stably O(log n), which is better than the O(n) of ordinary binary search trees in extreme cases.
