二叉搜索树&AVL树&红黑树

二叉搜索树

性质

二叉搜索树，顾名思义，就是便于进行搜索的二叉树，对于每一个子树来说，其左子树的值必定小于根节点的值，其右子树的值必定大于根节点的值，二叉搜索树的性质如下：

左子树关键字 < 根节点关键字 < 右子树关键字

查找元素的平均时间复杂度是O(log n)，但最坏时间复杂度可以达到O(n)，也就是所有子树只有一个分支。

对二叉搜索树进行一次中序遍历，得到的是一个从小到大的键值排序。

对二叉搜索树进行插入操作时，必定是插入到叶子结点。

查找

基本思路：如果需要查找的键值等于根节点，则更新它；如果小于根节点键值，递归查找左子树；大于同理。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

#define K(n) ((n) ? (n)->key : 0)
#define H(n) ((n) ? (n)->height : 0)
#define L(n) (n->lchild)
#define R(n) (n->rchild)

//树的结构
typedef struct Node {
    ElemType key;
    struct Node *lchild, *rchild;
    int height;
} Node;

//用于比较键值的函数，主要是考虑到可扩展性强，比如稍作修改就能够根据字符串的字典序比较了
int cmp_key(int a, int b) { return a - b; }

Node *get_new_node(ElemType key)
{
    Node *s = (Node *)malloc(sizeof(Node));
    s->height = 1;
    s->key = key;
    s->lchild = s->rchild = NULL;
    return s;
}

//查找函数，如果没有找到返回-1
int search(Node *root, ElemType key,Node *x){
    if(root == NULL)return -1;
    if(cmp_key(root->key, key) == 0){
        (*x) = (*root);
        return 1;
    }
    else if(cmp_key(root->key, key) > 0){
        return search(root->lchild,key,x);
    } else {
        return search(root->rchild,key,x);
    }
}

插入

插入的新结点要么更新现有结点，要么插入到叶节点，代码如下：

Node *insert(Node *root, ElemType key)
{
    if (root == NULL)
        return get_new_node(key);
    if (cmp_key(key, root->key) == 0)
        return root;
    else if (cmp_key(key, root->key) < 0)
        root->lchild = insert(root->lchild, key);
    else {
        root->rchild = insert(root->rchild, key);
    }
    return root;
}

注意：由于插入的结点可能是根节点，所以需要返回这个被修改过的或者更新过的根节点的地址，使该根节点的前一个结点能够存储到它的地址。

删除

删除的操作较为复杂，需要分如下情况讨论：

删除叶子结点：直接删除
删除的结点只有一个分支：将该分支替换待删除的结点
删除的结点有两个分支：寻找该结点的前驱或者后继结点，将该问题转化成问题2（前驱：小于当前结点的最大结点，也就是左子树的最右结点；后继：大于当前结点的最小结点，也就是右子树的最左结点）

下面将以前驱结点替换待删除结点为例，分析第3种删除操作:

insert

初始状态

insert

将根节点替换为前驱结点

insert

像步骤二一样删除前驱结点

能够这样替换的原因是该前驱结点一定比右子树的所有结点键值小（性质1），而且是左子树中键值最大的那个，因此可以放置在该位置。后继结点的替换同理。

代码如下：

//寻找前驱结点
Node *predecessor(Node *root)
{
    Node *temp = root->lchild;
    while (temp->rchild != NULL) {
        temp = temp->rchild;
    }
    return temp;
}

Node *erase(Node *root, ElemType key)
{
    if (root == NULL)
        return NULL;
    if (cmp_key(key, root->key) < 0)
        root->lchild = erase(root->lchild, key);
    else if (cmp_key(key, root->key) > 0)
        root->rchild = erase(root->rchild, key);
    else {
        //没有分支和只有一个分支可以看作是一种情况
        if (root->lchild == NULL || root->rchild == NULL) {
            Node *temp = root->lchild ? root->lchild : root->rchild;
            free(root);
            root = temp;
        } else {
            Node *temp = predecessor(root);
            root->key = temp->key;
            root->lchild = erase(root->lchild, temp->key);
        }
    }
    return root;
}

