红黑树从概念到手撕实现：平衡树的折中智慧

前言

学完 AVL 树，很多人会有个疑问：既然 AVL 树是'严格平衡'的二叉搜索树，查询效率理论上更高，为什么 C++ STL 的 map/set、Linux 内核里的关键结构偏偏选红黑树？难道'更平衡'反而成了缺点？

其实答案藏在工程取舍里。红黑树的精髓，从来不是比 AVL 树更平衡，而是在'查询效率'和'写入开销'之间找最优解。它不像 AVL 树那样追求极致的矮，而是用'近似平衡'（最长路径不超过最短路径 2 倍）的规则，换来了插入删除时更少的旋转和更低的空间开销。这刚好适配了工程中读写频繁、追求均衡性能的大多数场景。

本文将直接切入核心，从红黑树的 5 条性质讲起，拆解新节点为何默认红色、插入时三种情况如何处理等经典难点，再对比 AVL 树说清选型逻辑，最后附上可运行的手撕代码和验证逻辑。不管是为了面试手撕，还是搞懂底层原理，这篇都能帮你把红黑树的本质嚼透。

红黑树的概念

红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位表示结点的颜色，可以是 Red 或 Black。

红黑树的性质

1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 任何路径没有连续的红节点。
4. 各路径黑节点的个数相同。
5. 每个叶子结点都是黑色的（此处的叶子结点指的是那个空结点）。

这些性质保证了红黑树的最长路径长度不超过最短路径长度的 2 倍。因为一红后面必会跟一黑，且各路径黑节点个数一致。

关于路径的定义：从根节点到空节点算一条路径（默认规则）。路径长度计算时，空节点不算，根节点要算上。

红黑树的增删查改时间复杂度也是 O(logN)，其中 N 是节点个数。空树也可以是红黑树。

AVL 树跟红黑树的比较

AVL 树和红黑树在查找时的性能处于同一量级。但 AVL 树在插入和删除时为了维持严格平衡，旋转次数较多。因此红黑树在各方面更加均衡，虽然不如 AVL 树在纯查找场景下极致，但综合性能更好。如果大量查找且写入极少，AVL 略优；否则红黑树更通用。

红黑树的模拟实现

节点定义与基础结构

enum Colour { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv)
        :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {}
};

template<class K, class V>
struct RBTree {
    typedef RBTreeNode<K, V> Node;
public:
      {
         (_root == ) {
            _root =  (kv);
            _root->_col = BLACK;
             ;
        }

        Node* parent = ;
        Node* cur = _root;
         (cur) {
             (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            }   (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }  {
                 ; 
            }
        }

        cur =  (kv);
        cur->_col = RED; 

         (parent->_kv.first < kv.first) {
            parent->_right = cur;
        }  {
            parent->_left = cur;
        }
        cur->_parent = parent;

        
         (parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
             (parent == grandfather->_left) {
                Node* uncle = grandfather->_right;
                
                 (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }  {
                    
                     (cur == parent->_left) {
                        
                        (grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }  {
                        
                        (parent);
                        (grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    ;
                }
            }  {
                
                Node* uncle = grandfather->_left;
                 (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }  {
                     (cur == parent->_right) {
                        (grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }  {
                        (parent);
                        (grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    ;
                }
            }
        }
        _root->_col = BLACK; 
         ;
    }
:
    Node* _root = ;
};