红黑树：五大性质、插入调整与颜色翻转的手写实现

#include <iostream>
#include <utility>   // 引入 std::pair
using namespace std;
 
// 枚举值表示颜色：红色、黑色
enum Colour
{
    RED,
    BLACK
};
 
// 红黑树结点：默认按 key/value 结构实现
template<class K, class V>
struct RBTreeNode
{
    pair<K, V> _kv;              // 存放键值对，KV 结构
    RBTreeNode<K, V>* _left;     // 左孩子指针
    RBTreeNode<K, V>* _right;    // 右孩子指针
    RBTreeNode<K, V>* _parent;   // 父亲指针，向上调整时要用
    Colour _col;                 // 结点颜色，红或黑
 
    // 构造函数：初始化各个成员
    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv)                 // 键值对初始化
        , _left(nullptr)          // 左孩子先为空
        , _right(nullptr)         // 右孩子先为空
        , _parent(nullptr)        // 父亲先为空
        , _col(RED)               // 颜色默认给红色，原因后面细讲
    {}
};

#include <iostream>
#include <utility>
using namespace std;
 
enum Colour { RED, BLACK };
 
template<class K, class V>
struct RBTreeNode
{
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;
 
    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr),
          _parent(nullptr), _col(RED) {}
};
 
int main()
{
    RBTreeNode<int, int> cur( make_pair(7, 7) );
    cout << "新结点刚创建时的颜色是: "
         << (cur._col == RED ? "RED(红)" : "BLACK(黑)") << endl;
    // 新结点默认红：为了不破坏"黑高守恒"（性质 4），把新结点默认为红、只可能撞"连续红"（性质 3）
    cur._col = BLACK;   // 一旦需要，我们手动把它染黑（例如根结点）
    cout << "手动染黑后颜色是: "
         << (cur._col == RED ? "RED(红)" : "BLACK(黑)") << endl;
    return 0;
}

// 左旋：以 parent 为旋转点，将其右孩子提升为子树根
void RotateL(Node* parent)
{
    Node* subR = parent->_right;   // subR 为 parent 的右孩子
    Node* subRL = subR->_left;     // subRL 为 subR 的左孩子
 
    // 第一步：parent 的右孩子改为 subRL
    parent->_right = subRL;        // subRL 挂到 parent 的右边
    if (subRL)                     // subRL 可能存在，也可能为空
        subRL->_parent = parent;   // 若存在则更新其父亲为 parent
 
    Node* ppNode = parent->_parent; // 记录 parent 原本的父亲
 
    // 第二步：subR 顶上，接管 parent 的孩子位置
    subR->_left = parent;          // parent 变成 subR 的左孩子
    parent->_parent = subR;        // parent 的父亲改为 subR
 
    // 第三步：把 subR 接到祖父 ppNode 上
    if (ppNode == nullptr)         // parent 原本就是根
    {
        _root = subR;              // 新的根就是 subR
        subR->_parent = nullptr;   // 根的父为空
    }
    else
    {
        if (ppNode->_left == parent)
            ppNode->_left = subR;  // 是祖父的左孩子，则更新祖父左指针
        else
            ppNode->_right = subR; // 否则更新祖父右指针
        subR->_parent = ppNode;    // subR 的父亲设为祖父
    }
}

// 右旋：以 parent 为旋转点，将其左孩子提升为子树根
void RotateR(Node* parent)
{
    Node* subL = parent->_left;    // subL 为 parent 的左孩子
    Node* subLR = subL->_right;    // subLR 为 subL 的右孩子
 
    // 第一步：parent 的左孩子改为 subLR
    parent->_left = subLR;         // subLR 挂到 parent 的左边
    if (subLR)                     // 判空，subLR 可能为空
        subLR->_parent = parent;   // 若存在则更新其父亲
 
    Node* ppNode = parent->_parent; // 记录 parent 原本的父亲
 
    // 第二步：subL 顶上，接管 parent 的孩子位置
    subL->_right = parent;         // parent 变成 subL 的右孩子
    parent->_parent = subL;        // parent 的父亲改为 subL
 
    // 第三步：把 subL 接到祖父 ppNode 上
    if (ppNode == nullptr)         // parent 原本是根
    {
        _root = subL;              // 新根是 subL
        subL->_parent = nullptr;
    }
    else
    {
        if (ppNode->_left == parent)
            ppNode->_left = subL;  // 更新祖父的左指针
        else
            ppNode->_right = subL; // 更新祖父的右指针
        subL->_parent = ppNode;    // subL 的父亲设为祖父
    }
}

#include <iostream>
using namespace std;
 
struct Node
{
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int v) : val(v), left(nullptr), right(nullptr), parent(nullptr) {}
};
 
