C++ 红黑树的概念、规则与实现

概述

红黑树是一种自平衡的二叉搜索树，通过引入节点颜色（红色和黑色）来维护平衡性。相比 AVL 树，红黑树对平衡的控制较松，旋转次数更少，适合写操作频繁的场景。

1. 红黑树的概念

红黑树的每个节点增加一个存储位来表示节点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。

1.2 红黑树的规则

1. 每一个节点不是红色就是黑色。
2. 根节点是黑色的。
3. 任意一条路径不会有连续的红色节点，也就是说一个节点如果是红色的，那么它的孩子只能是黑色的。
4. 对于任意一个节点，从该节点到其所有叶子节点的简单路径上，必须含有数量相同的黑色节点。

这些性质保证了红黑树的高度不会超过 log₂n，从而确保了良好的性能。

说明： 《算法导论》等书籍补充了一条每个叶子节点 (NIL) 都是黑色的规则。这里所指的叶子节点不是传统意义上的叶子节点，而是空节点，有些书籍上也把 NIL 叫做外部节点。NIL 是为了方便准确地标识出所有路径。

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

由规则 4 可知，从根到叶子节点的每条路径都有相同数量的黑色节点，所以极端场景下，最短路径就是全是黑色节点的路径，假设最短路径长度为 bh (black height)。

由规则 2 和规则 3 可知，任意一条路径不会有连续的红⾊节点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2*bh。

综合红黑树的 4 点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到叶子节点路径的长度为 x，那么 bh <= h <= 2*bh。

1.4 红黑树的效率

假设 N 是红黑树中节点数量，h 最短路径的长度，那么 2h - 1 <= N < 2^(2*h) - 1，由此推出 h ≈ log₂N，也就意味着红黑树增删查改最坏也就是走最长路径 2 * log₂N，那么时间复杂度还是 O(logN)。

红黑树的表达相对 AVL 树要抽象一些，AVL 树通过高度差直观地控制了平衡。红黑树通过 4 条规则的颜色约束，间接地实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的节点，红黑树的旋转次数是更少的，因为它对平衡的控制没那么严格。

2. 红黑树的实现

2.1 红黑树的结构

红黑树与 AVL 树的结构基本上相似，只是 AVL 树中的每个节点的平衡因子改为了红黑树中每个节点的颜色。

// 枚举值表示颜色
enum Colour {
    RED,
    BLACK
};


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

    ( pair<K, V>& kv) : _kv(kv), _left(), _right(), _parent() {}
};

< ,  >
  {
     RBTreeNode<K, V> Node;
:
    
:
    Node* _root = ;
};