AVL树

AVL树是建立在二叉搜索树之上的平衡树，它具有以下性质：

性质

继承搜索二叉树的所有性质

对于任意一个结点来说，它的左子树和右子树高度的差值不会超过1

AVL树最坏情况下的查找时间复杂度也只有O(log n)的程度，相较于二叉搜索树大大降低(O(n))

对于性质3，原因在于相同高度下，二叉搜索树最坏只能存储H个结点，而AVL树能够存储至少 $ 1.6^H $个结点。

这里可以根据斐波那契数列的通项公式推导，假设一颗层数为H的AVL树最少存储low(H)个结点，则
$$
low(H) = 1 + low(H - 1) + low(H - 2)
$$
经过推导大约为 $ 1.6^H $个结点。

正是因为每一次的插入和删除都可能破坏AVL树的平衡性（性质2），因此需要对四种失衡类型进行讨论。

失衡类型

主要有以下4种：

在解决平衡性问题之前，还需要引入左旋和右旋的概念。

左旋和右旋

左旋：将右子树的根节点替换当前根节点，同时将右子树的左子树与根节点的右子树交换。

示意图如下：

left_rotate

右旋：将左子树的根节点替换当前根节点，同时将左子树的右子树与根节点的左子树交换。

示意图如下：

right

维持平衡性

以上四种失衡类型中，共有两组平衡方案：

一、 LL型和 RR型

对于LL型失衡，只需要对失衡结点采用右旋操作即可恢复平衡。

LL_right

证明如下：

假设第n个结点的高度为H(n), 则 H(K2) = H(K3) - 2,H(K7) = H(K4) ( - 1) ( 这里表示 K7的高度小于1个 K4 的高度或者两者相等 ) ; 左旋之后，只有两个结点的高度发生了变化，即 K1 和 K3，这时H(K7) = H(K4) ( - 1) = H(K3) - 1 ( - 1) = H(K2) + 1 ( - 1)(注：这里的K3是未旋转之前的 K3，旋转后的 K3用 K3’ 来表示 ), 因此结点K1是平衡的；

再考察结点K3‘，H(K1) = 1 + H(K7) = 1 + H(K4) ( - 1),因此结点 K3’ 也是平衡的。

对于RR型失衡，只需要对失衡结点采用左旋操作即可恢复平衡，在此不再赘述。

二、LR型和 RL型

对于LR型失衡，需要先对失衡结点的左子树进行一次左旋，再对失衡结点进行一次右旋。

证明比较困难，等我读了论文再回来填坑。

RL型失衡进行反向操作。

红黑树

介绍：

红黑树(Red-black tree) 是一种自平衡二叉查找树，它的结构比较复杂，但它的操作有着良好的最坏情况运行时间，它可以在O(log n) 时间内完成查找、插入和删除，这里的n的树中元素的数目。

重要性质

结点是黑色或者红色。

根节点一定是黑色。

所有叶子结点一定是黑色。（用NIL来表示，就是一般二叉树中的NULL结点，不过具有颜色）

每个红色结点必须有两个黑色的子节点（从每个叶子到根的所有路径上不可能有两个连续的红色结点）。

从任一结点到其每个叶子的所有简单路径都包含相同数目的结点。

这些约束保证了红黑树的关键特性：从根节点到叶子节点的最长可能路径不会多有最短可能路径的两倍长。(因为在相同黑色结点的情况下，最长的路径是红黑交替的情况)

准备工作

在理解红黑树的插入和删除操作之前，需要熟悉AVL树中的左旋和右旋操作，这些依然会再红黑树中使用到；除此之外，红黑树还会涉及结点颜色的变化，但总体而言，红黑树插入和删除的最坏时间复杂度相较AVL树降低了，但最坏查找时间会略有增加。

