红黑树---面试

BST二叉搜索树

1. 树中插入的是随机数据时，执行效果很好
2. 树中插入的是有序或逆序的数据，那么二叉搜索树就变得非平衡，换句话说就变成了一个链表。它快速查找、插入和删除指定数据项的能力就丧失。
   博客
   图片来自博客

• 特性

1. 左子树上所有结点的值均小于或等于它的根结点的值
2. 右子树上所有结点的值均大于或等于它的根结点的值
   博客
   图片来自博客
   二叉搜索树运用二分查找的思想，查找所需最大次数等同于二叉查找树的高度

红黑树

红黑树是一种自平衡的二叉查找树

• 红黑树的性质
  有两个特征:1,节点有颜色。2,在插入和删除的过程中，要遵循保持这些颜色的不同排列规则。红黑树的规则如下:

1. 每个结点要么是红的，要么是黑的。
2. 根结点是黑的
3. 如果一个结点是红的，那么它的两个儿子都是黑的(从每个叶子到根的所有路径上不能有两个连续的红色结点)
4. 对于任一结点而言，其到叶结点或空子节点的每一条路径都包含相同数目的黑结点。
5. 每个叶结点(叶结点即指树尾端或NULL结点)是黑的
   图片来自博客
   这些规则保证红黑树的自平衡，红黑树从根到叶子的最长路径不会超过最短路径的2倍

• 红黑树的节点

public class RBNode<T extends Comparable<T>>{
    boolean color; //颜色
    T key; //关键字(键值)
    RBNode<T> left; //左子节点
    RBNode<T> right; //右子节点
    RBNode<T> parent; //父节点

    public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
        this.key = key;
        this.color = color;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    public T getKey() {
        return key;
    }

    public String toString() {
        return "" + key + (this.color == RED? "R" : "B");
    }
}

平衡性的修正

• 变色
  下图为红黑树的一部分(子树)。新插入的结点Y是红色结点，它的父亲结点x也是红色的，不符合规则3，因此，可以把结点X从红色变成黑色:

  
  image.png

• 左旋
  逆时针旋转红黑树的两个结点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子，如图所示:身为右孩子的Y取代了X的位置，而X变成自己的左孩子，此为左旋转。

  
  图片见博客

• 右旋
  顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为自己的右孩子，如图所示:身为左孩子的Y取代X的位置，而X变成自己的右孩子。此为右旋转。

  
  image.png

• 红黑树的插入的五种情况

1. 新结点A位于树根，没有父结点。

   
   image.png
   

   这种局面，直接让新结点变色为黑色，规则2得到满足。同时，黑色的根结点使得每条路径上的黑色结点数目都增加1，所有没有打破规则4。

2. 新结点(B)的父节点是黑色的。
   此时，新插入的红色结点B并没有打破红黑树的规则，所以不需要做任何调整。

   
   image.png

3. 新结点(D)的父节点和其叔叔节点(祖父节点的另一个子节点)均为红色的。

   
   image.png
   

   这时，两个红色结点B和D连续，违反规则3。因此先让结点B变成黑色:

   
   image.png
   此时，结点B所在路径凭空多了一个黑色结点，打破规则5.因此让结点A变成红色:
   image.png
   

   这个时候，结点A和C又成为连续的红色结点，我们再让结点c 变成黑色:

   
   image.png
   经过上面的调整，这一局部重新符合红黑树的规则。

4. 新结点(D)的父节点是红色的，叔叔节点是黑色的或没有叔叔节点，且新结点是其父节点的右孩子，父结点(B)是祖父结点的左孩子。

   
   image.png
   

   以结点B为轴，做一次左旋转，使得新结点D成为父结点，原来的父节点B成为D的左孩子:

   
   image.png
   这么一来，进入局面5。

5. 新结点(D)的父节点是红色，叔叔节点是黑色或没有叔叔，且新结点是其父节点的左孩子，父结点(B)是祖父结点的左孩子。
   

   image.png
   以结点A为轴，做一次右旋转，使得结点B成为祖父结点，结点A成为结点B的右孩子。
   image.png
   接下来，让结点B变成黑色，结点A变成红色:
   image.png
   经过上面的调整，这一局部重新符合红黑树的规则。
   如果情况4当中的父结点B是祖父结点A的右孩子:则成为情况5的镜像，原本的右旋操作改为左旋；
   如果情况5当中的父结点B是祖父结点A的右孩子:则成为情况4的镜像，原本的左旋操作改为右旋。

多种情况混合

给定一颗红黑树，新插入的结点是21:

