map中为何使用红黑树而不是二叉平衡树?_【算法】红黑树

红黑树在JDK中应用很广泛，像HashMap、TreeMap等使用树结构的地方几乎都用了红黑树。这篇文章将透彻的分析红黑树原理。

我写这篇文章还有一个理由，就是国内的关于红黑树的文章太水了，互相抄，一点都不通，我看了半天看不懂！千万不要说程序员会用就行了，有的时候还真需要一股钻研的劲头才能成为一名优秀的人。这篇前半部分是汇总过来的，红黑树删除部分是翻译的一篇英文的，我不敢保证人人都能看懂我写的，不过我感觉我自己是懂的.....如果不懂评论区问我吧。

红黑树是平衡二叉查找树的一种。为了深入理解红黑树，我们需要从二叉查找树开始讲起。

BST

二叉查找树（Binary Search Tree，简称BST）或二叉搜索树，是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。

在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当左右高度差值小于等于1，我们就说二叉查找树是平衡的。需要注意二叉查找树不需要是满树。

查找：

T  key = a search key
Node root = point to the root of a BST

while(true){
    if(root==null){
        break;
    }
    if(root.value.equals(key)){
        return root;
    }
    else if(key.compareTo(root.value)<0){
        root = root.left;
    }
    else{
        root = root.right;
    }
}
return null;

当BST查找的时候，先与当前节点进行比较：

如果相等的话就返回当前节点；
如果少于当前节点则继续查找当前节点的左节点；
如果大于当前节点则继续查找当前节点的右节点。

直到当前节点指针为空或者查找到对应的节点，程序查找结束。

插入：

Node node = create a new node with specify value
Node root = point the root node of a BST
Node parent = null;

//find the parent node to append the new node
while(true){
   if(root==null)break;
   parent = root;
   if(node.value.compareTo(root.value)<=0){
      root = root.left;  
   }else{
      root = root.right;
   } 
}
if(parent!=null){
   if(node.value.compareTo(parent.value)<=0){//append to left
      parent.left = node;
   }else{//append to right
      parent.right = node;
   }
}

插入操作先通过循环查找到待插入的节点的父节点，和查找父节点的逻辑一样，都是比大小，小的往左，大的往右。找到父节点后，对比父节点，小的就插入到父节点的左节点，大就插入到父节点的右节点上。

删除

删除操作的步骤如下：

查找到要删除的节点。
如果待删除的节点是叶子节点，则直接删除。
如果待删除的节点不是叶子节点，则先找到待删除节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后继节点。

如果我们需要删除一个结点，而且在删除之后，依然满足二叉查找树的数据排序策略。此时删除操作可分为一下三种情况。如下

二叉查找树删除节点可以分成三种情况：

（1）删除叶子节点

叶子节点删除是最简单的情况，由于叶子节点没有左右子树，删除后不会破坏原有的树形结构，所以我们只需要找到节点并且把它置为null即可。

（2）被删除的节点只有一个子节点

我们只需将它的子节点指向它的父节点。

（3）被删除的节点左右子树都有

这种情况是比较复杂的，为了不破坏二叉查找书的结构，我们可以按照以下操作进行：

找出左子树中最大或者右子树中最小的值val
将当前节点的值替换为val
在左子树或者右子树中找到val删除

或者说的简单一点，直接找它中序排序的下一个节点来替换他自己。

Note：

由于二叉查找树的性质，如果将当前节点替换为左子树中最大的或者右子树中最小的一定不会破坏二叉查找树的结构。

BST存在的问题

BST存在的主要问题是，数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。

RBTree

基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的持久数据结构之一，在计算几何中也有重要作用。值得一提的是，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。

RBTree的定义

RBTree的定义如下:

任何一个节点都有颜色，黑色或者红色
根节点是黑色的
父子节点之间不能出现两个连续的红节点
任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
空节点被认为是黑色的

数据结构表示如下：

class  Node<T>{
   public  T value;
   public   Node<T> parent;
   public   boolean isRed;
   public   Node<T> left;
   public   Node<T> right;
}

RBTree在理论上还是一棵BST树，但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN,logN+1]（理论上，极端的情况下可以出现RBTree的高度达到2*logN，但实际上很难遇到）。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。

RBTree的旋转操作

旋转操作(Rotate)的目的是使节点颜色符合定义，让RBTree的高度达到平衡。
Rotate分为left-rotate（左旋）和right-rotate（右旋），区分左旋和右旋的方法是：待旋转的节点从左边上升到父节点就是右旋，待旋转的节点从右边上升到父节点就是左旋。

RBTree的查找操作

RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。

RBTree的插入操作

RBTree的插入与BST的插入方式是一致的，只不过是在插入过后，可能会导致树的不平衡，这时就需要对树进行旋转操作和颜色修复（在这里简称插入修复），使得它符合RBTree的定义。

新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。

插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：

叔叔节点也为红色。
叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。

可以说叔叔节点不是红就是null！

插入操作-case 1

case 1的操作是将父节点和叔叔节点与祖父节点的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。

插入操作-case 2

case 2的操作是将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话，只要将操作变成左旋就可以了。

插入操作-case 3

case 3的操作是将C节点进行左旋，这样就从case 3转换成case 2了，然后针对case 2进行操作处理就行了。case 2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构，则只需要将对应的左旋变成右旋，右旋变成左旋即可。

插入操作的总结

插入后的修复操作是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。之所以会向上回溯是由于case 1操作会将父节点，叔叔节点和祖父节点进行换颜色，有可能会导致祖父节点不平衡(红黑树定义3)。这个时候需要对祖父节点为起点进行调节（向上回溯）。

祖父节点调节后如果还是遇到它的祖父颜色问题，操作就会继续向上回溯，直到root节点为止，根据定义root节点永远是黑色的。在向上的追溯的过程中，针对插入的3中情况进行调节。直到符合红黑树的定义为止。直到牵涉的节点都符合了红黑树的定义，修复操作结束。

如果上面的3中情况如果对应的操作是在右子树上，做对应的镜像操作就是了。

RBTree的删除操作

删除操作首先需要做的也是BST的删除操作，删除操作会删除对应的节点，如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置。删除后就需要做删除修复操作，使的树符合红黑树的定义，符合定义的红黑树高度是平衡的。

删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。

删除修复操作分为四种情况(删除黑节点后)：

前提条件：和二叉搜索树的删除操作一样，我们可以把被删除的节点的中序后继复制到自己的位置，就可以保证红黑树的颜色结构不变，又不破坏二叉搜索树的结构。这样我们把所有删除的节点都“转换”成叶子节点的删除了。因为此叶子节点是被删除节点的中序后继，所以要么它有一个子节点要么一个都没有！ok，那我们可以总结出下面4中情况：

1、转化以后，被删除节点是红节点。

直接把该节点去掉就行了，因为红节点的删除不会影响红黑树的属性约束。

2、转化以后，被删除节点是黑节点，子节点是红的。

这时我们不能贸然把子节点移上来，因为子节点时红的有可能和被删除节点的父节点冲突，且黑节点数变化了。所以我们可以把子节点的颜色变为黑色再移上来替换被删除节点，是不是解决了？既不会影响上面的父节点，红黑结构也没有变，

3、转化以后，被删除节点是黑节点，子节点是黑的。