笔记

红黑树的基本性质与操作

张天宇 on 2020-06-12

本文介绍了红黑树的基本性质和基本操作。

红黑树

红黑树本质上是一种带颜色的二叉排序树，同时带有一定的规则，保证了一种平衡。

插入、查找、删除的最坏时间复杂度都为$O(logn)$。

在Java集合框架中，HashMap、TreeMap、TreeSet等都有红黑树的应用。

黑色高度：从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度。

5个特性

在原有的二叉查找树基础上增加了五个特性：

  1. 每个节点要么是红色，要么是黑色；
  2. 根节点永远是黑色的；
  3. 所有的叶子节点都是黑色(这里说的叶子节点实际上是为null的节点)；
  4. 每个红色节点的两个子节点一定都是黑色；
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

Java中实现的红黑树将使用null来代表空节点，因此在遍历红黑树时，看不到黑色的叶子节点，反而看到每个叶子节点都是黑色的。

性质4的意思是，从每个根到节点的路径上不会有两个连续的红色节点，但是黑色节点是可以连续的。因此如果给定黑色节点的个数N，最短路径的情况是连续N个黑色，树的高度是N-1；最长路径的情况是节点红黑相间，树的高度是2(N-1)。

红黑树的平衡插入

步骤

  • 首先和二叉查找树的插入一样，查找、插入；
  • 调整结构，保证满足红黑树状态；
    • 对节点进行重新着色
    • 对树进行相关的旋转操作

调整思想

插入一个节点会担心特征45是否满足，数学上将多个未知数化解为一个未知数。即把插入的节点直接染成红色，就不会再影响特征5，专心调整特征4就好了。染成红色后，我们只关心父节点是否为红，如果是红色，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，当然这些操作不能同时影响不同路径上的黑色节点数一致的规则。

插入实例

情况1：父亲节点和叔叔节点都是红色

将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。

情况2：父节点是红色，叔叔节点为黑色

父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋。最后，把根结点涂为黑色，整棵红黑树便重新恢复了平衡。

情况3：父节点是红色，叔叔节点为黑色，节点为父节点的右孩子

当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。

红黑树的删除调整

删除

待删除的节点按照儿子的个数分为三种，假设要删除得节点为Z：

  1. 节点Z没有孩子节点，这时候将Z节点删除，然后判断节点Z是否为黑色得，若Z为黑色的，则在删除后会导致黑高不相等。于是需要对红黑树进行调整。
  2. 节点Z只有一个孩子节点，此时直接使用其孩子节点代替Z节点，然后判断删除的Z节点是否为黑，如果为黑，则需要对红黑树进行调整。
  3. 节点Z有左后孩子节点，这时候首先找到Z节点的后继节点Y，这时候又有两种情况：第一种情况是Y是Z的右孩子节点，第二种情况是Y不是Z的右孩子节点，当Y不是Z的右孩子时，这时候需要把Y节点从原来的地方剥离出来，然后替换掉节点Z，并由Y的右孩子X填补Y的位置。(这里Y是不可能有左孩子节点的，如果有的话就不是Z的后继了)

在删除中，第一二情况中，如果删除的是红色，则无需进行调整；如果删除的节点是黑色的，则需要对红黑树进行调整。

第三种情况中，如果通过使用Z的后继节点Y替换Z节点，然后使用Y的右孩子来填补Y的位置。在此过程中需要将节点Y进行移动，由于移动之后的Y节点保持了原来Z的颜色，而X节点在代替Y节点之后可能会出现问题，当然只会在Y是黑色时候出现问题，当Y的节点为红色时候，移动时红黑树的性质不会被破坏，Y节点为黑色时候，一定会出现黑高的不相等，也可能会出现两个连续的红色节点，需要进行调整。

调整

在上文中探讨的第一二种情况中，如果删除的节点Z是黑色的，这时候为了黑高不被破坏，我们可以将替代Z的节点X再加一种额外的黑色，此时节点X可能是双黑或者红黑，若为红黑则只需要删除其中的红色保留黑色即可，如果为双黑色，需要做进一步的调整。

第三种情况中，如果移动的节点Y是黑色的，则将代替节点Y的节点X额外增加一种黑色，使得数的黑色高度相等。同样此时X节点可能成为双重黑色或红黑色，若是红黑色则只需要保存黑色即可，若是双黑色则需要进行调整。

当节点X具有双重黑色的特性时候需要对其进行调整，这时候有两种情况，分别是：X是左孩子节点和X是右孩子节点。由于这两种情况是对称的，在此只对X是左孩子节点情况进行讨论。

  • X的兄弟节点W是红色的。

    因为X的兄弟节点W为红色，不能将黑色直接上移，所以对其做一些变换，首先将W变为黑色，X的父节点变为红色，然后以兄弟节点为中心进行左旋。旋转后的X的兄弟节点为原来W的左孩子，此节点必为黑色，因为W为红色。通过这一步，我们能确保X的兄弟节点为黑色，为下一步调整做好准备。

  • X的兄弟节点W是黑色的，并且W的两个子节点也是黑色的。

    通过将X和W中的一个黑色上移到X的父节点，使得X的父节点变成新的X节点。在将X上的一个黑色上移后还剩下了一个黑色，将W的黑色上移之后W只剩下了红色。若新的X为红黑色，则将新的X变为黑色，调整结束；若新的X为双黑色时，并且这时候的X不为根节点，继续调整，否则结束。

  • X的兄弟节点是黑色的，并且W的左孩子为红色，右孩子为黑色。这种情况下不能提取X和W的黑色上移，因为W的孩子有红色节点。此种情况W的左孩子为红色，右孩子为黑色。我们首先以W为中心进行右旋，并且将W的左孩子的颜色修改为黑色，将W修改为红色。这时候此种情况就转化为了第四种，即X的兄弟节点W的右孩子为红色节点。

  • X的兄弟节点W是黑色的，并且W的右孩子为红色，左孩子颜色任意。这时，首先将W的颜色改为其父节点的颜色，X的父节点和W的右孩子修改为黑色。然后以X的父节点为中心进行左旋，最后将X指向其根节点。




标签
笔记