C语言_串匹配算法

发表于2024-02-14更新于2024-02-19阅读次数

串的匹配

串的匹配就是从大的字符串中找到字串，并且返回第一个字串的位置。

C语言库函数有一个strstr，是朴素的串匹配算法，也叫BF算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int BF(string source, string pattern)
{
    int i = 0;
    int j = 0;
    while(i < source.size() && j < pattern.size())
    {
        if(source[i] == pattern[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;//后退j个字符，再进1
            j = 0;
        }
    }
    if(j == pattern.size())//如果pattern的j走到了最后，则说明已经全部匹配
    {
        return i - j;
    }
    return -1;
}

KMP算法

是一个升级版的串匹配算法，名字取自三个人名（Knuth-Morris-Pratt）。

总地来说，KMP的核心效果就是让原串的指示器不用退回。如何达到这个效果？就是考虑和模式串已经匹配的部分。这一部分模式串的子串，如果后缀有和前缀相重复的部分，则就可以跳过这些部分，即跳过前缀，在前缀的后一个字符开始再次比对（实际操作中，原串指示器不动，而是模式串的指示器回退到当时子串前缀的后一个字符位置）。

于是，整个问题的核心，就从关注原串变到关注模式串本身了。需要找到模式串的不同长度（起点一致，不能从中间分割）下子串的前缀后缀相等的前缀（后缀）最大长度，从而建立一个所谓的next数组。

这个next数组，教科书的求法是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int * getNext(string str)
{
    int * next = new int[str.size()];
    
    int j = 0;   // j 用来遍历子串
    int k = -1;   // k 用来表示公共前后缀的长度
    next[0] = -1; // 表示，当第0个字符都已经匹配失败了，则原串前进1，模式串位置给-1，前进1后自然地（巧妙处理）到0位置。
    while(j < str.size() - 1)//size不包括\0，即不处理最后一位字符位置
    {
        if(-1 == k || str[j] == str[k])
        {
            ++j;
            ++k;
            next[j] = k;
        }
        else
        {
            k = next[k];     //如果在找相同的后缀失配，同样也可以使用KMP的思想，在已匹配的这部分字符串中找相同的前后缀部分，从而去回溯k！比如：如果没有相同前后缀，则k为0
            // 这里巧妙地复用了next数组，因为在推进k的过程中，观察的也是这个模式串的一部分，所以可以使用此next作为前缀的next！
        }
    }
}
int KMP(string source, string pattern)
{
    int i = 0;
    int j = 0;
    int * next = getNext(pattern);//add
    while(i < source.size() && j < pattern.size())
    {
        if(source[i] == pattern[j])
        {
            ++i;
            ++j;
        }
        else// modify
        {
            j = next[j];   
        }
    }
    if(j == pattern.size())//如果pattern的j走到了最后，则说明已经全部匹配
    {
        return i - j;
    }
    return -1;
}

上面这个求next数组的代码虽然看起来很简洁，但要彻底理解，还是比较难的，因为代码的细节处理得很巧妙，其中k = next[k]更是复用了KMP的next数组思想。
这个求getNext的函数可以优化，避免模式串中重复的字段：见ShiLei算法180节
比如：abcabc的next数组如果没有优化，则会成为-1 0 0 0 1 2，而经过优化以后：-1 0 0 -1 0 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int * getNext(string str)
{
    int * next = new int[str.size()];
    
    int j = 0;   // j 用来遍历子串
    int k = -1;   // k 用来表示公共前后缀的长度
    next[0] = -1; // 表示，当第0个字符都已经匹配失败了，则原串前进1，模式串位置给-1，前进1后自然地（巧妙处理）到0位置。
    while(j < str.size() - 1)//size不包括\0，即不处理最后一位字符位置
    {
        if(-1 == k || str[j] == str[k])
        {
            ++j;
            ++k;
            // 优化：如果发现此时k的位置字符和j的字符一样，则说明遇到了重复的字段，则继续进行回退，就省去了在kmp处理中多余的回退。
            if(str[k] == str[j])
            {
                next[j] = next[k];
            }
            else
            {
                next[j] = k;
            }
        }
        else
        {
            k = next[k];     //如果在找相同的后缀失配，同样也可以使用KMP的思想，在已匹配的这部分字符串中找相同的前后缀部分，从而去回溯k！比如：如果没有相同前后缀，则k为0
            // 这里巧妙地复用了next数组，因为在推进k的过程中，观察的也是这个模式串的一部分，所以可以使用此next作为前缀的next！
        }
    }
}

还有一个更直白的找模式串子串的前后缀最大长度的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int PMT[50] = {0};
void init_pmt(char const * pattern)
{
    int len = strlen(pattern);
    char sub[50] = {'\0'};
    for(int i = 1; i <= len; ++i)
    {
        strncpy(sub, pattern, i);
        sub[i] = '\0';
        char prefix[50] = {'\0'};
        char suffix[50] = {'\0'}
        for(int j = 1; j <= i - 1; ++j)
        {
            strncpy(prefix, sub, j);
            prefix[j] = '\0';
            strcpy(suffix, sub + i - j);
            if(strcmp(prefix, suffix) == 0)
            {
                PMT[i - 1] = j;
            }
        }
    }
}
int kmp(char const * source, char const * pattern)
{
    //i 指示 原串，j指示模式串
    int i = 0, j = 0;
    while(source[i] && pattern[j])
    {
        if(source[i] == pattern[j])
        {
            ++i;
            ++j;
        }
        else //仅仅是这里与BF不一样。
        {
            // 首位不相等，i进1
            if(j == 0)
            {
                ++i;
            }
            else// 除了首位不相等j归0外，其他情况为回退j，回退多少？查表
            {
                j = PMT[j - 1];// j - 1是已匹配了的最后位置
            }
        }
    }
    if(pattern[j] == '\0')//如果j移到了最后，说明已经匹配到
    {
        return i - j;//返回的是原串中 匹配到的模式串的起始位置
    }
    return -1;
}

image-20240320015452152

Bayer Moore

坏字符

每次把目标字符串和原字符串从后往前比较，如果某位置对应不上，则原字符串的这个字符称为“坏（bad）”字符。需要在目标字符串从后往前继续寻找（已经在之前匹配上的字符跳过）与这个bad字符相等的字符，然后按照这个相等字符的位置与原字符串的坏字符位置对齐（后移目标字符串）；如果在目标字符串中没找到坏字符，则把目标字符串整体后移到坏字符位置的下一个位置。对齐之后，重新把目标字符串和原字符串从后往前比较。

找匹配串中下一个坏字符，需要告诉：当前坏字符是什么（原串中的字符），当前坏字符位置在哪（模式串中的下标值），以及目标串指针。即从匹配串中的坏字符的位置的前一个位置开始找下一个相同的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int next_bad(char bad, char const * pattern, int wherebad)
{
    // pattern串中从后往前找与原串的坏字符相同的字符，从哪里坏的位置的前一个开始
    // 若未找到字符则i = -1自然退出
    int i = -1;
    for (i = wherebad - 1; i >= 0; --i)
    {
        if (pattern[i] == bad)
        {
            break;
        }
    }
    return i;
}

好后缀

在模式字符串从后往前与原串一一匹配的过程中，遇到了坏字符，那么坏字符之后的，即已经匹配上了的在后面的部分串称之为好后缀。那么，我们可以去寻找模式字符串中还是否存在好后缀。如果存在，则可以让模式字符串的下一个好后缀与原串的当前位置的好后缀对齐，从而达到让模式串快速前进。

好后缀的思想很类似于KMP算法，即找公共前后缀，让重复的前缀对齐原串的后缀位置。但是区别就在于，BM算法是从后往前去匹配的，找到好后缀的同时，顺带着也找到了坏字符的位置。

下一个坏字符与原串当前坏字符对齐，或者下一个好后缀与原串当前好后缀对齐，模式字符串前进的步数会不一样，那么，就可以去对比哪个可以前进得更多。

那么，类似于KMP地，去聚焦于模式字符串本身，不同点在于，每次寻找后缀都是从右向左寻找最近的下一个好后缀。（如果找的不是最近的而是靠左的下下个好后缀的话，那么模式字符串在BM算法前进过程中就会步子迈大了，跳过了可能完全成功匹配的机会）

去建立一个SUFFIX_TB表格，下标值i代表此位置开始的后缀字符串，内容值SUFFIX_TB[i]代表左边下一个最近的好后缀的下标位置。
SUFFIX_TB表格起初把全部值初始化为-1。表示当前i位置时没找到下一个好后缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int SUFFIX_TB[50] = {0};
void init_suffix(char const * const pattern)
{
    int pattern_len = strlen(pattern);
    char sub[50] = {'\0'};
    
    for(int i = 0; i < 50; ++i)
    {
        SUFFIX_TB[i] = -1;
    }
    // i指示的是后缀的起始位置，从第1个下标位置开始找
    for(int i = 1; i < pattern_len; ++i)
    {
        // 当前要找的好后缀为 i下标位置开始到最后 
        strcpy(sub, pattern + i);
        // 从好后缀开始的位置（i下标）的上一个开始，从右向左比较，因为要找最近的
        for(int j = i - 1; j >= 0; --j)
        {
            // sub是要找的好后缀。pattern + j是要对比的字符串的起始位置，他们的长度都应为pattern_len - i
            if(strncmp(sub, pattern + j, pattern_len - i) == 0)
            {
                // 找到从右往左的最近的下一个好后缀，更新表格。i代表此位置开始的后缀字符串。j代表下一个好后缀的起始位置。
                SUFFIX_TB[i] = j;
                // 不要忘记break！如果不break继续找的话，左边可能有另一个完全匹配的好后缀，会覆盖掉
                break;
            }
        }
    }
}

封装到next_good函数，参数只需要一个wherebad，即坏字符的位置（模式串中的下标值），那么就可以确定好后缀的位置了（即坏字符的下一个位置）。

1
2
3
4
int next_good(int wherebad)
{
    return SUFFIX_TB[wherebad+1];
}

实现BM算法

每次比较选择坏字符和好后缀哪个可以让模式字符串走的更远。参数一个原串指针，一个模式串指针。返回值为匹配成功后，原串中目标子串的起始下标值。如果没找到则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int boyer_moore(char const* const source, char const* const pattern)
{
    init_suffix(pattern);
    int src_len = strlen(source), pattern_len = strlen(pattern);
    // 因为BM是从后往前比对的，因此，初始值都是 模式串 最后位置的下标值-1
    int i = pattern_len - 1, j = pattern_len - 1;
    // 循环寻找目标串的条件是 原串i 没到结尾
    // 这个循环处理的是i，即只要遇到失配的情况，则i前进，j重新对齐下一个位置进行再次一一匹配。
    while (i < src_len)
    {
        // 这个循环处理的是j。只要模式串j和原串i位置的字符相等，则j和i同时左移1。同时j的值需要大于等于0。
        while (source[i] == pattern[j] && j >= 0)
        {
            --i;
            --j;
        }
        // 如果退出了小while循环，则有两种情况
        //情况1： j < 0, 说明模式串j走到最左，则完全匹配。此时i位置处在目标子串开始的前一个位置。则结果应返回i+1
        if (j < 0)
        {
            return ++i;
        }
        //情况2： 此时出现失配，即原串的i位置字符失配。
            // 参数：当前坏字符是什么（原串中的字符）；目标串指针；当前坏字符位置在哪（模式串中的下标值）
        int next_bad_index = next_bad(source[i], pattern, j);
        int next_good_index = next_good(j);
        // 对比这两个值。选择哪个？

        // 如果坏字符、好后缀都没找到      0  0 模式串起始点重新对齐到i的下一个位置，i再挪到最后
        // 如果没找到坏字符，找到了好后缀  0  1 由于没找到坏字符，则有好后缀也没意义了，所以与0 0一样：模式串起始点重新对齐到i的下一个位置，i再挪到最后
        // 如果找到了坏字符，没找到好后缀  1  0 虽然好后缀是-1，看起来可以跳过很多，但是！由于存在坏字符，不能一下略过去，所以不能选择好后缀。要选择坏字符位置值
        // 
        // 总结：只要有一个没找到，则二者最小值为 -1。模式串起始点都是重新对齐到i的下一个位置

        // 如果找到了坏字符，找到了好后缀   1  1
            // 再次分情况：看next_good和next_bad谁值小，选谁。
        //总结：取二者最小值。
            //如果是好后缀则将相当于可以把模式串后移j - next_good + 1。
            //如果是坏字符则将相当于可以把模式串后移j -  next_bad。
                //如果两个都是最小值。即相等，则优先选择好后缀，因为对齐时，好后缀比坏字符更能多进1位。
                //如果最小值为-1，则模式串起始点重新对齐到i的下一个位置
        if (next_bad_index == -1 || next_good_index == -1)
        {
            if (next_bad_index == -1)
            {
                i += j + 1;
            }
            else if(next_good_index == -1)
            {
                i += pattern_len - 1 - next_bad_index;
            }
        }
        else if (next_bad_index < next_good_index)
        {
            //i += pattern_len - 1 - j + j - next_bad_index;
            i += pattern_len - 1 - next_bad_index;
        }
        else if (next_good_index <= next_bad_index)
        {
            i += pattern_len - 1 - next_good_index + 1;
        }
        j = pattern_len - 1;
    }
    return -1;
}

测试

1
2
3
4
5
6
int main()
{
    int res = boyer_moore("GATTGCTAGATTAACTATACTAA", "CTATACTA");
    return 0;
}
// 结果：14

总结来说，

  1. 如果坏字符、好后缀都找到了。那么取最小值作为下一个的对齐点。
    1. 如果二者相等，则优先取好后缀。因为模式字符串重新对齐时，好后缀比坏字符更能多进1位。
  2. 如果至少有一个没找到：
    1. BM算法最大的易错点：如果找到了坏字符而没找到好后缀，则必须去对齐坏字符。因为好后缀有时候找不到是很正常的。如果跳过了这个坏字符，那么就会忽略中间的情况！
    2. 如果找到了好后缀而没找到坏字符，则忽略这个好后缀。因为模式串中根本就没有下一个坏字符，你去对齐好后缀是没意义的！所以，没找到坏字符就相当于二者都没找到！见2.3。
    3. 如果都没找到，则模式串起始点重新对齐到当前原串指示位置i的下一个位置（实际上是调整i的值来做到对齐），j再挪到模式串的最后，重新从后向前一一匹配！

实际的场景

线上项目涉及到数据搜索、字符串匹配，如果数据量很大时，应用最多的其实是字典树、倒排索引的数据结构。例子：百度搜索、开源的Lucene、ElasticSearch（ElasticSearch是一个基于Lucene构建的开源项目）

1
2
3
4
5
6
7
8
9
Lucene 和 Elasticsearch（ES）都主要基于倒排索引（Inverted Index）进行高效率搜索。

倒排索引是一种数据结构，用于快速查找包含特定词条（term）的文档。它将文档中的每个词条映射到包含该词条的文档列表，这样的索引结构使得搜索过程能够快速定位到包含特定词条的文档，而无需扫描整个文档集合。

在倒排索引中，每个词条都关联着一个包含该词条的文档列表（称为倒排列表），并且可以附加一些额外的信息，如词频、位置等。这使得搜索引擎可以快速定位到满足查询条件的文档，并根据相关度进行排序。

Lucene 是基于 Java 编写的搜索引擎库，提供了倒排索引的实现和管理功能，开发人员可以使用 Lucene 来构建自己的搜索引擎或搜索功能。而 Elasticsearch 是一个基于 Lucene 构建的分布式搜索和分析引擎，它使用 Lucene 的倒排索引作为核心数据结构，同时提供了分布式存储、查询和分析等功能，使得用户可以轻松地构建和管理大规模的搜索应用。

因此，倒排索引是 Lucene 和 Elasticsearch 实现高效率搜索的关键数据结构之一。

字典树

字典树是指基于树的一种数据结构，用于以一种能够高效搜索、插入和删除操作的方式存储一组键（通常是字符串）。Trie树（又称prefix tree）和三叉搜索树（Ternary Search Tree，又称T-tree、T树）是字典树的具体实现，各自具有其特点和优势。

  1. Trie树（前缀树）特别适用于需要进行前缀匹配和检索的任务，例如字典实现和自动完成系统。
  2. T树（三叉搜索树）在空间效率和快速字符串搜索操作之间提供了平衡。它们也适用于字典实现以及拼写检查和近似字符串匹配等任务。

总之，虽然Trie树和三叉搜索树是不同的实现，但它们都属于字典树类别，用于高效存储和检索键-值对，尤其是字符串。

其他树

B树

B树的全名是“Bayer–McCreight B树”。这是一种由Rudolf Bayer和Edward M. McCreight于1972年引入的数据结构。B树的名称来自于这两位作者姓氏的首字母。B树被广泛应用于数据库和文件系统中，用于高效地存储和检索数据，尤其是在处理大型数据集和基于磁盘的存储时。

T*树

T*树是B树数据结构的一种变体，旨在提高范围查询的性能，例如查找在给定范围内的所有值，与传统的B树相比。

在T*树中，每个节点可以有不同数量的子节点，通常范围在d​到2d\sqrt d​到2d之间，其中dd是树的最大度数。这允许更灵活地平衡树，并且可以使得树的高度相比传统的B树更浅，尤其是对于大型数据集而言。

T*树通过在其内部节点中存储额外的摘要信息来实现高效的范围查询性能，例如存储在其子树中的键的聚合值或范围。这样在范围查询期间可以更快地遍历和修剪不必要的子树。

总的来说，T*树旨在在保持B树的优点，如高效的插入、删除和搜索操作的同时，提供改进的范围查询性能。它们在数据库系统和其他需要高效范围查询的应用中被广泛使用。

B*树

B*树是B树的一种改进版本，旨在减少节点的分裂和合并操作，从而减少树的高度，提高查询性能。
与普通的B树不同，B*树在节点填满时不会立即进行分裂，而是等到达到阈值时才分裂，这样可以减少分裂的频率，减小树的高度。

B*树还通过在非叶节点中保留更多的键来减少合并操作的频率，从而进一步减小树的高度。

虽然B*树和T*树都是B树的变体，但它们的设计目标和实现方式略有不同。B*树的重点是减少树的高度，而T*树的重点是提高范围查询的性能。

C语言_树

发表于2024-01-26更新于2024-02-14阅读次数

BST（Binary Search Tree，二叉搜索树）

Binary Search Tree，二叉搜索树，也称为二叉排序树。
BST（二叉搜索树）具有以下性质：

  1. 有序性：对于任意节点，其左子树中所有节点的值均小于该节点的值，右子树中所有节点的值均大于该节点的值。
  2. 递归结构：左子树和右子树本身也是BST。
1
2
3
4
5
6
struct _TreeNode{
    unsigned key;
    char val;
    struct _TreeNode * left;
    struct _TreeNode * right;
}

例如下图的树就是一个BST：

性质

  1. 可以发现，BST树不一定是完全二叉树。
  2. 关于前、中、后序遍历的有序性：
    • 中序遍历（左 → 根 → 右）的结果是升序有序序列。这是由BST的性质直接保证的。
    • 前序遍历（根 → 左 → 右）和后序遍历（左 → 右 → 根）的结果通常不是有序序列。仅在某些特殊结构有序（如退化为单链表形态的左斜树或右斜树）。

插入

在当前节点下插入元素，返回新的root。

为什么要求返回一个新的root呢？

  1. 便于返回新的root。根节点不一定不变，比如之后如果有平衡化的操作。
  2. 便于进行递归，因为树本身就是递归结构，完成insert也可以依赖递归进行，在递归过程中，root是动态变化的，层层递进。

如果遇到插入key相同的情况，将value内容替代。

以下是自己写的版本：left、right指针没有接上新节点！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
PTreeNode insert(PTreeNode root, PTreeNode node)
{
    if(root == NULL) return node;//终止条件，root为空时，直接将node作为根
    if(node->key == root->key)
    {
        root->val = node->val;
        return root;
    }
    if(node->key < root->key)
    {
        root = root->left;
    }
    else
    {
        root = root->right;
    }
    insert(root, node);
}

简洁明了的正确版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
PTreeNode insert(PTreeNode root, PTreeNode node)
{
    if(!root) return node;//终止条件，插入的地方为空时，返回node本身作为根
    if(node->key < root->key) // key小于root时，插入到左侧
    {
        root->left = insert(root->left, node);
    }
    else if(node->key > root->key)
    {
        root->right = insert(root->right, node);
    }
    else
    {
        root->val = node->val;
        free(node);//实际上不该由此函数处理，应该由外部处理
    }
    return root;
}

创建节点

1
2
3
4
5
6
7
8
9
PTreeNode make_tree_node(unsigned key, char val)
{
    PTreeNode node = (PTreeNode)malloc(sizeof(TreeNode));
    node->key = key;
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

测试

1
2
3
4
5
6
7
8
int main(void)
{
    PTreeNode root = NULL;
    root = insert(root, make_tree_node(3, 'c'));
    root = insert(root, make_tree_node(2, 'b'));
    root = insert(root, make_tree_node(4, 'd'));
    root = insert(root, make_tree_node(1, 'a'));
}

查找

建立树就是为了查找，虽然插入困难了些，但是一旦有建立好的树，则搜索要简单得多。

1
2
3
4
5
6
7
8
9
10
11
12
13
PTreeNode search(PTreeNode root, unsigned key)
{
    if(!root) return NULL;
    if(key < root->key)
    {
        return search(root->left, key);
    }
    else if(key > root->key)
    {
        return search(root->right, key);
    }
    return root;
}

测试

1
2
3
4
5
6
7
8
9
10
int main(void)
{
    PTreeNode root = NULL;
    root = insert(root, make_tree_node(3, 'c'));
    root = insert(root, make_tree_node(2, 'b'));
    root = insert(root, make_tree_node(4, 'd'));
    root = insert(root, make_tree_node(1, 'a'));
    PTreeNode node = search(root, 2);
    PTreeNode node2 = search(root, 20);
}

删除

给定一个root，查找特定的key，删除后，返回0或1（C语言中没有bool类型，用int代替）

需要考虑：

  1. 删除的节点如果有子树怎么办？

首先递归查找key，如果找到了指定key，则有以下几种情况：

  1. 要删除的节点为叶子节点：直接删除
  2. 要删除的节点只有一支子树（左子树或右子树）：子树节点代替上来即可
  3. 要删除的节点有两支子树：在两棵子树中找到一个值大小邻近的节点，交换位置后，就可以转化为上述1、2的情况，就可以简化删除过程。
    1. 可以选择左子树的最右侧节点：左子树中最大值，但其有可能有左子树（一定不会存在右子树的），因此转化为2。如果没有子树，则转化为1，直接删除。
    2. 也可以选择右子树的最左侧节点：右子树中最小值，但其有可能有右子树（一定不会存在左子树的），因此转化为2。如果没有字树，则转化为1，直接删除。

remove也是一种递归，终止条件为当前root为空。

  1. 找到节点为叶子节点时，发现返回值应当为PTreeNode，因为你递归删除子树时，需要反馈给上层一个节点地址信息，以更新上层root的孩子链接。
  2. 当目标节点有两支子树时，从左右侧找相邻值均可。我们选择从右子树找最小值。
  3. remove和系统库函数名字冲突，需要改名为remove_node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int remove_node(PTreeNode root, unsigned key)
{
    if(!root) return NULL;
    if(key < root->key)
    {
        root->left = remove_node(root->left, key);
    }
    else if(key > root->key)
    {
        root->right = remove_node(root->right, key);
    }
    else // 找到key
    {
        // 情况1：叶子节点
        if(root->left == NULL && root->right == NULL)
        {
            free(root);
            root = NULL;
        }
        // 情况3：同时有两支子树
        // 当目标节点有两支子树时，从左右侧找相邻值均可。我们选择从右子树找最小值。
        else if(root->left != NULL && root->right != NULL)
        {
            PTreeNode right_min = find_right_min(root);
            exchange(right_min, root);
            // root已经交换到深层，其可能成为了叶子节点，也可能存在一支右子树。再次递归走情况1、2删除。
            root->right = remove_node(root->right, key);
        }
        else// 情况2：有且仅有一支子树
        {
            PTreeNode newroot = NULL;
            if(root->left != NULL)
            {
                newroot = root->left;
            }
            else
            {
                newroot = root->right;
            }
            free(root);
            root = newroot;
        }
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
//除了交换val值，不要忘记交换key值
void exchange(PTreeNode n1, PTreeNode n2)
{
    unsigned key = n1->key;
    n1->key = n2->key;
    n2->key = key;
    
    char val = n1->val;
    n1->val = n2->val;
    n2->val = val;
}
1
2
3
4
5
6
7
8
9
10
PTreeNode find_right_min(PTreeNode root)
{
    //形参传入的是根节点，不是根节点的右子树，所以初始化一定注意应当传入root->right
    PTreeNode right_min = root->right;
    while(right_min->left)
    {
        right_min = right_min->left;
    }
    return right_min;
}

树的遍历方式

树是一种非线性结构，既然要遍历就得按照一定顺序。

  1. 若按深度优先（DFS），从访问根节点的时机来看，有前序、中序、后序。
    1. 首先访问根节点，第二遍历左子树，第三遍历右子树：是前序
    2. 首先遍历左子树，第二访问根节点，第三遍历右子树：是中序
    3. 首先遍历左子树，第二遍历右子树，第三访问根节点：是后序
  2. 若按广度优先（BFS），则按层次遍历。

前序（PreOrder）

前序是先访问根节点，再访问左子树、右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void visit(void PTreeNode root)
{
    printf("key: %u, val: %c\n", root->key, root->val);
}
void preorder(PTreeNode root)
{
    //终止条件，根节点为空
    if(!root){
        return;
    }
    //访问根节点
    visit(root);
    //遍历左子树
    preorder(root->left);
    //遍历右子树
    preorder(root->right);
}

前序遍历测试代码如下，结果应为：3 2 1 4

1
2
3
4
5
6
7
8
9
int main(void)
{
    PTreeNode root = NULL;
    root = insert(root, make_tree_node(3, 'c'));
    root = insert(root, make_tree_node(2, 'b'));
    root = insert(root, make_tree_node(4, 'd'));
    root = insert(root, make_tree_node(1, 'a'));
    preorder(root);
}

中序（InOrder）

1
2
3
4
5
6
7
8
9
10
11
12
13
void inorder(PTreeNode root)
{
    //终止条件，根节点为空
    if(!root){
        return;
    }
    //遍历左子树
    inorder(root->left);
    //访问根节点
    visit(root);
    //遍历右子树
    inorder(root->right);
}

中序遍历测试代码如下，结果应为：1 2 3 4

1
2
3
4
5
6
7
8
9
int main(void)
{
    PTreeNode root = NULL;
    root = insert(root, make_tree_node(3, 'c'));
    root = insert(root, make_tree_node(2, 'b'));
    root = insert(root, make_tree_node(4, 'd'));
    root = insert(root, make_tree_node(1, 'a'));
    inorder(root);
}

后序（PostOrder）

1
2
3
4
5
6
7
8
9
10
11
12
13
void postorder(PTreeNode root)
{
    //终止条件，根节点为空
    if(!root){
        return;
    }
    //遍历左子树
    postorder(root->left);
    //遍历右子树
    postorder(root->right);
    //访问根节点
    visit(root);
}

后序遍历测试代码如下，结果应为：1 2 4 3

1
2
3
4
5
6
7
8
9
int main(void)
{
    PTreeNode root = NULL;
    root = insert(root, make_tree_node(3, 'c'));
    root = insert(root, make_tree_node(2, 'b'));
    root = insert(root, make_tree_node(4, 'd'));
    root = insert(root, make_tree_node(1, 'a'));
    postorder(root);
}

层序（BFS）

递归思想、栈结构对于层序遍历不太好使，需要换一种思路，队列、先进先出（FIFO）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bfs(PTreeNode root)
{
    push_node(root);
    while(queue_size() > 0)
    {
        PTreeNode top = pop();
        visit(top);
        if(top->left != NULL)
        {
            push_node(top->left);
        }
        if(top->right != NULL)
        {
            push_node(top->right);
        }
    }
}

队列设计

使用链表充当队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
typedef struct _QueueNode
{
    PTreeNode val;
    struct _QueueNode * next;
}QueueNode, * PQueueNode;

PQueueNode queue_top = NULL;

PQueueNode make_queue_node(PTreeNode treeNode)
{
    PQueueNode queue_node = (PQueueNode)malloc(sizeof(QueueNode));
    queue_node->val = treeNode;
    queue_node->next = NULL;
    return queue_node;
}

void push_node(PTreeNode treeNode)
{
    PQueueNode queue_node = make_queue_node(treeNode);
    //判断目前是否有首节点，没有就当作首节点
    if(queue_top == NULL)
    {
        queue_top = queue_node;
    }
    else
    {
        PQueueNode cur_node = queue_top;
        while(cur_node->next)
        {
            cur_node = cur_node->next;
        }
        cur_node->next = queue_node;
    }
}
unsigned queue_size()
{
    unsigned cnt = 0u;
    PQueueNode node = queue_top;
    while(node)
    {
        ++cnt;
        node = node->next;
    }
}
PTreeNode pop()
{
    if(queue_top == NULL)return NULL;
    PTreeNode treeNode = queue_top->val;
    PQueueNode oldNode = queue_top;
    queue_top = queue_top->next;
    free(oldNode);
    oldNode = NULL;
}

层序遍历测试代码如下，结果应为：3 2 4 1

1
2
3
4
5
6
7
8
9
10
int main(void)
{
    PTreeNode root = NULL;
    root = insert(root, make_tree_node(3, 'c'));
    root = insert(root, make_tree_node(2, 'b'));
    root = insert(root, make_tree_node(4, 'd'));
    root = insert(root, make_tree_node(1, 'a'));
    bfs(root);
    return 0;
}

B树（2-3-(4)树）

B代表Balanced，据说也代表波音公司，因为它是由Rudolf Bayer和Edward M. McCreight在波音研究实验室工作时发明的。
其性质是为了解决BST树的退化问题的，比如说一直向左子树插入一个边缘值，就会导致树退化为链表，这种不平衡导致效率降低。

B树派生出好多种形态的树，2-3-(4)树就是B树的4阶形式。红黑树又是2-3-(4)树的一种形式，是一种多叉树的二叉树实现。

B树、AVL树、红黑树的对比

AVL树、B树、红黑树，都是解决BST树退化问题的自平衡结构。

  1. 结构上：
    1. AVL树和红黑树都是二叉树。节点中都记录了平衡状态。
      1. AVL存储平衡因子。
      2. 红黑树存储颜色标记。
    2. B树为多路树，节点有多个键、子节点指针。
  2. 性能上：
    1. AVL树，严格平衡。查询效率最高。
    2. 红黑树，不严格平衡。查询效率略慢于AVL树。
      1. 但在数学上，AVL和红黑树的增删查时间复杂度都是大O(log n)。
      2. 对于插入操作，AVL和红黑树都是最多旋转2次。
      3. 对于删除操作，AVL树由于需要严格平衡，旋转次数可能需要O(log n)次，而红黑树可以通过翻转颜色，让旋转次数最多3次。
        1. 为什么不能直接说“logn 次”？
          1. 平衡因子：每个节点的左右子树高度差（Balance Factor, BF）的绝对值不超过1。
          2. 高度约束：对于包含 n 个节点的AVL树，其高度 h≤1.44log2​n（基于斐波那契数列的黄金分割比例）。
          3. 树高与路径长度：若树高为 h，删除节点的路径长度最多为 h。
          4. 每层最多一次旋转：每层失衡节点需一次或两次旋转（如双旋），但旋转次数的增长趋势仍为 O(h)。
          5. 最终结果：最坏旋转次数=O(h)=O(logn)
    3. B树也是平衡的，但其只适用于外存（磁盘）IO操作。
      1. 见“高级数据结构_B树”
      2. B树不需要旋转节点。是通过分裂、合并节点达到平衡的。
      3. 为什么B树不像AVL、红黑树那样适用于内存操作：
        1. 指针操作开销：B树的插入/删除涉及多次指针调整（分裂或合并节点），而AVL/红黑树的旋转操作仅需修改少量指针。
        2. B树节点的数据量通常较大（例如一个节点占4KB），可能超出CPU缓存行（通常64B-256B），导致缓存未命中率增加。
        3. 总之，局部性差：二叉树的节点较小，更容易被缓存命中；而B树的节点遍历需要访问更多内存块，降低缓存利用率。
    4. 因此。AVL树适合读多写少；红黑树适合写多读少。

与B树不同的是，AVL是一种BST，是二叉树，即比平衡二叉搜索树多了平衡的概念，具体来说多了旋转的操作、节点的状态。
B树在原型上，是多叉树，且节点可有多个值。由于B树不是二叉树，因此B树不属于BST。

对于AVL和红黑树：由于AVL是严格平衡的，在查询效率上略优于红黑树这种不严格平衡的树，但它们的时间复杂度都是O(log⁡n)O(\log n);
但是，对于AVL和B树而言，搜索算法没什么差异，AVL树和B树同样都是二分查找的分治策略, 时间复杂度都为O(log⁡n)O(\log n);

节点形态

有2型节点、3型节点。

2型节点是节点内部有1个key，可以有两个子节点；3型节点是内部有2个key，可以有三个子节点。2-3树的意思是，树中可能包含2型节点和3型节点。

插入节点位置的规则遵循BSTree的规则，即从左往右按从小到大的顺序，左侧最小、右侧最大。如果是3型节点，则需要满足：左侧最小，key1次小，中子树是中值，key2次大，右侧最大。

除了以上规则以外，为了能更好地控制2-3-(4)树，多了一个特殊的附加规则：2、3、4型节点要么是叶子节点（没有子节点），要么子节点全都占满，没有中间状态。

  1. 假设目前有一个内含6的2型节点
  2. 要插入9，由于子树要么空要么满，所以只能将其与6并列放入2型节点中，变为一个内含6、9的3型节点。
  3. 继续插入7，会进入一个临时状态，即将其与6、9并列，变为一个内含6、7、9的4型节点。但是紧接着，会分裂为3个2型节点：7作为根节点，左子树为6，右子树为9。
  4. 继续插入5，经过对比，向7的左子树6插入，与6并列，变为一个内含5、6的3型节点。
  5. 继续插入4，经过对比，向7的左子树（5、6）插入，与5、6并列，变为一个内含4、5、6的4型节点。
  6. 紧接着，左子树又要面临分裂为3个2型节点，但如果单纯地分别把4、6下裂后，只有左支的深度单独加1，会导致整个树的不平衡（左偏）。
  7. 但如果换个方向，向父节点推5，会巧妙地保持整个树深度同步。
  8. 而5上推与7并列后，根节点变为3型节点，需要有三个子树，那么9保留原位，而4、6正好可以各占一个子树的位置。所以，最终结果为：整根为（5、7），子树1为4，子树2为6，子树3为9。

实现

  1. 其中一个比较棘手的问题是，凡是两个数以上的比较，都需要一个机制来对比，哪怕是三个数的对比。
  2. 2-3-4树的数据结构不确定，有中间不稳定的4型节点，所以不能简单地用left、middle、right对比。
  3. 如果B树单个节点中有上千个数据，那么就用数组来存放。但是如果此B树是2-3-4树，则数组就显得比较大动干戈了。
  4. 综上原因，我们想到一个巧妙的方法，就是用颜色来代替某些支。由此产生了：红黑树

红黑树（二叉搜索红黑树）

红黑树其实是2-3树的一个变形（不存在4型节点）。

我们加以人为规定：把原先2-3树，同一节点中的较小数裂在根节点的左侧子树。这样的话，3型节点就转化成了二叉树。

当然也可以人为规定把较大数放在右侧子树，甚至说同时存在较小数放左、较大数放右的情况。这样徒使程序变得很复杂，失去了简化2-3树的意义。所以为了编写程序简单，统一规定都按左侧（左斜）处理。


上图的 c 用红线相连，指向 a，称 a 为红色节点，代表 a、c 原先在2-3树中曾为同一节点。红色代表鲜明，可以理解为：有血肉联系。c 是黑色节点。

红黑树对应2-3树的有效形式

  1. 我们将树中的链接分为两种类型：
    1. 红链接将两个2- 结点连接起来构成一个3- 结点
    2. 黑链接则是2-3 树中的普通链接。
    3. 确切地说，我们将3- 结点表示为由一条左斜的红色链接（两个2-结点其中之一是另一个的左子结点）相连的两个2- 结点。
    4. 规定只能左红，不能出现右红。
  2. 规定只能连续一支红线，即一个节点最多只能由一个红线连接，即表示在2-3树中的3型节点。不能出现连续两支红线。
  3. 在实际程序中，因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们把颜色存储在左子树节点。
  4. 如果指向它的链接是红色的，那么为红色。我们约定空链接为黑色（因此根节点存储的应当总是黑色。我们在每次插入后都要将根结点设为黑色。注意，每当根结点由红变黑时树的黑链接高度就会加1）。
  5. 有这样的性质，红黑树最长支的长度 不超过 最短支的长度的2倍。虽然AVL树最大差1，但AVL树插入性能太慢。红黑树就很好地平衡了层数差异和性能。

极端形式

二叉树的极端形式就是：一支最长、一支最短：左子树最长情况下是一红线一黑线交替穿插。右子树最短情况下是全黑。这种情况下，左支和右支的高度差最大是2倍。这个高度差是可以接受的，因为红黑树相比于其他树来说插入较简单，比如两边最多差1的AVL树插入是很费劲的，时间复杂度太高。而又能兼顾到查找的速度。

应用

STL中的map（dictionary）、set；

Linux中网络编程中epoll用到的数据结构

节点定义

用直观的符号代替不直观的内容（整数，不能是小数）。通常需要typedef，否则在声明、初始化枚举类时，需要写出全称enum Color。

1
2
3
4
5
typedef enum _Color
{
    Black = 0,
    Red
}Color;
1
2
3
4
5
6
7
8
typedef struct _RBNode
{
    unsigned key;
    char val;
    Color color;
    struct _RBNode * left;
    struct _RBNode * right;
}RBNode, *PRBNode;

插入

我们可以默认创造出的新节点都是红色的，因为2-3树在插入节点时，节点总是试图与上层节点结合成为同一节点。

创建节点（默认红色）

1
2
3
4
5
6
7
8
9
PRBNode make_rb_node(unsigned key, char val)
{
    PRBNode node = (PRBNode)malloc(sizeof(RBNode));
    node->val = val;
    node->key = key;
    node->color = Red;
    node->left = NULL;
    node->right = NULL;
}

根节点的颜色问题（插入空树）

在下面插入的过程中，可能会有颜色转换操作，会使根结点变为红色。这也可能出现在很大的红黑树中。严格地说，红色的根结点说明根结点是一个3- 结点的一部分，但实际情况并不是这样。因此我们在每次插入后都会将根结点设为黑色。注意，每当根结点由红变黑时树的黑链接高度就会加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 树空时插根节点的情况。
PRBNode insert_rb_node(PRBNode root, PRBNode node)
{
    if(root == NULL)return node;
    //...
}
PRBNode insert_node(PRBNode root, PRBNode node)
{
    root = insert_rb_node(root, node);
    //在插入过程中，根节点有可能变红，插入后要把根设为黑色。
    if(is_red(root))
    {
        root->color = Black;
    }
    return root;
}

插入到2-型节点

  1. 比如向一个内含 c 的 2-型节点插入 a，已知 2-型节点没有子树，则将 a 插入到 c 左子树，则相当于在 2-3 树中合并节点的情况，在红黑树中则相当于 c 的颜色设为红色即可。c 默认就是红色，不用操作。最后：c 红，a 黑。
  2. 比如向一个内含 c 的 2-型节点插入 d，2-型节点没有子树，则将之插入到右子树，因为 c 没有子树，则相当于在 2-3树中合并节点的情况。由于默认创建出来的节点是红的，造成右红，那么就需要左旋操作：即让 d 上位，c 下位至 d 的左子树，且 c 右支接管 d 原先的左子树。插入之前，b 是黑色，c 是红色，插入之后，还需将 b、c 的颜色交换。
1
2
3
4
5
6
7
PRBNode left_rotate(PRBNode root)
{
    PRBNode newroot = root->right;
    root->right = newroot->left;
    newroot->left = root;
    return newroot; //new root
}
1
2
3
4
5
6
void exchange_color(PRBNode n1, PRBNode n2)
{
    Color color = n1->color;
    n1->color = n2->color;
    n2->color = color;
}

插入到3-型节点

该3-型节点此时一定有左子树，且左子树一定为红色，右子树不可能是红的。

  1. 左红右红：向（c、f）节点（没有右子树）插入 h ： h 将要插到 f 的右子树，但 h 默认为红色，出现了左红右红，需要调整。此时相当于在2-3-4树中合并为过渡4-型节点的情况，之后即将分裂为3个2-型节点。而在红黑树中，自然地省去了分裂的步骤，此时需要把 c、h 节点的红色反转为黑色（flip color）。注意！还需要把 f 的颜色反转为红色，因为在2-3-4树中的分裂操作中，被上推的节点企图与上层进行结合，一旦结合，就成红色了。总之，3 节点翻转颜色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int flip_color(PRBNode root)
{
    if(root == NULL)return 0;
    if(root->color == Red)
    {
        root->color = Black;
    }
    else
    {
        root->color = Red;
    }
    return 1;
}
void flip_colors(PRBNode root)
{
    //如果根节点颜色反转成功，则才能继续反转子节点
    if(flip_color(root))
    {
        flip_color(root->left);
        flip_color(root->right);
    }
}
  1. 左连续红：向（c、f）节点（没有右子树）插入 a ：a 将要插到 c 的左子树，但 a 默认为红色， 出现了左支连续红色，需要调整。此时相当于在2-3-4树中合并为过渡4-型节点的情况，之后即将分裂为3个2-型节点，把 c 上推，把 a、f 下裂。在红黑树中，则需要右旋操作： f 下位至 c 的右子树，且 f 的左支接管 c 原先的右子树。此时又出现了左红右红，效仿情况1，把3个节点颜色全部反转即可。则最后：a 黑、c 红、f 黑。
    1. 颜色问题：右旋前的颜色为：a 红、c 红、f 黑，右旋后的颜色为：a 红、c 黑、f 红。为什么上移的 c 变黑了？因为 c（newRoot）相当于替代了 f（oldRoot）的位置，旧根本来就是黑的，所以 c 要变黑。
1
2
3
4
5
6
7
8
PRBNode right_rotate(PRBNode root)
{
    PRBNode x = root->left;
    root->left = x->right;
    x->right = root;
    exchange_color(x, root);
    return x;// new root
}
  1. 左空右红：向（c、f）节点（没有右子树）插入 d ：d 将要插到 c 的右子树（注意，不是根节点 f 的右子树，而是其左子树 c 的右子树），但 d 默认为红色，出现了右支红色，需要调整。需要以 c 为根左旋，之后 c 成了 d 的左支，d 成了 f 的左支，出现了左支连续红色。此时和在情况2中一样，需要以 f 为根右旋，即把 d 上推，把 c、f 下裂。f 下位至 d 的右子树，且 f 的左支接管 d 原先的右子树。整体来说：先左旋，后右旋。
    1. 像情况2一样，右旋后，又出现了左红右红，则需要把3个节点颜色全部反转。最后：c 黑、d 红、f 黑。

整体过程


相比于BSTree的插入，前面的流程一致，只是多了插入后的调平的操作。

  1. 终止条件是当时的root为空
  2. 要插入的node的key与已存在的节点的key相等时，认为是更新节点值的操作
  3. 调整——我们需要精心安排 if 的顺序，经过3种情况分析：
    1. 左黑右红：在左旋后会出现左连续红，则需要右旋，之后会出现左红右红。
    2. 左连续红：右旋后会出现左红右红。
    3. 左红右红：翻转颜色即可。
    4. 总体来说：
      1. 1和2是互斥关系：以上图为例，c为根时，只能看到c、d两层，看不到情况 2 从 f 层开始的左连续红。
      2. 1和3也是互斥关系：由于1和2是互斥关系，不会在那一层递归进行对 f 的右旋，所以不会出现左红右红，因此1和3也是互斥关系。
      3. 2和3是并列先后顺序关系。在 情况2 对 f 进行右旋后，能在同一层递归关系中继续看到 c、d、f 的颜色关系，出现左红右红，因此2必须在3前面。
      4. 情况3，对三个节点全部翻转颜色。
  4. 最后红黑树还要注意一条规则是总根一定是黑色的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
PRBNode insert_rb_node(PRBNode root, PRBNode node)
{
    if(root == NULL)return node;//此处不用调整了，会由上一层调整
    if(root->key == node->key)
    {
        root->val = node->val;
        return root;
    }
    //递归向下
    //左支递归插入
    if(node->key < root->key)
    {
        root->left = insert_rb_node(root->left, node);
    }
    else//右支递归插入
    {
        root->right = insert_rb_node(root->right, node);
    }
    //递归向上
    //调整
    //左空右红。
    // 左空右红时局部左旋后会出现左侧连续红，
    // 但不能在同一层递归处理后续情况，因此是if-else关系
    if(!is_red(root->left) && is_red(root->right))
    {
        root = left_rotate(root);//可能会更新root
    }
    else
    {
        //左侧连续红
        // 必须排到左红右红前面，因为右旋后出现左红右红，需要在同一层递归处理。因此是if-if先后顺序关系。
        if(is_red(root->left) && is_red(root->left->left))
        {
            root = right_rotate(root);
        }
        //左红右红：反转颜色
        if(is_red(root->left) && is_red(root->right))
        {
            flip_colors(root);
        }
    }
    return root;
}
int is_red(PRBNode root)
{
    if(root)
    {
        return root->color == Red;
    }
    return Black;// 若root为空则返回黑
}
PRBNode insert_node(PRBNode root, PRBNode node)
{
    root = insert_rb_node(root, node);
    //在插入过程中，根节点有可能变红，插入后要把根设为黑色。
    if(is_red(root))
    {
        root->color = Black;
    }
    return root;
}

测试

1
2
3
4
5
6
7
8
9
int main()
{
    PRBNode root = NULL;
    root = insert_node(root, make_rb_node(3, 'c'));
    root = insert_node(root, make_rb_node(2, 'b'));
    root = insert_node(root, make_rb_node(4, 'd'));
    root = insert_node(root, make_rb_node(1, 'a'));
    return 0;
}

支持4-型节点的红黑树（存在左红右红）

Cpp的STL模板库以及其他语言的库，Dictionary和Map中用的都是支持4-型节点的红黑树。

首先我们要明确，我们在2-3树下的红黑树规定了红链接只能出现在左侧。
原先2-3树下的红黑树，插入过程中临时存在的4-型节点，只是一个临时、不稳定的中间状态，插入后要立即检查左连续两红、左红右红、左空右红，这几种非法的4-型节点情况，调整。
现在如果支持4-型节点，那么红链接支持出现在右侧。那么就会允许左连续两红、左红右红、左空右红的存在吗？不！仍然不允许，因为这仍是基于左倾的红黑树，实际仅能存在节点为黑色、左右字节点为红色的这样的情况（即左红右红）。

但是，微妙的是，虽然允许了4-型节点的合法存在，但在插入过程中，为了操作简便，把4-型节点又拆解为非4-型节点了，拆解中用到的旋转操作是我们上文写过的2-3树下的左倾红黑树下的操作。于是树经过拆解后，又变成了2-3树下的左倾红黑树，就又可以用到之前的操作了。

总之，基于左倾旋转操作的支持4-型节点的红黑树，有以下性质：
一棵红黑树是满足下面红黑性质的二叉搜索树：

  1. 每个结点或是红色的，或是黑色的。
  2. 根结点是黑色的。
  3. 每个叶结点 (NIL) 是黑色的。
  4. 如果一个结点是红色的，则它的两个子结点都是黑色的。
  5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

如果支持4-型节点稳定存在，在结构上，相比只有2-3型的结构，2-3-4树的层数会更少一些。虽然实际在红黑树的形式下层数没有明显减少，然而，操作效率上会得到改善。
但是，就要解决一个问题，即4-型节点再插入一个节点，怎么处理？是允许临时5-型节点存在吗？这样就使程序复杂化了。

高效、巧妙的处理方式：

  1. 在递归向下、插入之前，事先分解掉红黑树中所有的4-型节点（但必须是等价转化，不能让2-3-4树形式上的层数变多，对于红黑树形式来说，可能会多1层，但还是符合平衡的要求范围内的，可以看上图）。这样，后续插入时就不会存在4-型节点，要么是2-型、要么是3-型。
    1. 我们发现，分解4-型节点，其实仅需翻转颜色而已。
  2. 插入
  3. 插入之后，递归向上调平。
    1. 只需要处理：左黑右红、左连续红的情况。
    2. 左黑右红和左连续红不在同一递归层次中处理，互斥。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
PRBNode insert_rb_node(PRBNode root, PRBNode node)
{
    if(root == NULL)return node;//此处不用调整了，会由上一层调整
    if(root->key == node->key)
    {
        root->val = node->val;
        return root;
    }
    //递归向下之前，先分解所有遇到的4-型节点。
    if(is_red(root->left) && is_red(root->right))
    {
        flip_colors(root);
    }
    //递归向下
    //左支递归插入
    if(node->key < root->key)
    {
        root->left = insert_rb_node(root->left, node);
    }
    else//右支递归插入
    {
        root->right = insert_rb_node(root->right, node);
    }
    //递归向上
    //调整
    //左空右红。
    // 左空右红时局部左旋后会出现左侧连续红，
    // 但不能在同一层递归处理后续情况，因此是if-else关系
    if(!is_red(root->left) && is_red(root->right))
    {
        root = left_rotate(root);//可能会更新root
    }
    else
    {
        //左侧连续红
        if(is_red(root->left) && is_red(root->left->left))
        {
            root = right_rotate(root);
        }
        // 在允许4-型的红黑树中，左红右红合法。不用处理。
        //if(is_red(root->left) && is_red(root->right))
        //{ }
    }
    return root;
}
int is_red(PRBNode root)
{
    if(root)
    {
        return root->color == Red;
    }
    return Black;// 若root为空则返回黑
}
PRBNode insert_node(PRBNode root, PRBNode node)
{
    root = insert_rb_node(root, node);
    if(is_red(root))
    {
        root->color = Black;
    }
    return root;
}

测试

1
2
3
4
5
6
7
8
9
int main()
{
    PRBNode root = NULL;
    root = insert_node(root, make_rb_node(3, 'c'));
    root = insert_node(root, make_rb_node(2, 'b'));
    root = insert_node(root, make_rb_node(4, 'd'));
    root = insert_node(root, make_rb_node(1, 'a'));
    return 0;
}

删除

红黑树的删除可以参考BST的过程。

红黑树形式的分析——类比BST树
BST中，如果节点是

  1. 叶子节点，直接删除
  2. 只有一支子树，则直接删除，删除后让该支子树替代root自身即可（叶子节点的子树为NULL））
  3. 如果有两个子树，则选取一个叶子节点交换（选择两支子树中相近大小的节点替代自身），即把将要删除的节点下移至叶子节点或者下移至只有一支子树的状态，就可以转化为情况1、2了。
  4. 递归返回后需要调平

2-3-4树形式的分析——类比插入的思想
除此之外，红黑树是2-3-4树，拿2-3-4树的形式来分析，如果要删除的节点在叶子节点中，可能在一个4-型节点、3-型节点、2-型节点中，4-型、3-型可以直接删除，因为不影响该路径层数的平衡。
总之，如果是2-型节点，就不能直接删除。

类比于红黑树避免插入4-型节点而分解所有的4-型节点的道理，我们可以在避免删除2-型节点而让所有的2-型节点扩张为3-型或4-型节点。

因此，4-型节点在红黑树中，既可以存在，也可以不存在。
如果允许存在4-型节点，则删除后不用向上递归分解4-型节点。如果不允许存在4-型节点，则删除后需要向上递归分解4-型节点。

代码可以参照算法（4th）291页3.3.41

红黑树非递归版本

见算法（4th）265页3.2.13。

模型

我们分析的模型，基于的红黑树形式是：实际4-型节点仅能存在为根黑色、左右字节点为红色的这样的情况（即左红右红）。详见支持4-型节点的红黑树（存在左红右红）。
如果仅分析新节点插到左子树的情况：

  1. 爷黑，左红右红。
    1. 爷爷、父、叔全部翻转颜色。爷爷的父节点可能还是红色，需要不断向上调整，直到达到根，根记得设为黑色。
  2. 爷黑，左连续两红。
    1. 插到了父节点（红色）的左子树
      1. 翻转父节点、爷爷节点颜色，之后以爷爷节点右旋。
    2. 插到了父节点（红色）的右子树
      1. 先以父节点左旋，就会转化为上面的情况。
  3. 爷黑，左黑、右无所谓。直接插

实际上，新节点插到右子树只是上述过程的镜像。所以我们无需再分析。

默认插入的新节点为红色。
若树为空树，则直接插入节点，最后记得根要设为黑色；
若树不为空，且插入位置的父节点为黑色，则直接插入。
若插入位置的父节点为红色：
只分析节点插入到左支的情况。

  1. 叔叔节点为红色，插入的位置不管是父节点的左侧还是右侧。都相当于爷爷黑、爷爷的左红右红。翻转上面3个节点颜色即可。但是，爷爷变红之后，可能还和爷爷的父节点冲突，需要不断向上调整，直到找到整个树的根，设为黑色。
  2. 叔叔节点为黑色，插入的位置是父节点的左侧。则相当于爷爷黑、左连续两红。需要先把父节点和爷爷的节点颜色翻转（父设为黑，爷爷设为红）。再以爷爷为轴右旋。则父节点上位，为黑色，结束。
  3. 叔叔节点为黑色，插入的位置是父节点的右侧。则相当于爷爷黑、左连续两红。以父节点左旋，之后变成了情况2。

为了能实现回溯之前节点，需要在节点中包含一个父节点指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <typename T>
class RBTree
{
    // 节点的颜色
    enum Color
    {
        BLACK,
        RED
    };
    // 节点类型
    struct Node
    {
        Node(T data = T(), Node *parent = nullptr,
             Node *left = nullptr, Node *right = nullptr,
             Color color = BLACK)
            : data_(data), left_(left), right_(right), parent_(parent), color_(color)
        {
        }
        T data_;
        Node *left_;
        Node *right_;
        Node *parent_; // 指向当前节点的父节点
        Color color_;  // 节点的颜色
    };
    // 指向红黑树的根节点
    Node *root_;
};

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
void insert(const T &val)
{
    if (root_ == nullptr)
    {
        root_ = new Node(val);
        return;
    }

    Node *parent = nullptr;
    Node *cur = root_;
    // BST 插入流程
    while (cur != nullptr)
    {
        if (cur->data_ > val)
        {
            parent = cur;
            cur = cur->left_;
        }
        else if (cur->data_ < val)
        {
            parent = cur;
            cur = cur->right_;
        }
        else
        {
            return;
        }
    }
    // parent现在是node的父节点
    Node *node = new Node(val, parent, nullptr, nullptr, RED);
    // 判断node插到了parent左还是右，然后让其left或right指向node
    if (parent->data_ > val)
    {
        parent->left_ = node;
    }
    else
    {
        parent->right_ = node;
    }

    // 如果新插入的红色节点，父节点也是红色，不满足红黑树性质，进行插入调整操作
    if (RED == color(parent))
    {
        fixAfterInsert(node);
    }
}
// 调平函数
void fixAfterInsert(Node *node)
{
    // 如果当前红色节点的父节点是红色，不断向上调整
    while (color(parent(node)) == RED)
    {
        // 左镜像的3种情况，即插入的节点在左子树当中
        if (left(parent(parent(node))) == parent(node))
        {
            Node *uncle = right(parent(parent(node)));
            if (RED == color(uncle)) // 情况一
            {
                setColor(parent(node), BLACK);
                setColor(uncle, BLACK);
                setColor(parent(parent(node)), RED);
                node = parent(parent(node)); // 继续调整
            }
            else
            {
                // 先处理情况三
                if (right(parent(node)) == node)
                {
                    node = parent(node);
                    leftRotate(node);
                }
                // 统一处理情况二
                rightRotate(parent(parent(node)));
                break; // 调整已经完成
            }
        }
        else // 右镜像的3种情况，即插入的节点在右子树当中
        {
            Node *uncle = left(parent(parent(node)));
            if (RED == color(uncle)) // 情况一
            {
                setColor(parent(node), BLACK);
                setColor(uncle, BLACK);
                setColor(parent(parent(node)), RED);
                node = parent(parent(node)); // 继续调整
            }
            else
            {
                // 先处理情况三
                if (left(parent(node)) == node)
                {
                    node = parent(node);
                    rightRotate(node);
                }
                // 统一处理情况二
                leftRotate(parent(parent(node)));
                break; // 调整已经完成
            }
        }
    }
    // 此处强制root为黑色节点
    setColor(root_, BLACK);
}

分析出，红黑树的插入，最多旋转2次：先左旋、再右旋；或者先右旋、再左旋。

删除

总体思路：

  1. 叶子节点的删除：
    1. 根。先把根清理，再删除。
    2. 红色叶子，直接用BST方式删除。
    3. 黑色叶子，从兄弟借黑色节点。
  2. 有两个子树的节点删除：
    1. 删除有两个子树的节点，可以把节点与其左子树的最右节点（此时最多有一个子树，或者为叶子节点）替换，然后转化为删除只有一个子树的节点或删除叶子节点。
  3. 有一个子树的节点删除：
    1. 主要思想是把孩子替补上来。
      1. 补上来的孩子是红色，直接把孩子涂成黑色。
      2. 补上来的孩子是黑色，无法再从自己孩子这里补充黑色了，需要从兄弟借黑色节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
void remove(const T &val)
{
    // 查找
    if(root_ == nullptr)
    {
        return;
    }
    Node* cur = root_;
    while(cur != nullptr)
    {
        if (cur->data_ > val)
        {
            cur = cur->left_;
        }
        else if(cur->data_ < val)
        {
            cur = cur->right_;
        }
        else
        {
            break;
        }
    }
    if(cur == nullptr)
    {
        return;
    }
    // 删除
    // 左右都不为空，则找左子树中的最右值（前驱）或者右子树中的最左值（后继），替换
        // 此处找的是左子树中的最右值（前驱）
    if (cur->left_ != nullptr && cur->right_ != nullptr)
    {
        Node * pre = cur->left_;
        while (pre->right_ != nullptr)
        {
            pre = pre->right_;
        }
        // 替换值
        cur->data_ = pre->data_;
        cur = pre; // 转化为删除pre
    }
    // 删除cur指向的节点，目前可以确定其最多有一棵子树，或者全空
    Node * child = cur->left;
    if (child == nullptr)
    {
        child = cur->right_;
    }
    
    // 如果cur有子树，需要更新cur子树的parent指向cur的parent
    if (child != nullptr)
    {
        child->parent_ = cur->parent_;
        // 如果cur的parent为空，则说明删除cur后，child变成了根
        if (cur->parent_ == nullptr)
        {
            root_ = child;
        }
        else
        {
            // 因为cur是最右节点，不可能有右子树。
            // cur在左支，删除后 需要把孩子继承给cur的parent的左支
            if (cur->parent_->left_ == cur)
            {
                cur->parent_->left_ = child;
            }
            else
            {
                // 因为cur是最右节点，不可能有右子树。
                // cur在右支，删除后 需要把孩子继承给cur的parent的右支
                cur->parent_->right_ = child;
            }
        }
        Color color = color(cur);
        delete cur;
        // 若删除的节点是红色，完毕。
        // 若删除的节点是黑色，需要调整
            // 如果补上来的孩子是红色，直接涂成黑色
            // 如果补上来的孩子是黑色，无法再借孩子黑色，需要借兄弟的。
        if (c == Black)
        {
            fixAfterRemove(child);
        }
    }
    else // cur没有子树。
    {
        // 看parent是否为空，若是，说明其为根节点
        if (cur->parent_ == nullptr)
        {
            delete cur;
            root_ = nullptr;
            return;
        }
        else // 此时删除的节点cur是正常的叶子节点
        {
            // 删除黑色叶子，要借兄弟一个黑色节点
            if (color(cur) == Black)
            {
                fixAfterRemove(cur);
            }
            // 不管叶子是黑还是红，都要走以下步骤
            if (left(parent(cur)) == cur)
            {
                left(parent(cur)) == nullptr;
            }
            else
            {            {
                right(parent(cur)) == nullptr;
            }
            delete cur;
        }
    }
}
  1. 根黑或者红。兄弟黑
    1. 兄弟的右孩子是红色，左无所谓
      1. 把兄弟的右孩子设为黑色。以根节点为轴，左旋。完毕。
      2. 总之，借了右支的黑节点。右支需要改一个红色为黑色。
    2. 兄弟的左孩子是红色，右是黑色
      1. 以兄弟为轴右旋，于是转化为了情况1。
      2. 注意兄弟换了，需要更新（brother=parent->right）。
    3. 兄弟的两个孩子全黑。
      1. 总体思想：由于左边即将失去一个黑色，可以把黑色的兄弟涂红以平衡。
        1. 右支新添了红色节点，回头需看若根节点为红色，则改为黑色。结束。
        2. 若根节点为黑色，则向上追溯一个红色节点，改为黑色。
  2. （情况4）根黑或者红。兄弟红
    1. 兄弟的两个孩子全黑（因为兄弟节点是红，其孩子不能出现红）。意味着根的右支已经没有孩子可借。
      1. 以根为轴，左旋。这样，要删除的节点就有了黑色兄弟。
      2. 但是要注意，要删除的节点的兄弟换了，需要更新（brother=parent->right）。
      3. 可以归结到上述兄弟黑的三种情况了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 旋转时产生的颜色交换应集成在旋转函数中
void fixAfterRemove(Node * node)
{
    while (node != root_ && color(node) == Black)
    {
        // 左镜像，即删除的节点在根的左支。
        if (left(parent(node)) == node)
        {
            Node * brother = right(parent(node));
            // 情况4，兄弟红。转化为兄弟黑的情况
            if (color(brother) == RED)
            {
                leftRotate(parent(node));
                brother = right(parent(node));
            }
            // 情况3，兄弟的两个孩子为黑。
            if (color(left(brother)) == Black && color(right(brother)) == Black)
            {
                setColor(brother, Red);
                node = parent(node);
                // 进入下一次while循环看父节点是黑还是红。遇到红则退出。
            }
            else //情况2 兄弟的左孩子是红色，右是黑色
            {
                if (color(right(brother)) == Black)
                {
                    rightRotate(brother);
                    brother = right(parent(node));
                }
                // 情况1 兄弟的右孩子是红色，左孩子无所谓。
                setColor(right(brother), Black);
                leftRotate(parent(node));
                break;
            }
        }
        else // 右镜像，即删除的节点在根的右支。
        {
            Node * brother = left(parent(node));
            // 情况8，兄弟红。转化为兄弟黑的情况
            if (color(brother) == RED)
            {
                rightRotate(parent(node));
                brother = left(parent(node));
            }
            // 情况7，兄弟的两个孩子为黑。
            if (color(left(brother)) == Black && color(right(brother)) == Black)
            {
                setColor(brother, Red);
                node = parent(node);
                // 进入下一次while循环看父节点是黑还是红。遇到红则退出。
            }
            else //情况6 兄弟的右孩子是红色，左是黑色
            {
                if (color(left(brother)) == Black)
                {
                    leftRotate(brother);
                    brother = left(parent(node));
                }
                // 情况5 兄弟的左孩子是红色，右孩子无所谓。
                setColor(left(brother), Black);
                rightRotate(parent(node));
                break;
            }
        }
    }
    // 直到node指向的节点是红色，则直接涂成黑色，结束。
    setColor(node, Black);
}

分析出，红黑树的删除，最多旋转3次：先左旋、再右旋、再左旋；或者先右旋、再左旋、再右旋。