红黑树学习记录

红黑树性质

红黑树和基本 $AVL$ 不同，不需要频繁进行高度平衡判断，而是使用黑节点的个数，对树型进行维护。

具有以下性质：

每个节点只能是黑、红两种颜色的一种
根节点一定为黑色，外节点看作黑色
不能有两个相连的节点同为红色

从根到任何一个外节点的路径上，黑色节点个数相同

其中 $4$ 性质最为重要，对红黑树的插入、删除更新，都是为满足其性质进行的。

插入

首先需要明确，新插入一个节点时，应该是什么颜色。

考虑如果是黑色，那新节点插入的路径上，黑色个数增加，显然需要向上进行调整，以确保 $4$ 性质的成立，这就增加了额外的操作。

所以新增加的节点，颜色应为红色。

为解释方便，插入部分各节点关系如下：

其中， $0$ 表示左子树， $1$ 表示右子树。

$No$ 为插入的节点，插入时，按照普通二叉查找树的方式进行插入，待新节点插入到位后，再按照以下情况进行调整。

处理过程中，要特别注意对根节点的处理。

这里主要讲解插入节点为左子树的情况，右子树的处理就是其镜像变换，可以通过代码简单描述。

1.0 father为黑

显然，插入后的树满足所有的性质，无需进行更新。

1.1 father、uncle为红

此时，将 $fa,uncle$ 变为黑色， $ffa$ 变为红色。但这种处理可能导致 $ffa$ 出现双红冲突，所以需要继续对 $ffa$ 进行处理（此时 $ffa$ 相当于 $No$ ）。

1.2 father为红，uncle为黑

需注意， $uncle$ 为外节点的话，颜色也是黑色。

1.2.1 fa、No不在同一方向

将 $No$ 左旋，变为 $1.2.2$ 所属情况，同时待处理的节点变为 $fa$ 。

1.2.2 fa、No在同一方向

将 $fa$ 右旋，同时 $fa,ffa$ 颜色互换。

删除

红黑树的删除较为复杂，需针对多种情况进行处理。

此部分的节点关系如下：

其中 $No$ 为待删除的节点。

2.0 No有两个子树

处理方式同二叉查找树，先将 $No$ 和后继 $p$ 交换，然后再进行删除。之后情况便转换为 $2.1、2.2、2.3$ 其中之一。

2.1 No为红色叶节点

直接将 $No$ 删去即可，并不会影响树的性质，此处 $fa$ 为白色，表示其颜色无需考虑（之后同理）。

2.2 No为黑色，且只有一个子树

此时 $No$ 唯一的一个子节点一定是红色，将 $No$ 删除后，用 $fa$ 连接到其子节点，并将子节点颜色改为黑色。

2.3 No为黑色叶节点

2.3.1 br为红色

将 $br$ 左旋，同时 $br,fa$ 颜色互换。之后继续在调整后的树上，对 $No$ 进行调整。

2.3.2 br为黑，远侄子为黑，近侄子为红

此时远侄子一定是外节点，将 $bls$ 右旋，同时 $br,bls$ 颜色互换，情况变为 $2.3.3$ ，之后继续在调整后的树上，对 $No$ 进行调整。

2.3.3 br为黑，远侄子为红

将 $br$ 左旋，同时 $br,fa$ 颜色互换， $brs$ 变为黑色，删除 $No$ 后， $fa$ 左儿子为空。

2.3.4 fa为红，br为黑叶子

$nls,nrs,bls,brs$ 此时全为外节点，将 $No$ 删除， $fa$ 左儿子为空，同时 $fa,br$ 颜色互换。

2.3.5 fa为黑，br为黑叶子

与 $2.3.4$ 处理方式相同，不过处理完 $No$ 后，要将 $fa$ 当成新的待处理节点，继续向上更新。

部分代码

节点结构体

struct Node
{
    /* 存放数据 */
    int data;
    /* 颜色，0红，1黑 */
    int color;
    /* 0左，1右，之后涉及到方向都这么规定 */
    Node *next[2];
    /* 父亲 */
    Node *father;
};

这里将左右子节点的指针放到一个数组中，而不是分别开两个变量，是为了简化后续操作做好准备

