数据结构与算法之美（三）

跳表

跳表：带有多级索引的链表。

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是O(logn)。

跳表的空间复杂度是O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。

散列表

散列思想

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置，当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列函数

散列函设计的三点基本要求

  • 散列函数计算得到的散列值 是一个非负整数；
  • 如果key1 = key2，那么hash(key1) == hash(key2)；
  • 如果key1 != key2，那么hash(key1) != hash(key2)；

散列冲突

  1. 开放寻址法

    开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？我先讲一个比较简单的探测方法，线性探测（Linear Probing）。

    当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

    对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法，二次探测（Quadratic probing）和双重散列（Double hashing）。

    所谓二次探测，跟线性探测很像，线性探测每次探测的步长是1，那它探测的下标序列就是hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是hash(key)+0，hash(key)+1^2，hash(key)+2^2……

    所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

    不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

    装载因子的计算公式是：散列表的装载因子=填入表中的元素个数/散列表的长度。

    装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

  2. 链表法

    在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

    当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢？

    实际上，这两个操作的时间复杂度跟链表的长度k成正比，也就是O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中n表示散列中数据的个数，m表示散列表中“槽”的个数。

如何设计散列函数

首先，散列函数的设计不能太复杂。过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。

其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即使出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据也特别多的情况。

装载因子过大了怎么办

针对散列表，当装载因子过大时，我们也可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中。

当散列表的装载因子超过某个阈值时，就需要进行扩容。装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于1。

如何避免低效地扩容

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新的散列表中。

当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就变得很快了。

这期间的查询操作怎么来做呢？对于查询操作，为了兼容了新、老散列表中的数据，我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。

如何选择冲突解决方法

  1. 开放寻址法

    优点：开放寻址法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以有效地利用CPU缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。

    缺点：用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

    适用场景：当数据量比较小、装载因子小的时候，适合采用开放寻址法。

  2. 链表法

    优点：首先，链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。

    链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于1的情况。接近1时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

    缺点：链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这方面对于执行效率也有一定的影响。

    适用场景：基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

哈希算法

什么是哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

一个优秀的哈希算法的几点要求

  • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
  • 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的韩系值也大不相同。
  • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。
  • 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

哈希算法的应用

  1. 安全加密

    对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推到出原始数据，第二点是散列冲突的概率要很小。

  2. 唯一标识

    我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取100个字节，从中间取100个字节，从最后再取100个字节，然后将这300个字节放到一块，通过哈希算法（比如MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。

    如果还想继续提高效率，我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。

    如果不存在，那就说明这个图片不在图库中；如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。

  3. 数据校验

    我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

  4. 散列函数

    散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过，相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。

    不仅如此，散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。

  5. 负载均衡

    负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。

    我们可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个IP过来的所有请求，都路由到同一个后端服务器上。

  6. 数据分片

    • 如何统计“搜索关键词”出现的次数

      我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用n台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号。

      这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

    • 如何快速判断图片是否在图库中？

      我们同样可以对数据进行分片，然后采用多机处理。我们准备n台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

      当我们要判断一个图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数n求余取模。假设得到的值是k，那就去编号k的机器构建的散列表中查找。

  7. 分布式存储

    我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

一致性哈希算法：假设我们有k个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成m个小区间（m远大于k），每个机器负责m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

二叉树基础

树

“树”这种数据结构真的很像我们现实生活中的“树”，这里面每个元素我们叫做“节点”；用来连线相邻节点之间的关系，我们叫作“父子关系”。我们把没有父节点的节点叫做根节点，把没有子节点的节点叫作叶子节点或者叶节点。

高度、深度、层的定义

  • 节点的高度=节点到叶子节点的最长路径（边数）
  • 节点的深度=很节点到这个节点所经历的边的个数
  • 节点的层数=节点的深度+1
  • 树的高度=根节点的高度

二叉树

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。

完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

存储二叉树的方法

  • 基于指针或者引用的二叉链式存储法

    每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

  • 基于数组的顺序存储法

    我们把根节点存储在下标i=1的位置，那左子节点存储在下标2i=2的位置，右子节点存储在2i+1=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