image.png
显然，新结点21和它的父结点22是连续的红色结点，违背规则3。这种情况符合3:新结点的父结点和叔叔结点都是红色
经过三次变色，22变为黑色，25变为红色，27变为黑色:
image.png
调整后，以结点25为根的子树符合红黑树规则，但结点25和结点17成为连续的红色结点，违背规则3。
于是，我们把结点25看做一个新结点，正好符合情况5的镜像:
新结点的父结点是红色，叔叔结点是黑色或没有叔叔，且新结点是父结点的右孩子，父结点是祖父结点的右孩子
以根结点13为轴进行左旋转，使得结点17成为新的根结点:
image.png
接下来，让结点17变为黑色，结点13变为红色:
image.png
如此一来，红黑树变得重新符合规则。

删除操作

**第一步: ** 如果待删除结点有两个非空的孩子结点，转换成待删除结点只有一个孩子(或没有孩子)的情况。(ps:10是黑色结点)

image.png
如图是一颗红黑树的局部，标数字的三角形代表任意形态的子树，假设结点8是待删除结点。因为结点8有两个孩子，选择仅大于8的结点10复制到8的位置，结点颜色变成待删除结点的颜色：
image.png
接下来，删除红色的结点10:
image.png
红色结点10能成为仅大于8的结点，必定没有左孩子结点，所以问题转换成待删除结点只有一个右孩子(或没有孩子)的情况。
第二步: 根据待删除结点和其唯一子结点的颜色，分情况处理。
情况一: 自身是红色，子结点是黑色:
image.png
这种情况最简单，按照二叉查找树的删除操作，删除结点1即可：
image.png
情况二: 自身是红色，子结点是黑色:
image.png
这种情况，首先按照二叉查找树的删除操作，删除结点1:
image.png
此时，这条路径凭空减少一个黑色结点，那么把结点2变成黑色即可:
image.png
情况3: 自身是黑色，子结点也是黑色或者子结点是空叶子结点:
image.png
这种情况最复杂，涉及很多变化。首先按照二叉查找树的删除操作，删除结点1:
image.png
显然，这条路径上减少一个黑色结点，而且结点2再怎么变色也解决不了。这时进入第三步，专门解决父子双黑的情况。
第三步:遇到双黑结点，在子结点顶替父结点之后，分为6种子情况处理:
子情况1: 结点2是红黑树的根结点
image.png
此时所有路径都减少一个黑色结点，并未打破规则，不需要调整。
**子情况2: ** 结点2的父亲、兄弟、侄子结点都是黑色:
image.png
此时，直接把结点2的兄弟结点B改为红色:
image.png
这样一来，原来结点2所在的路径少了一个黑色结点，现在结点B所在的路径也少一个黑色结点，两边“扯平”。
结点A以下的每条路径都减少一个黑色结点，与结点A之外的其他路径不平衡。此时看情况3
**情况3: ** 结点2的兄弟结点是红色:
image.png
首先，以结点2的父节点A为轴，进行左旋:
image.png
然后结点A变成红色，结点B变成黑色:
image.png
子情况4: 结点2的父结点是红色，兄弟和侄子结点是黑色:
image.png
直接把结点2的父结点A变成黑色，兄弟结点B变成红色:
image.png
这样，结点2的路径补充黑色结点，而结点B的路径并没有减少黑色结点，重合红黑树的规则。
子情况5 结点2的父结点随意，兄弟结点B是黑色右孩子，左侄子结点是红色，右侄子结点是黑色:
image.png
这时，以结点2的兄弟结点B为轴进行右旋
image.png
接下来结点B变成红色，结点C变成黑色:
image.png
转换成子情况6
子情况6: 结点2的父结点随意，兄弟结点B是黑色右孩子，右侄子结点是红色:
image.png
首先，以结点2的父结点A为轴左旋:
image.png
接下来让结点A和结点B的颜色交换，并且结点D变为黑色:
image.png
经过结点2的路径由(随意加黑)变成(随意+黑+黑)，补充了一个黑色结点
经过结点D的路径由(随意+黑+红)变成(随意+黑)，黑色结点并没有减少。这时，重新符合红黑树规则。

红黑树的各种操作的时间复杂度

能保证在最坏情况下，基本的动态几何操作的时间均为O(logn)

红黑树相比于BST和AVL树有什么优点?

AVL树是严格平衡的二叉树，要求每个节点的左右子树高度差不超过1。
红黑树要求任何一条路径的长度不超过其他路径的2倍。
所以AVL树的查找效率更高，但平衡调整的成本更高。
在需要频繁查找时，选用AVL树更合适，
在需要频繁插入删除时，选用红黑树更合适。
我只是搬过来，自己理解理解
大部分内容来自公众号
大部分内容来自公众号