// 独立版的左旋（演示用，逻辑与红黑树里的 RotateL 一致）
void rotateLeft(Node*& root, Node* parent)
{
    Node* subR = parent->right;
    Node* subRL = subR->left;
    parent->right = subRL;
    if (subRL) subRL->parent = parent;
    Node* pp = parent->parent;
    subR->left = parent;
    parent->parent = subR;
    subR->parent = pp;
    if (pp == nullptr) root = subR;
    else if (pp->left == parent) pp->left = subR;
    else pp->right = subR;
}
 
// 独立版的右旋（演示用，与 rotateLeft 镜像）
void rotateRight(Node*& root, Node* parent)
{
    Node* subL = parent->left;
    Node* subLR = subL->right;
    parent->left = subLR;
    if (subLR) subLR->parent = parent;
    Node* pp = parent->parent;
    subL->right = parent;
    parent->parent = subL;
    subL->parent = pp;
    if (pp == nullptr) root = subL;
    else if (pp->left == parent) pp->left = subL;
    else pp->right = subL;
}
 
void destroy(Node* r)
{
    if (!r) return;
    destroy(r->left);
    destroy(r->right);
    delete r;
}
 
void inorder(Node* r)
{
    if (!r) return;
    inorder(r->left);
    cout << r->val << ' ';
    inorder(r->right);
}
 
int main()
{
    // 构造一棵小 BST：根10，左8，右12；8的左6、右9
    Node* root = new Node(10);
    Node* n8 = new Node(8);
    Node* n12 = new Node(12);
    Node* n6 = new Node(6);
    Node* n9 = new Node(9);
    root->left = n8;   n8->parent = root;
    root->right = n12; n12->parent = root;
    n8->left = n6;     n6->parent = n8;
    n8->right = n9;    n9->parent = n8;
 
    cout << "旋转前          中序遍历: ";
    inorder(root); cout << endl;
 
    rotateLeft(root, root);   // 以根 10 为轴左旋
    cout << "以10左旋后      中序遍历: ";
    inorder(root); cout << endl;
 
    rotateRight(root, root);  // 再以当前根右旋回来
    cout << "再以新根右旋后  中序遍历: ";
    inorder(root);            // 和第一次完全一样，说明旋转不改变中序
    cout << endl;
 
    destroy(root);
    return 0;
}

// 插入一个键值对，成功返回 true；key 已存在返回 false
bool Insert(const pair<K, V>& kv)
{
    // 情况：空树插入
    if (_root == nullptr)
    {
        _root = new Node(kv);      // 新结点成为根
        _root->_col = BLACK;       // 根必须是黑色
        return true;
    }
 
    // 第一步：按二叉搜索树规则查找插入位置
    Node* parent = nullptr;        // 记录当前结点的父亲
    Node* cur = _root;             // 从根开始向下走
    while (cur)
    {
        if (cur->_kv.first < kv.first)   // key 比当前大，往右走
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first) // key 比当前小，往左走
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;          // key 已存在，插入失败
        }
    }
 
    // 第二步：把新结挂到父亲的孩子位置上
    cur = new Node(kv);            // 创建新结点，颜色默认红
    cur->_col = RED;               // 非空树插入必须是红色
    if (parent->_kv.first < kv.first)
        parent->_right = cur;      // 大于父亲，挂在右边
    else
        parent->_left = cur;       // 小于父亲，挂在左边
    cur->_parent = parent;         // 建立父亲指针
 
    // 第三步：修正红黑树性质（核心，下面重点拆解）
    while (parent && parent->_col == RED)   // 父亲是红才需要处理
    {
        Node* grandfather = parent->_parent; // 取出祖父
 
        // 情形一：p 是 g 的左孩子
        if (parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right; // 叔叔是 g 的右孩子
 
            if (uncle && uncle->_col == RED)
            {
                // 叔叔存在且为红 -> 变色，然后继续往上处理
                parent->_col = BLACK;          // p 变黑
                uncle->_col = BLACK;           // u 变黑
                grandfather->_col = RED;       // g 变红
                cur = grandfather;             // 把 g 当作新的 cur
                parent = cur->_parent;         // 继续向上检查
            }
            else
            {
                // 叔叔不存在或为黑 -> 旋转 + 变色
                if (cur == parent->_left)
                {
                    // 左左形态：对 g 做右单旋
                    RotateR(grandfather);      // 以 g 为轴右旋
                    parent->_col = BLACK;      // p 变黑，当新根
                    grandfather->_col = RED;   // g 变红
                }
                else
                {
                    // 左右形态：先 p 左旋，再 g 右旋（双旋）
                    RotateL(parent);           // 以 p 为轴左旋
                    RotateR(grandfather);      // 以 g 为轴右旋
                    cur->_col = BLACK;         // c 变黑，当新根
                    grandfather->_col = RED;   // g 变红
                }
                break;                         // 单旋/双旋后无需继续向上
            }
        }
        else
        {
            // 情形一：p 是 g 的右孩子（与上面完全镜像）
            Node* uncle = grandfather->_left;  // 叔叔是 g 的左孩子
 
            if (uncle && uncle->_col == RED)
            {
                // 叔叔存在且为红 -> 变色后继续往上
                parent->_col = BLACK;          // p 变黑
                uncle->_col = BLACK;           // u 变黑
                grandfather->_col = RED;       // g 变红
                cur = grandfather;             // 上提 g，继续处理
                parent = cur->_parent;
            }
            else
            {
                // 叔叔不存在或为黑 -> 旋转 + 变色
                if (cur == parent->_right)
                {
                    // 右右形态：对 g 做左单旋
                    RotateL(grandfather);      // 以 g 为轴左旋
                    parent->_col = BLACK;      // p 变黑，当新根
                    grandfather->_col = RED;   // g 变红
                }
                else
                {
                    // 右左形态：先 p 右旋，再 g 左旋（双旋）
                    RotateR(parent);           // 以 p 为轴右旋
                    RotateL(grandfather);      // 以 g 为轴左旋
                    cur->_col = BLACK;         // c 变黑，当新根
                    grandfather->_col = RED;   // g 变红
                }
                break;                         // 处理完毕，跳出
            }
        }
    }
 
    _root->_col = BLACK;   // 保险起见，最后把根强制涂黑
    return true;           // 插入成功
}