/// <summary>
/// 前序遍历
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> PreorderTraversal(TreeNode root)
{
    var list = new List<int>();
    if (root == null) return list;
    list.Add(root.Val);
    list.AddRange(PreorderTraversal(root.Left));
    list.AddRange(PreorderTraversal(root.Right));
    return list;
}
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> InorderTraversal(TreeNode root)
{
    var list = new List<int>();
    if (root == null) return list;
    list.AddRange(InorderTraversal(root.Left));
    list.Add(root.Val);
    list.AddRange(InorderTraversal(root.Right));
    return list;
}
/// <summary>
/// 后序遍历
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> PostorderTraversal(TreeNode root)
{
    var list = new List<int>();
    if (root == null) return list;
    list.AddRange(PostorderTraversal(root.Left));
    list.AddRange(PostorderTraversal(root.Right));
    list.Add(root.Val);
    return list;
}

二叉查找树

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树的操作

  1. 二叉查找树的查找操作

    我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

  2. 二叉查找树的插入操作

    新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

    如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，

    如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

  3. 二叉查找树的删除操作

    针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

    第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为null。

    第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

    第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。

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
public class BinarySearchTree
{
    public TreeNode Tree;
    public TreeNode Find(int data)
    {
        var p = Tree;
        while (p != null)
        {
            if (data < p.Val) p = p.Left;
            else if (data > p.Val) p = p.Right;
            else return p;
        }
        return null;
    }
    public void Insert(int data)
    {
        if (Tree == null)
        {
            Tree = new TreeNode(data);
            return;
        }
        var p = Tree;
        while (p != null)
        {
            if (data > p.Val)
            {
                if (p.Right == null)
                {
                    p.Right = new TreeNode(data);
                    return;
                }
                p = p.Right;
            }
            else
            {
                if (p.Left == null)
                {
                    p.Left = new TreeNode(data);
                    return;
                }
                p = p.Left;
            }
        }
    }
    public void Delete(int data)
    {
        var p = Tree;
        TreeNode pp = null;
        while (p != null && p.Val != data)
        {
            pp = p;
            p = data > p.Val ? p.Right : p.Left;
        }
        if (p == null) return;
        if (p.Left != null && p.Right != null)
        {
            var minP = p.Right;
            var minPP = p;
            while (minP.Left != null)
            {
                minPP = minP;
                minP = minP.Left;
            }
            p.Val = minP.Val;
            p = minP;
            pp = minPP;
        }
        TreeNode child;
        if (p.Left != null) child = p.Left;
        else if (p.Right != null) child = p.Right;
        else child = null;
        if (pp == null) Tree = child;
        else if (pp.Left == p) pp.Left = child;
        else pp.Right = child;
    }
}
支持重复数据的二叉查找树

如果存储的两个对象键值相同，这种情况该怎么处理呢？

两个解决方法

  1. 二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

  2. 每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

    当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

    对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

二叉查找树的时间复杂度

二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度是O(logn)。

二叉查找树和散列表的比较
  1. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列。
  2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。
  3. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
  4. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
  5. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

红黑树

平衡二叉树的严格定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。

红黑树的英文是“Red-Black Tree”，简称R-B Tree。它是一种不严格的平衡二叉查找树，它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。

红黑树的定义

  • 红黑树中的节点，一类被标记为黑色，一类被标记为红色；
  • 根节点是黑色的；
  • 每个叶子节点都是黑色的空节点(NIL)，也就是说，叶子节点不存储数据；
  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。

实现红黑树的基本思想

红黑树的平衡过程：遇到什么样的节点排布没我就对应怎么去调整，只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。

插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。

关于插入操作的平衡调整的两种特殊情况（不会违背红黑树的定义）：

  • 如果插入节点的父节点是黑色的，那么我们什么都不用做，它仍然满足红黑树的定义。
  • 如果插入的节点是根节点，那么我们直接改变它的颜色，把它变成黑色就可以了。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。

我们下面依次来看每种情况的调整过程。提醒你注意下，为了简化描述，我把父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点。

CASE 1：如果关注节点是a，它的叔叔节点d是红色，我们就依次执行下面的操作：

  • 将关注节点a的父节点b、叔叔节点d的颜色都设置成黑色；
  • 将关注节点a的祖父节点c的颜色设置成红色；
  • 关注节点变成a的祖父节点c；
  • 跳到CASE 2或者CASE 3。

