红黑树学习

BST 二叉查找树 -> AVL 平衡二叉树 -> RBT 红黑树

---

二叉查找树

1. 左子树上所有结点的值均小于或等于它的根结点的值
2. 右子树上所有结点的值均大于或等于它的根结点的值
3. 左、右子树也分别为二叉排序树

理想情况下是这样子

存在的问题：如果BST树的节点正好从大到小的插入，此时树的结构也类似于链表结构，这时候的查询或写入耗时与链表相同，最坏时间复杂为线性

这时候就有了平衡二叉树AVL（发明者名字简写）

AVL也属于二叉搜索树的一种，与其不同的是AVL通过机制保证其自身的平衡

平衡二叉树

1. AVL树是最先发明的自平衡二叉查找树
2. 在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树
3. 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树

平衡二叉树的特性

1. 对于任何一颗子树的root根结点而言，它的左子树任何节点的key一定比root小，而右子树任何节点的key 一定比root大

2. 对于AVL树而言，其中任何子树仍然是AVL树

3. 每个节点的左右子节点的高度之差的绝对值最多为1

也就是说，AVL树=BST树+自平衡功能

具体怎么旋转？

记住这四张图就好

那如何删除呢？

1. 叶子节点直接删除，判断平衡进行调整直到根节点
2. 只有左（或右）子树，节点删除，以左（或右）子树替代，判断平衡进行调整直到根节点
3. 删除的节点既有左子树又有右子树，找到其前驱节点（左子树中最大值的节点）或者后驱节点（右子树中最小值的节点）将其替换，判断平衡进行调整直到根节点

缺点：

由于AVL树必须保证左右子树平衡，Max(最大树高-最小树高) <= 1

所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡

正是由于这种严格的平衡条件，导致AVL需要花大量时间在调整上，故AVL树一般使用场景在于查询场景（而不是增加删除频繁的场景）

红黑树：牺牲了部分平衡性，以换取插入/删除操作时较少的旋转操作，整体来说性能要优于AVL树

红黑树

1. 节点非黑即红（颜色属性）
2. 根节点一定是黑色（根属性）
3. 叶子节点（NIL）一定是黑色（叶子属性）
4. 每个红色节点的两个子节点都为黑色（红色属性）
5. 从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点（平衡属性）

RBT使用空间去换时间，在AVL的节点上，增加了颜色属性的数据，换取后面平衡操作的次数减少

红黑树并不是一棵平衡二叉树（见图），但是基于性质5，从任一节点到每个叶子的所有路径都包含相同数目的黑色节点，故 以黑色节点的高度作为约束，RBT的左子树和右子树的层数是相同的

红黑树的平衡称为黑色完美平衡

恢复平衡的三个操作：变色，左旋，右旋

如何维护红黑树：

• 初始状态只有一个黑色节点（同时是根节点和叶子节点）

• 插入新节点：

  因为父节点为黑色的概率较大，默认插入新节点为红色可以避免颜色冲突

  1. 插入节点的Key已经存在：更新当前节点的值为插入节点的值，颜色不变

  2. 插入节点的父节点为黑色：由于节点默认红色，所以可以直接插入而无需做自平衡

     

  3. 插入节点的父节点为红色

     分为两种情况：叔叔节点是红色还是黑色

     如果叔叔节点是红色，则如图变换，再以点P为基点进行自平衡

     

     如果叔叔节点是黑色，如图变换即可

     

     在这里插入图片描述

     

     在这里插入图片描述

     反方向同理

实验代码

#include <iostream>
#include <cstdlib>
using namespace std;

// 颜色枚举，0 表示黑色，1 表示红色
enum Color { BLACK, RED };

// 节点结构体
struct Node {
    int data;          // 节点值
    Color color;       // 节点颜色
    Node* left;        // 左子节点
    Node* right;       // 右子节点
    Node* parent;      // 父节点
};

// 全局变量定义
Node* root = nullptr;  // 红黑树根节点
Node* NIL = nullptr;   // 哨兵节点