// 按二叉搜索树规则查找，找到返回结点指针，否则返回空
Node* Find(const K& key)
{
    Node* cur = _root;             // 从根开始
    while (cur)
    {
        if (cur->_kv.first < key)
            cur = cur->_right;     // key 大，向右找
        else if (cur->_kv.first > key)
            cur = cur->_left;      // key 小，向左找
        else
            return cur;            // 找到，返回该结点
    }
    return nullptr;                // 走到空都没找到
}

// 递归检查红黑树性质，blackNum 传引用不方便，这里用传值累加每条路径
bool _Check(Node* root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        // 前序遍历走到空，意味着一条路径走完了，此时统计出 blackNum
        if (refNum != blackNum)
        {
            cout << "存在黑色结点数量不相等的路径" << endl;
            return false;             // 违反性质 4
        }
        return true;                  // 这条路径合法
    }
 
    // 检查连续红：查孩子不方便，反过来查父亲的颜色
    if (root->_col == RED
        && root->_parent != nullptr   // 根结点的父亲为空，需判空
        && root->_parent->_col == RED)
    {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;                 // 违反性质 3
    }
 
    if (root->_col == BLACK)
        blackNum++;                   // 遇到黑结点，当前路径黑结点数加一
 
    // 递归检查左子树和右子树，两条都合法才算合法
    return _Check(root->_left, blackNum, refNum)
        && _Check(root->_right, blackNum, refNum);
}

// 对外验证接口：判断当前树是否是合法的红黑树
bool IsValidRBTree()
{
    if (_root == nullptr)
        return true;                   // 空树当然合法
 
    if (_root->_col == RED)
        return false;                  // 根结点必须是黑，违反性质 2
 
    int refNum = 0;                    // 参考值：一条路径的黑结点数量
    Node* cur = _root;                 // 从根出发，一直往左走
    while (cur)
    {
        if (cur->_col == BLACK)
            ++refNum;                  // 统计最左路径的黑结点数
        cur = cur->_left;
    }
 
    // 以 refNum 为基准，递归检查整棵树
    return _Check(_root, 0, refNum);
}

#include <iostream>
#include <utility>      // std::pair、std::make_pair
using namespace std;
 
enum Colour
{
    RED,
    BLACK
};
 
template<class K, class V>
struct RBTreeNode
{
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;
 
    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr),
          _parent(nullptr), _col(RED) {}
};
 
template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
 