插入

注意：

性质1和性质3总是保持着。

性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。

性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。

插入操作的所有流程如下图：

insert_flow

为什么插入结点默认为红色？

因为如果插入黑色结点，红黑树的平衡一定会被破坏（主要影响性质5），但如果插入红色结点，性质5不会受到影响，并且便于调整，因此一般选择将插入结点初始化为红色。

下面将逐个来分析以上的几种情况：

父亲结点是黑色

可以直接插入，因为不会影响到平衡。

父亲结点是红色

此时插入红色结点将破坏性质4，因此需要根据叔叔结点的颜色再做调整，使红黑树重新达到平衡。

叔叔结点是红色

调整方法如下：

直接将父亲(F)结点和叔叔(U)结点的颜色变为黑色，再将祖父结点(G)的颜色变为红色，这样到达1-5叶子结点的路径上黑色结点个数并没有发生变化(主要分析通过上面三角形的三个顶点的路径)。
叔叔结点是黑色

根据孩子结点的不同，又要分成4中情况：
- LL型和RR型
这种情况很可能并不是直接插入进来的，而是经过其他插入调整后形成的形状，但我们依然要把它调整成平衡的。如上图所示，在对祖父结点进行右旋操作以后，将新的根节点变红，新的左右结点变成黑色，(或者反过来)，因为插入操作并没有破坏性质5，因此在解决掉性质4的冲突以后，红黑树重新达到平衡。RR型变换同理。
- LR型和RL型
这种情况需要先将父亲结点左旋，转化成LL型，再对LL型进行相应操作，可以证明调整后性质5依然是满足的。RL型变换同理。

附上一份代码：

Node *insert_maintain(Node *root){
    if(!has_red(root))return root;
    int flag = 0;
    if(C(L(root)) == 0 && has_red(L(root))) flag = 1;
    if(C(R(root)) == 0 && has_red(R(root))) flag = 2;
    if(flag == 0)return root;

    //uncle is black;
    if(flag == 1 && C(R(root)) == 1){
        if(C(R(L(root))) == 0){
            L(root) = left_rotate(L(root));
        }
        root = right_rotate(root);
    }
    if(flag == 2 && C(L(root)) == 1){
        if(C(L(R(root))) == 0){
            R(root) = right_rotate(R(root));
        }
        root = left_rotate(root);
    }

    C(root) = 0;
    C(L(root)) = C(R(root)) = 1;

    return root;
}

Node *__insert(Node *root, ElemType key){
    if(root == NIL)return get_new_node(key);
    else if(cmp_key(root->key, key) == 0)return root;
    else if(cmp_key(key, root->key) < 0){
        root->lchild = __insert(root->lchild, key);
    }
    else if(cmp_key(key, root->key) > 0){
        root->rchild = __insert(root->rchild, key);
    }
    return insert_maintain(root);
}

Node *insert(Node *root,ElemType key){
    root = __insert(root,key);
    root->color = 1;
    return root;
}

删除

删除操作要比插入更加复杂一些，但主要是对删除后形成的双重黑结点处理。

第一步操作与二叉查找树的删除方法是一样的，如果待删除结点有两个度，则寻找它的前驱或者后继结点替换之，再删除替换点；如果只有一个度（只有叶子结点就任取其中一个作为根节点的度），就将该结点的颜色叠加到根节点（红色+黑色=黑色，黑色+黑色=双重黑），再做第二步调整。

先附上流程图：

d_f1

如果上一步没有产生双重黑结点，则第二步平衡忽略，否则，进入第二步调整，消除双重黑结点。

流程图如下：

d_f2

(真的是很复杂了… …)

下面将根据流程图罗列出的各种情况依次讨论：

如果根节点的孩子结点没有双重黑，则不用处理。

在有双重黑的情况下：