旋转

显然，旋转分为左旋和右旋，而不同的旋转，需要操作不同的指针。

但观察旋转方式可以发现，旋转时各指针操作的相对位置是一样的，比如都是保留和自己同方向的子节点，而反方向的子节点接到父节点的同方向。

注意观察，左右子节点的变化规律

因此，借助结构体的定义方式，我们可以通过一个函数，解决所有旋转操作。

/* 将No按照direction反方向旋转 */
/* 如No右旋时，No为左子树，direction=0 */
void rotate(Node *No, int direction)
{
    /* 获取No的父亲和祖先 */
    Node *fa = No->father, *ffa = fa->father;
    /* 对父亲进行更改 */
    No->father = fa->father;
    fa->father = No;
    /* 父亲同方向连接No反方向叶节点 */
    fa->next[direction] = No->next[direction ^ 1];
    /* 注意子树是否存在 */
    if (No->next[direction ^ 1])
        No->next[direction ^ 1]->father = fa;
    /* 父亲变为反方向叶节点 */
    No->next[direction ^ 1] = fa;
    /* 根节点特判 */
    if (!ffa)
    {
        root = No;
        return;
    }
    /* 处理祖先 */
    if (ffa->next[0] == fa)
        ffa->next[0] = No;
    else
        ffa->next[1] = No;
}

查找

想要完成插入或者删除，则必须先有查找。

/* 查找值域为x的节点，找到返回节点，否则返回最后查找失败的叶节点 */
Node *findNode(const int x)
{
    /* 树为空 */
    if (!root)
        /* 返回无效值 */
        return NULL;
    /* 从根开始 */
    Node *No = root;
    while (1)
    {
        /* 去右子树 */
        if (x > No->data)
        {
            if (No->next[1])
                No = No->next[1];
            else
                return No;
        }
        /* 去左子树 */
        else if (x < No->data)
        {
            if (No->next[0])
                No = No->next[0];
            else
                return No;
        }
        /* 找到x */
        else
            return No;
    }
}

插入

插入时，需要先进行查找，如果值存在，则无需插入，否则，在失败叶节点下插入新节点，并对新节点更新。

/* 对No进行更新 */
void insertUpdate(Node *No)
{
    while (1)
    {
        /* getDirection确定No的方向 */
        int direction = getDirection(No);
        /* 处理到根节点 */
        if (direction == -1)
        {
            /* root_color is black */
            No->color = 1;
            return;
        }
        /* 意义同之前的介绍 */
        Node *fa, *ffa, *uncle;
        fa = No->father;
        /* fa黑色，无需处理 */
        if (fa->color)
            return;
        ffa = fa->father;
        /* uncle为fa的反向节点 */
        uncle = ffa->next[getDirection(fa) ^ 1];
        /* 1.1情况 */
        if (uncle && uncle->color == 0)
        {
            /* changeColor改变节点颜色 */
            fa->changeColor();
            ffa->changeColor();
            uncle->changeColor();
            No = ffa;
        }
        /* 1.2情况 */
        else
        {
            /* 1.2.1情况 */
            if (ffa->next[direction] != fa)
            {
                /* 旋转No */
                rotate(No, direction);
                No = fa;
                continue;
            }
            /* 1.2.2情况 */
            rotate(fa, direction);
            fa->changeColor();
            ffa->changeColor();
            return;
        }
    }
}

/* 插入x */
void insert(const int x)
{
    /* 树为空，则直接创建根节点 */
    if (!root)
    {
        root = new Node(x, 1, 0);
        return;
    }
    /* 查找x */
    Node *No = findNode(x);
    /* 建立右子树 */
    if (x > No->data)
    {
        No->next[1] = new Node(x, 0, No);
        /* 对新节点进行更新 */
        insertUpdate(No->next[1]);
    }
    /* 建立左子树 */
    else if (x < No->data)
    {
        No->next[0] = new Node(x, 0, No);
        insertUpdate(No->next[0]);
    }
}

删除

删除操作较为复杂，尤其是删除黑色叶节点，需要注意顺序，一种一种情况去处理。