CASE 2：如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的右子节点，我们就依次执行下面的操作：

  • 关注节点变成节点a的父节点b；
  • 围绕新的关注节点b左旋；
  • 跳到CASE 3。

CASE 3：如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的左子节点，我们就依次执行下面的操作：

  • 围绕关注节点a的祖父节点c右旋；
  • 将关注节点a的父节点b、兄弟节点c的颜色互换。
  • 调整结束。

删除操作的平衡调整

删除操作的平衡调整分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

  1. 针对删除节点初步调整

    CASE 1：如果要删除的节点是a，它只有一个子节点b，那我们就依次进行下面的操作：

    • 删除节点a，并且把节点b替换到节点a的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
    • 节点a只能是黑色，节点b也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点b改为黑色；
    • 调整结束，不需要进行二次调整。

    CASE 2：如果要删除的节点a有两个非空子节点，并且它的后继节点就是节点a的右子节点c。我们就依次进行下面的操作：

    • 如果节点a的后继节点就是右子节点c，那右子节点c肯定没有左子树。我们把节点a删除，并且将节点c替换到节点a的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
    • 然后把节点c的颜色设置为跟节点a相同的颜色；
    • 如果节点c是黑色，为了不违反红黑树的最后一条定义，我们给节点c的右子节点d多加一个黑色，这个时候节点d就成了“红-黑”或者“黑-黑”；
    • 这个时候，关注节点变成了节点d，第二步的调整操作就会针对关注节点来做。

    CASE 3：如果要删除的是节点a，它有两个非空子节点，并且节点a的后继节点不是右子节点，我们就依次进行下面的操作：

    • 找到后继节点d，并将它删除，删除后继节点d的过程参照CASE 1；
    • 将节点a替换成后继节点d；
    • 把节点d的颜色设置为跟节点a相同的颜色；
    • 如果节点d是黑色，为了不违反红黑树的最后一条定义，我们给节点d的右子节点c多加一个黑色，这个时候节点c就成了“红-黑”或者“黑-黑”；
    • 这个时候，关注节点变成了节点c，第二步的调整操作就会针对关注节点来做。

  2. 针对关注节点进行二次调整

    CASE 1：如果关注节点是a，它的兄弟节点c是红色的，我们就依次进行下面的操作：

    • 围绕关注节点a的父节点b左旋；
    • 关注节点a的父节点b和祖父节点c交换颜色；
    • 关注节点不变；
    • 继续从四种情况中选择适合的规则来调整。

    CASE 2：如果关注节点是a，它的兄弟节点c是黑色的，并且节点c的左右子节点d、e都是黑色的，我们就依次进行下面的操作：

    • 将关注节点a的兄弟节点c的颜色变成红色；
    • 从关注节点a中去掉一个黑色，这个时候节点a就是单纯的红色或者黑色；
    • 给关注节点a的父节点b添加一个黑色，这个时候节点b就变成了“红-黑”或者“黑-黑”；
    • 关注节点从a变成其父节点b；
    • 继续从四种情况中选择符合的规则来调整。

    CASE 3：如果关注节点是a，它的兄弟节点c是黑色，c的左子节点d是红色，c的右子节点e是黑色，我们就依次进行下面的操作：

    • 围绕关注节点a的兄弟节点c右旋；
    • 节点c和节点d交换颜色；
    • 关注节点不变；
    • 跳转到CASE 4，继续调整。

    CASE 4：如果关注节点a的兄弟节点c是黑色的，并且c的右子节点是红色的，我们就依次进行下面的操作：

    • 围绕关注节点a的父节点b左旋；
    • 将关注节点a的兄弟节点c的颜色，跟关注节点a的父节点b设置成相同的颜色；
    • 将关注节点a的父节点b的颜色设置为黑色；
    • 从关注节点a中去掉一个黑色，节点a就变成了单纯的红色或者黑色；
    • 将关注节点a的叔叔节点e设置为黑色；
    • 调整结束。
读书笔记
#读书笔记 #技术
数据结构与算法之美（三）
http://blog.chcaty.cn/2021/07/26/shu-ju-jie-gou-yu-suan-fa-zhi-mei-san/
作者
caty
发布于
2021年7月26日
许可协议