兄弟结点为红色

根据兄弟结点的位置进行相应旋转（在左则右旋，在右则左旋），并且将根节点和兄弟结点颜色互换，这样就转化成了兄弟结点为黑色的情况。

变换以后，到达1~4的路径上的黑色结点个数未改变，可以进行下一步调整。
兄弟结点为黑色
- 兄弟结点的孩子都为黑
  
  将双重黑结点颜色降为黑色，同时其兄弟结点的颜色叠加到根节点。
  
  因为第二层黑色同时降低一层，因此平衡未改变，之后再对根节点降黑。
- 兄弟结点有一个孩子颜色为红
  - LL型和RR型
    
    这里以RR型为例，直接将根节点左旋，然后新的根节点保持与原来根节点一样的颜色（绿色表示颜色未知），新的孩子结点变为黑色。
    
    可以证明，到达1-5路径上的黑色结点数目没有变化。LL型同理。
  - LR型和RL型
    
    以RL型为例，将兄弟结点右旋，并且颜色调整成RR型，就可以重复上面的步骤了。
    
    LR型同理。

至此，红黑树的全部操作就完成了，最后附上删除操作的代码：

Node *predecessor(Node *root) {
    Node *temp = root->lchild;
    while (temp->rchild != NIL) temp = temp->rchild;
    return temp;
}

Node *erase_maintain(Node *root) {
    if (C(L(root)) != 2 && C(R(root)) != 2) return root;
    if (hasRed(root)) {
        int flag = 0;
        root->color = 0;
        if (C(L(root)) == 0) root = right_rotate(root), flag = 1;
        else if (C(R(root)) == 0) root = left_rotate(root), flag = 2;
        root->color = 1;
        if (flag == 1) root->rchild = erase_maintain(root->rchild);
        else root->lchild = erase_maintain(root->lchild);
        return root;
    }
    if (C(L(root)) == 1) {
        C(R(root)) = 1;
        if (!hasRed(L(root))) {
            C(root) += 1;
            C(L(root)) -= 1;
            return root;
        }
        if (C(L(L(root))) != 0) {
            C(L(root)) = 0;
            root->lchild = left_rotate(root->lchild);
            C(L(root)) = 1;
        }
        C(L(root)) = C(root);
        root = right_rotate(root);
        C(L(root)) = C(R(root)) = 1;
    } else {
        C(L(root)) = 1;
        if (!hasRed(R(root))) {
            C(root) += 1;
            C(R(root)) -= 1;
            return root;
        }
        if (C(R(R(root))) != 0) {
            C(R(root)) = 0;
            root->rchild = right_rotate(root->rchild);
            C(R(root)) = 1;
        }
        C(R(root)) = C(root);
        root = left_rotate(root);
        C(L(root)) = C(R(root)) = 1;
    }
    return root;
}

Node *__erase(Node *root, int key) {
    if (root == NIL) return root;
    if (key < root->key) {
        root->lchild = __erase(root->lchild, key);
    } else if (key > root->key) {
        root->rchild = __erase(root->rchild, key);
    } else {
        if (root->lchild == NIL || root->rchild == NIL) {
            Node *temp = root->lchild == NIL ? root->rchild : root->lchild;
            temp->color += root->color;
            free(root);
            return temp;
        } else {
            Node *temp = predecessor(root);
            root->key = temp->key;
            root->lchild = __erase(root->lchild, temp->key);
        }
    }
    return erase_maintain(root);
}

Node *erase(Node *root, int key) {
    root = __erase(root, key);
    root->color = 1;
    return root;
}

数据结构与算法

#二叉搜索树 #AVL树 #红黑树

二叉搜索树&AVL树&红黑树

http://example.com/2023/01/10/二叉搜索树&AVL树&红黑树/

作者

Chen Shuwen

发布于

2023年1月10日

许可协议

计算机系统基础上一篇

二叉树的路径和下一篇