// 初始化哨兵节点
void initializeNILNode() {
    NIL = new Node;
    NIL->color = BLACK;
    NIL->left = NIL->right = NIL->parent = nullptr;
}

// 创建一个新节点
Node* createNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->color = RED; // 新插入节点默认为红色
    newNode->left = newNode->right = newNode->parent = NIL;
    return newNode;
}

// 左旋操作
void leftRotate(Node*& root, Node* x) {
    Node* y = x->right;       // 设置 y 为 x 的右子节点
    x->right = y->left;       // 将 y 的左子树移为 x 的右子树
    if (y->left != NIL) {
        y->left->parent = x;  // 更新父指针
    }
    y->parent = x->parent;    // 将 y 的父节点指向 x 的父节点
    if (x->parent == NIL) {
        root = y;             // 如果 x 是根节点，更新根节点
    } else if (x == x->parent->left) {
        x->parent->left = y;  // x 是左子节点
    } else {
        x->parent->right = y; // x 是右子节点
    }
    y->left = x;              // 将 x 设置为 y 的左子节点
    x->parent = y;            // 更新 x 的父指针
}

// 右旋操作
void rightRotate(Node*& root, Node* y) {
    Node* x = y->left;        // 设置 x 为 y 的左子节点
    y->left = x->right;       // 将 x 的右子树移为 y 的左子树
    if (x->right != NIL) {
        x->right->parent = y; // 更新父指针
    }
    x->parent = y->parent;    // 将 x 的父节点指向 y 的父节点
    if (y->parent == NIL) {
        root = x;             // 如果 y 是根节点，更新根节点
    } else if (y == y->parent->left) {
        y->parent->left = x;  // y 是左子节点
    } else {
        y->parent->right = x; // y 是右子节点
    }
    x->right = y;             // 将 y 设置为 x 的右子节点
    y->parent = x;            // 更新 y 的父指针
}

// 修复插入导致的红黑树性质破坏
void fixInsert(Node*& root, Node* z) {
    while (z->parent->color == RED) { // 父节点是红色时可能违反性质
        if (z->parent == z->parent->parent->left) { // 父节点是祖父节点的左子节点
            Node* 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;       // 将 z 移动到祖父节点继续调整
            } else {
                if (z == z->parent->right) { // z 是父节点的右子节点
                    z = z->parent;
                    leftRotate(root, z);    // 左旋转父节点
                }
                z->parent->color = BLACK;    // 父节点变黑
                z->parent->parent->color = RED; // 祖父节点变红
                rightRotate(root, z->parent->parent); // 右旋祖父节点
            }
        } else { // 父节点是祖父节点的右子节点，逻辑对称
            Node* 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(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    root->color = BLACK; // 根节点始终是黑色
}

// 插入一个新节点到红黑树
void insert(int data) {
    Node* z = createNode(data);
    Node* y = NIL;       // 用于记录 z 的父节点
    Node* x = root;      // 从根节点开始搜索插入位置

    while (x != NIL) {   // 找到插入位置
        y = x;
        if (z->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;       // 设置 z 的父节点
    if (y == NIL) {      // 树为空，z 为根节点
        root = z;
    } else if (z->data < y->data) {
        y->left = z;
    } else {
        y->right = z;
    }

    fixInsert(root, z);  // 修复红黑树性质
}

// 中序遍历
void inorder(Node* root) {
    if (root != NIL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

// 主函数
int main() {
    initializeNILNode(); // 初始化哨兵节点

    // 插入节点
    insert(10);
    insert(20);
    insert(15);
    insert(25);
    insert(30);
    insert(5);

    // 中序遍历输出
    cout << "Inorder traversal: ";
    inorder(root);
    cout << endl;

    return 0;
}

---

References

红黑树（图解+秒懂+史上最全）

【动态图文详解，史上最易懂的红黑树讲解】手写红黑树（Red Black Tree）