【C/C++】红黑树学习笔记

红黑树

1 基本概念

1.1 定义

红黑树首先是二叉搜索树（左<根<右）；
基本性质：

1. 结点非红即黑；
2. 根/叶子都是黑；
3. 任意节点向下的所有路径上存在黑结点数量一致；
4. 红结点下不能直连红结点；

1.2 基本特性推理

• 最长路径不超过最短路径的两倍；

1.3 对比

与AVL树对比：

1.4 延伸

1.4.1 简单判别是否是红黑树

• 答案：否
  • 如果添加NIL结点，发现某一结点下路径的黑结点数量并不相同

1.4.2 应用

• c++ stl中的map/set 是基于红黑树实现的

2 插入

2.1 插入结点默认红色

• 如果默认黑色，首先就会破坏黑高同原则，调整相对比较麻烦；
• 默认红色，可能破坏不红红原则或根为黑原则，调整相对容易；

2.2 插入结点

如果红黑树性质被破坏，分三种情况调整：

2.2.1 插入结点是根结点

• 违反根为黑原则
• 调整方案：直接变黑

2.2.2 插入结点的叔叔是红色

示例1：插入结点1

调整方案：

• father 和 uncle 变红，grandpather 变黑
• grandfather变为插入结点，继续判断是否违反原则

2.2.3 插入结点的叔叔是黑色

示例：插入结点1

该情况下，uncle可能直观上不存在，但是红黑树默认有NIL结点，是黑的

调整方案：

• 根据不同场景（LL/LR/RR/RL）进行旋转，然后变色

场景分析

LL型

step 1：基于grandfather右旋

step 2：变色

RR型

step 1：基于grandfather进行左旋

step 2：变色

LR型

调整方案：

RL型

调整方案：

3 构建

按照二叉搜索树规则，依次插入结点，并根据插入规则进行调整

4 示例代码

根据算法导论伪代码实现：

#pragma once

#include <iostream>
#include <functional>

enum Color {RED, BLACK};

struct RBNode {
    int key;
    Color color;
    RBNode *left;
    RBNode *right;
    RBNode *parent;
};

class RBTree {
private:
    RBNode *root;
    RBNode *NIL;

    void LeftRotate(RBNode *x) {
        RBNode *y = x->right;
        x->right = y->left;

        if (x->right != NIL) {
            x->right->parent = x;
        }

        y->parent = x->parent;

        if (x->parent == NIL) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }

        x->parent = y;
        y->left = x;
    }

    void RightRotate(RBNode *y) {
        RBNode *x = y->left;
        y->left = x->right;

        if (y->left != NIL) {
            y->left->parent = y;
        }

        x->parent = y->parent;

        if (y->parent == NIL) {
            root = x;
        } else if (y->parent->left = y) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }

        y->parent = x;
        x->right = y;
    }

    void InsertFixup(RBNode *z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                RBNode *y = z->parent->parent->right;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        LeftRotate(z);
                    }

                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    RightRotate(z->parent->parent);
                }
            } else {
                RBNode *y = z->parent->parent->left;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        RightRotate(z);
                    }

                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    LeftRotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

    void Transplant(RBNode *u, RBNode *v) {
        if (u->parent == NIL) {
            root = v;
        } else if (u == u->parent->left) {
            u->parent->left = v;
        } else {
            u->parent->right = v;
        }

        v->parent = u->parent; // if v is nullptr or NIL
    }

    void DeleteFixup(RBNode *x) {
        while (x != root && x->color == BLACK) {
            if (x == x->parent->left) {
                RBNode *w = x->parent->right;

                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    LeftRotate(x->parent);
                    w = x->parent->right;
                }

                if (w->left->color == BLACK && w->right->color == BLACK) {
                    w->color = RED;
                    x = x->parent;
                } else {
                    if (w->right->color == BLACK) {
                        w->left->color = BLACK;
                        w->color = RED;
                        RightRotate(w);
                        w = x->parent->right;
                    }

                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->right->color = BLACK;
                    LeftRotate(x->parent);
                    x = root;
                }
            } else {
                RBNode *w = x->parent->left;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    RightRotate(x->parent);
                    w = x->parent->left;
                }

                if (w->right->color == BLACK && w->left->color == BLACK) {
                    w->color = RED;
                    x = x->parent;
                } else {
                    if (w->left->color == BLACK) {
                        w->right->color = BLACK;
                        w->color = RED;
                        LeftRotate(w);
                        w = x->parent->left;
                    }

                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->left->color = BLACK;
                    RightRotate(x->parent);
                    x = root;
                }
            }
        }

        x->color = BLACK;
    }

    RBNode* Minimum(RBNode *node) {
        while (node->left != NIL) {
            node = node->left;
        }

        return node;
    }

public:
    RBTree() {
        NIL = new RBNode{0, BLACK, nullptr, nullptr, nullptr};
        root = NIL;
    }

    ~RBTree() {
        std::function<void(RBNode *)> deleteNode = [&](RBNode *node) {
            if (node != NIL) {
                deleteNode(node->left);
                deleteNode(node->right);
                delete node;
            }
        };

        deleteNode(root);
        delete NIL;
    }

    void Insert(int key) {
        RBNode *z = new RBNode{key, RED, NIL, NIL};
        RBNode *y = NIL;
        RBNode *x = root;

        while (x != NIL) {
            y = x;
            if (z->key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        z->parent = y;
        if (y == NIL) {
            root = z;
        } else if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }

        InsertFixup(z);
    }

    void Remove(int key) {
        RBNode *z = root;
        while (z != NIL && z->key != key) {
            if (key < z->key) {
                z = z->left;
            } else {
                z = z->right;
            }
        }

        if (z == NIL) {
            return;
        }

        RBNode *y = z;
        RBNode *x;
        Color yOriColor = y->color;

        if (z->left == NIL) {
            x = z->right;
            Transplant(z, z->right);
        } else if (z->right == NIL) {
            x = z->left;
            Transplant(z, z->left);
        } else {
            y = Minimum(z->right);
            yOriColor = y->color;
            x = y->right;

            if (y->parent == z) {
                x->parent = y;
            } else {
                Transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }

            Transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        delete z;

        if (yOriColor == BLACK) {
            DeleteFixup(x);
        }
    }

    void Inorder() {
        InorderHelper(root);
        std::cout << std::endl;
    }

    void InorderHelper(RBNode* node) {
        if (node != NIL) {
            InorderHelper(node->left);
            std::cout << node->key << " (" << (node->color == RED ? "R)" : "B)") << " ";
            InorderHelper(node->right);
        }
    }
};