public:
    RBTree() : _root(nullptr) {}
 
    ~RBTree()                      // 析构：释放整棵树的结点，防止内存泄漏
    {
        destroy(_root);
    }
 
    bool Insert(const pair<K, V>& kv)
    {
        // 空树插入：新结点成为根，根必须黑色
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
 
        // 第一步：按二叉搜索树规则找插入位置
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;      // key 已存在
            }
        }
 
        // 第二步：挂上新结点，默认红色
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;
 
        // 第三步：自底向上修正红黑性质
        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
 
            if (parent == grandfather->_left)          // p 是 g 的左
            {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED)
                {
                    // 情况一：叔叔红，只变色，继续上提
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    // 情况二/三：叔叔黑或不存在，旋转 + 变色
                    if (cur == parent->_left)          // 左左：右单旋
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else                               // 左右：左旋+右旋 双旋
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else                                        // p 是 g 的右（镜像）
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)
                {
                    // 情况一（镜像）：叔叔红，只变色，继续上提
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_right)          // 右右：左单旋
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else                                // 右左：右旋+左旋 双旋
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
 
        _root->_col = BLACK;        // 兜底：根永远是黑的
        return true;
    }
 
    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < key)
                cur = cur->_right;
            else if (cur->_kv.first > key)
                cur = cur->_left;
            else
                return cur;
        }
        return nullptr;
    }
 
    // 合法性自检
    bool IsValidRBTree()
    {
        if (_root == nullptr) return true;
        if (_root->_col == RED) return false;
        int refNum = 0;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_col == BLACK) ++refNum;
            cur = cur->_left;
        }
        return check(_root, 0, refNum);
    }
 
    int Height() const
    {
        return height(_root);
    }
 
    void InOrder() const
    {
        inOrder(_root);
        cout << endl;
    }
 
private:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;
        Node* ppNode = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;
        if (ppNode == nullptr)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent) ppNode->_left = subR;
            else ppNode->_right = subR;
            subR->_parent = ppNode;
        }
    }
 
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        Node* ppNode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (ppNode == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent) ppNode->_left = subL;
            else ppNode->_right = subL;
            subL->_parent = ppNode;
        }
    }
 
    bool check(Node* root, int blackNum, const int refNum)
    {
        if (root == nullptr)
        {
            // 走到空 = 一条路径走完，比对黑结点数
            if (refNum != blackNum)
            {
                cout << "存在黑色结点数量不相等的路径" << endl;
                return false;
            }
            return true;
        }
        // 连续红：反过来查父亲
        if (root->_col == RED
            && root->_parent != nullptr
            && root->_parent->_col == RED)
        {
            cout << root->_kv.first << " 存在连续的红色结点" << endl;
            return false;
        }
        if (root->_col == BLACK) ++blackNum;
        return check(root->_left, blackNum, refNum)
            && check(root->_right, blackNum, refNum);
    }
 
    void destroy(Node* root)
    {
        if (!root) return;
        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }
 
    int height(Node* root) const
    {
        if (!root) return 0;
        int l = height(root->_left);
        int r = height(root->_right);
        return (l > r ? l : r) + 1;
    }
 
    void inOrder(Node* root) const
    {
        if (!root) return;
        inOrder(root->_left);
        cout << root->_kv.first << ' ';
        inOrder(root->_right);
    }
 
    Node* _root;
};
 
int main()
{
    // 综合序列：把你的手写红黑树跑出汗
    RBTree<int, int> t;
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    for (auto e : a)
    {
        t.Insert(make_pair(e, e));
        cout << "insert " << e << " -> "
             << (t.IsValidRBTree() ? "OK" : "FAIL") << endl;
    }
 
    t.InOrder();                          // 按 key 有序，证明它仍是合法 BST
    cout << (t.IsValidRBTree() ? "红黑树合法" : "红黑树不合法") << endl;
 
    // 查找每个已插入的数据，都应能找到
    for (auto e : a)
        cout << "Find " << e << ": "
             << (t.Find(e) ? "found" : "not found") << endl;
 
    // 查找不存在的 key
    cout << "Find 100: "
         << (t.Find(100) ? "found" : "not found") << endl;
 
    cout << "9 个结点，树高 = " << t.Height()
         << "（远小于 9，说明近似平衡生效）" << endl << endl;
 
    // 第二组：依次触发 情况一(叔叔红->变色)、情况三(叔叔黑折线->双旋)
    RBTree<int, int> t2;
    int b[] = {10, 5, 15, 3, 4};
    for (auto e : b)
    {
        t2.Insert(make_pair(e, e));
        cout << "[演示] insert " << e << " -> "
             << (t2.IsValidRBTree() ? "OK" : "FAIL") << endl;
    }
 
    // 第三组：依次触发 情况一(叔叔红->变色上提)、情况二(叔叔黑直线->单旋)
    RBTree<int, int> t3;
    int c[] = {20, 10, 30, 5, 3};
    for (auto e : c)
    {
        t3.Insert(make_pair(e, e));
        cout << "[演示2] insert " << e << " -> "
             << (t3.IsValidRBTree() ? "OK" : "FAIL") << endl;
    }
 
    return 0;
}