/* 针对2.0情况，寻找No的后继 */
Node *removeChange(Node *No)
{
    /* Ne是要寻找的后继，初始为No右子树 */
    Node *Ne = No->next[1];
    /* 不断向下，直到Ne没有左子树 */
    while (Ne->next[0])
        Ne = Ne->next[0];
    /* 交换No，Ne */
    No->data = Ne->data;
    /* 将后继返回 */
    return Ne;
}

/* 针对2.3情况，黑叶子删除后的更新 */
void removeblackNode(Node *No)
{
    while (1)
    {
        /* 确定No方向 */
        int direction = getDirection(No);
        /* 处理到根节点为止 */
        if (direction == -1)
        {
            No->color = 1;
            return;
        }
        /* fa，brother(br)意义同介绍 */
        Node *fa = No->father;
        /* br是No反向节点 */
        Node *brother = fa->next[direction ^ 1];
        /* 2.3.1情况 */
        if (brother->color == 0)
        {
            rotate(brother, direction ^ 1);
            swap(fa->color, brother->color);
        }
        /* br为黑色 */
        else if (brother->color == 1)
        {
            /* 2.3.3情况 */
            if (brother->next[direction ^ 1] && brother->next[direction ^ 1]->color == 0)
            {
                rotate(brother, direction ^ 1);
                swap(fa->color, brother->color);
                brother->next[direction ^ 1]->color = 1;
                return;
            }
            /* 2.3.2情况 */
            else if (brother->next[direction] && brother->next[direction]->color == 0)
            {
                swap(brother->color, brother->next[direction]->color);
                rotate(brother->next[direction], direction);
            }
            /* br是黑叶子 */
            else
            {
                /* 2.3.4情况 */
                if (fa->color == 0)
                {
                    fa->changeColor();
                    fa->next[direction ^ 1]->changeColor();
                    return;
                }
                /* 2.3.5情况 */
                else
                {
                    fa->next[direction ^ 1]->changeColor();
                    /* 继续处理fa */
                    No = fa;
                }
            }
        }
    }
}

/* No删除后的更新 */
void removeUpdate(Node *No)
{
    while (1)
    {
        /* 确定No方向 */
        int direction = getDirection(No);
        Node *fa = No->father;
        /* No为叶节点 */
        if (!(No->next[0] || No->next[1]))
        {
            /* 根节点特判 */
            if (No == root)
            {
                root = NULL;
                /* 处理结束 */
                goto removeUpdateEnd;
            }
            /* 2.1情况 */
            else if (No->color == 0)
            {
                fa->next[direction] = NULL;
                goto removeUpdateEnd;
            }
            /* 2.3情况 */
            else
            {
                /* 针对5种情况处理 */
                removeblackNode(No);
                No->father->next[direction] = NULL;
                goto removeUpdateEnd;
            }
        }
        /* 2.0情况，No两个子树 */
        else if (No->next[0] && No->next[1])
            No = removeChange(No);
        /* 2.2情况，No只有一个子树 */
        else
            for (int i = 0; i <= 1; ++i)
                if (No->next[i])
                {
                    /* 注意根节点的特殊处理 */
                    if (fa)
                        fa->next[direction] = No->next[i];
                    if (No == root)
                        root = No->next[i];
                    No->next[i]->father = fa;
                    No->next[i]->color = 1;
                    goto removeUpdateEnd;
                }
    }
removeUpdateEnd:
    /* 更新完成后再删除No */
    delete No;
}

/* 删除值为x的节点 */
void remove(const int x)
{
    /* 查找x */
    Node *No = findNode(x);
    /* 树为空 || 值为x的节点不存在 , 无需处理 */
    if (!No || No->data != x)
        return;
    /* 进行删除和更新 */
    removeUpdate(No);
}

总结

红黑树的代码算是平衡树中比较复杂的，不过虽然看起来代码冗长和复杂，其实就是对之前分析的几种情况的模拟，以上红黑树主要实现部分的代码，删去注释和多余的括号空行后，大概180多行，对于一个复杂的平衡树代码来说，已经算是很正常的了。大部分数据结构的原理都比较简单，代码实现才是难点。