本文共 2913 字，大约阅读时间需要 9 分钟。

红黑树，作为一种高度平衡的二叉树，具有与AVL树相似的插入和删除操作，但其平衡机制更为灵活。红黑树通过两种主要方式维持高度平衡：重新着色和旋转（左旋、右旋）。在插入操作中，当出现不平衡时，主要通过调整结点颜色来快速恢复平衡，仅在必要时进行旋转。

红黑树插入操作

在红黑树中，插入操作的关键在于保证插入后树的高度平衡。标准的BST插入操作如下：

插入后，新结点设为红色。若新结点是根结点，设其为黑色（提升整棵树的黑高）。若新结点非根结点，需检查其父结点和叔叔结点的颜色：

插入结点 x 的情况分析

1. 父结点 p 某为红色：

• 若叔叔结点 u 为红色：
  • 将 p 和 u 设为黑色。
  • 若爷爷结点 g 不是根结点，设 g 为红色。
  • 将 g 设置为新插入结点，并重复上述步骤。

2. 父结点 p 某为黑色：

• 根据 x、p 与 g 的位置关系（LL、LR、RR、RL），分别执行左旋或右旋，同时调整颜色。

课程操作示例

以下是插入操作的详细案例：

插入结点 2

• 新结点 2 为根结点，设为黑色。

插入结点 6

• 插入到 2 的右子树，2 为黑色，不需调整。

插入结点 9

• 6 为红色，9 插入在 6 的右树，为红色。
• 2 为黑色，需左旋，将 2 的左孩 6 确定为根。

插入结点 10

• 9 为红色，10 插入在 9 的左树，为红色。
• 2 为红色（经过左旋后），需调整颜色和旋转。

插入结点 12

• 10 为红色，12 插入在 10 的右树。
• 检查父母和叔叔颜色，执行相应的旋转。

插入结点 15

• 设为红色，根据父母和叔叔颜色调整。

红黑树实现

结点定义

struct Node {    int data;    bool color;    Node* left;    Node* right;    Node* parent;    Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};

旋转操作

void rotateLeft(Node* root, Node* g) {    Node* p = g->right;    g->right = p->left;    p->parent = g;    if (g->parent == nullptr) {        root = p;    } else if (g == g->parent->left) {        g->parent->left = p;    } else {        g->parent->right = p;    }    p->left = g;    g->parent = p;}void rotateRight(Node* root, Node* g) {    Node* p = g->left;    g->left = p->right;    p->parent = g;    if (g->parent == nullptr) {        root = p;    } else if (g == g->parent->left) {        g->parent->left = p;    } else {        g->parent->right = p;    }    p->right = g;    g->parent = p;}

平衡调整

void fixViolation(Node* root, Node* pt) {    Node* parent_pt = pt->parent;    Node* grand_parent_pt = parent_pt->parent;    while (pt != root && pt->color != BLACK && parent_pt->color == RED) {        parent_pt = pt->parent;        grand_parent_pt = parent_pt->parent;        if (parent_pt == grand_parent_pt->left) {            Node* uncle_pt = grand_parent_pt->right;            if (uncle_pt->color == RED) {                grand_parent_pt->color = RED;                parent_pt->color = BLACK;                uncle_pt->color = BLACK;                pt = grand_parent_pt;            } else {                rotateRight(root, parent_pt);                swapColors(parent_pt, grand_parent_pt);                pt = parent_pt;            }        } else {            Node* uncle_pt = grand_parent_pt->left;            if (uncle_pt->color == RED) {                grand_parent_pt->color = RED;                parent_pt->color = BLACK;                uncle_pt->color = BLACK;                pt = grand_parent_pt;            } else {                rotateLeft(root, parent_pt);                swapColors(parent_pt, grand_parent_pt);                pt = parent_pt;            }        }    }    if (pt->color == BLACK) {        root->color = BLACK;    }}

应用实例

判断红黑树高度平衡

创造如下二叉树：

16      /   \    5     65   /   \   /  \ 32     75 30   1

逐个插入节点，调用 fixViolation 保持植树高度平衡。如上图所示，该树满足红黑树高度平衡条件，最大高度与最小高度差不超过1。

转载地址：http://pxqqz.baihongyu.com/