开发者社区> 行者武松> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

红黑树深入剖析及Java实现

简介:
+关注继续查看

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

BST

二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。

在理想的情况下,二叉查找树增删查改的时间复杂度为O(logN)(其中N为节点数),最坏的情况下为O(N)。当它的高度为logN+1时,我们就说二叉查找树是平衡的。

BST

BST的查找操作


  1. T  key = a search key 
  2. Node root = point to the root of a BST 
  3.  
  4. while(true){ 
  5.     if(root==null){ 
  6.         break
  7.     } 
  8.     if(root.value.equals(key)){ 
  9.         return root; 
  10.     } 
  11.     else if(key.compareTo(root.value)<0){ 
  12.         root = root.left; 
  13.     } 
  14.     else
  15.         root = root.right; 
  16.     } 
  17. return null

从程序中可以看出,当BST查找的时候,先与当前节点进行比较:

  • 如果相等的话就返回当前节点;

  • 如果少于当前节点则继续查找当前节点的左节点;

  • 如果大于当前节点则继续查找当前节点的右节点。

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

BST的插入操作


  1. Node node = create a new node with specify value 
  2. Node root = point the root node of a BST 
  3. Node parent = null
  4.  
  5. //find the parent node to append the new node 
  6. while(true){ 
  7.    if(root==null)break
  8.    parent = root; 
  9.    if(node.value.compareTo(root.value)<=0){ 
  10.       root = root.left;   
  11.    }else
  12.       root = root.right; 
  13.    }  
  14. if(parent!=null){ 
  15.    if(node.value.compareTo(parent.value)<=0){//append to left 
  16.       parent.left = node; 
  17.    }else{//append to right 
  18.       parent.right = node; 
  19.    } 

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

BST的删除操作

删除操作的步骤如下:

  1. 查找到要删除的节点。

  2. 如果待删除的节点是叶子节点,则直接删除。

  3. 如果待删除的节点不是叶子节点,则先找到待删除节点的中序遍历的后继节点,用该后继节点的值替换待删除的节点的值,然后删除后继节点。

BST remove

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的定义如下:

  1. 任何一个节点都有颜色,黑色或者红色

  2. 根节点是黑色的

  3. 父子节点之间不能出现两个连续的红节点

  4. 任何一个节点向下遍历到其子孙的叶子节点,所经过的黑节点个数必须相等

  5. 空节点被认为是黑色的

数据结构表示如下:


  1. class  Node<T>{ 
  2.    public  T value; 
  3.    public   Node<T> parent; 
  4.    public   boolean isRed; 
  5.    public   Node<T> left; 
  6.    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(右旋),区分左旋和右旋的方法是:待旋转的节点从左边上升到父节点就是右旋,待旋转的节点从右边上升到父节点就是左旋。

BST remove

RBTree的查找操作

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

RBTree的插入操作

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

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

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

  1. 叔叔节点也为红色。

  2. 叔叔节点为空,且祖父节点、父节点和新节点处于一条斜线上。

  3. 叔叔节点为空,且祖父节点、父节点和新节点不处于一条斜线上。

插入操作-case 1

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

插入修复case 1

插入操作-case 2

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

插入修复case 2

插入操作-case 3

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

插入修复case 3

插入操作的总结

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

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

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

RBTree的删除操作

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

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

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

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

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

  1. 待删除的节点的兄弟节点是红色的节点。

  2. 待删除的节点的兄弟节点是黑色的节点,且兄弟节点的子节点都是黑色的。

  3. 待调整的节点的兄弟节点是黑色的节点,且兄弟节点的左子节点是红色的,右节点是黑色的(兄弟节点在右边),如果兄弟节点在左边的话,就是兄弟节点的右子节点是红色的,左节点是黑色的。

  4. 待调整的节点的兄弟节点是黑色的节点,且右子节点是是红色的(兄弟节点在右边),如果兄弟节点在左边,则就是对应的就是左节点是红色的。

删除操作-case 1

由于兄弟节点是红色节点的时候,无法借调黑节点,所以需要将兄弟节点提升到父节点,由于兄弟节点是红色的,根据RBTree的定义,兄弟节点的子节点是黑色的,就可以从它的子节点借调了。

case 1这样转换之后就会变成后面的case 2,case 3,或者case 4进行处理了。上升操作需要对C做一个左旋操作,如果是镜像结构的树只需要做对应的右旋操作即可。

之所以要做case 1操作是因为兄弟节点是红色的,无法借到一个黑节点来填补删除的黑节点。

删除情况1

删除操作-case 2

case 2的删除操作是由于兄弟节点可以消除一个黑色节点,因为兄弟节点和兄弟节点的子节点都是黑色的,所以可以将兄弟节点变红,这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点,继续向上调整,直到整颗树的颜色符合RBTree的定义为止。

case 2这种情况下之所以要将兄弟节点变红,是因为如果把兄弟节点借调过来,会导致兄弟的结构不符合RBTree的定义,这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后,达到了局部的平衡了,但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点,接着进行修复操作。

删除情况2

删除操作-case 3

case 3的删除操作是一个中间步骤,它的目的是将左边的红色节点借调过来,这样就可以转换成case 4状态了,在case 4状态下可以将D,E节点都阶段过来,通过将两个节点变成黑色来保证红黑树的整体平衡。

之所以说case-3是一个中间状态,是因为根据红黑树的定义来说,下图并不是平衡的,他是通过case 2操作完后向上回溯出现的状态。之所以会出现case 3和后面的case 4的情况,是因为可以通过借用侄子节点的红色,变成黑色来符合红黑树定义4.

删除情况3

删除操作-case 4

Case 4的操作是真正的节点借调操作,通过将兄弟节点以及兄弟节点的右节点借调过来,并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的,这样的话,整棵树还是符合RBTree的定义的。

Case 4这种情况的发生只有在待删除的节点的兄弟节点为黑,且子节点不全部为黑,才有可能借调到两个节点来做黑节点使用,从而保持整棵树都符合红黑树的定义。

删除情况4

删除操作的总结

红黑树的删除操作是最复杂的操作,复杂的地方就在于当删除了黑色节点的时候,如何从兄弟节点去借调节点,以保证树的颜色符合定义。由于红色的兄弟节点是没法借调出黑节点的,这样只能通过选择操作让他上升到父节点,而由于它是红节点,所以它的子节点就是黑的,可以借调。

对于兄弟节点是黑色节点的可以分成3种情况来处理,当所以的兄弟节点的子节点都是黑色节点时,可以直接将兄弟节点变红,这样局部的红黑树颜色是符合定义的。但是整颗树不一定是符合红黑树定义的,需要往上追溯继续调整。

对于兄弟节点的子节点为左红右黑或者 (全部为红,右红左黑)这两种情况,可以先将前面的情况通过选择转换为后一种情况,在后一种情况下,因为兄弟节点为黑,兄弟节点的右节点为红,可以借调出两个节点出来做黑节点,这样就可以保证删除了黑节点,整棵树还是符合红黑树的定义的,因为黑色节点的个数没有改变。

红黑树的删除操作是遇到删除的节点为红色,或者追溯调整到了root节点,这时删除的修复操作完毕。

RBTree的Java实现


  1. public class RBTreeNode<T extends Comparable<T>> { 
  2.     private T value;//node value 
  3.     private RBTreeNode<T> left;//left child pointer 
  4.     private RBTreeNode<T> right;//right child pointer 
  5.     private RBTreeNode<T> parent;//parent pointer 
  6.     private boolean red;//color is red or not red 
  7.  
  8.     public RBTreeNode(){} 
  9.     public RBTreeNode(T value){this.value=value;} 
  10.     public RBTreeNode(T value,boolean isRed){this.value=value;this.red = isRed;} 
  11.  
  12.     public T getValue() { 
  13.         return value; 
  14.     } 
  15.     void setValue(T value) { 
  16.         this.value = value; 
  17.     } 
  18.     RBTreeNode<T> getLeft() { 
  19.         return left; 
  20.     } 
  21.     void setLeft(RBTreeNode<T> left) { 
  22.         this.left = left; 
  23.     } 
  24.     RBTreeNode<T> getRight() { 
  25.         return right; 
  26.     } 
  27.     void setRight(RBTreeNode<T> right) { 
  28.         this.right = right; 
  29.     } 
  30.     RBTreeNode<T> getParent() { 
  31.         return parent; 
  32.     } 
  33.     void setParent(RBTreeNode<T> parent) { 
  34.         this.parent = parent; 
  35.     } 
  36.     boolean isRed() { 
  37.         return red; 
  38.     } 
  39.     boolean isBlack(){ 
  40.         return !red; 
  41.     } 
  42.     /** 
  43.     * is leaf node 
  44.     **/ 
  45.     boolean isLeaf(){ 
  46.         return left==null && right==null
  47.     } 
  48.  
  49.     void setRed(boolean red) { 
  50.         this.red = red; 
  51.     } 
  52.  
  53.     void makeRed(){ 
  54.         red=true
  55.     } 
  56.     void makeBlack(){ 
  57.         red=false
  58.     } 
  59.     @Override 
  60.     public String toString(){ 
  61.         return value.toString(); 
  62.     } 
  63.  
  64. public class RBTree<T extends Comparable<T>> { 
  65.     private final RBTreeNode<T> root; 
  66.     //node number 
  67.     private java.util.concurrent.atomic.AtomicLong size =  
  68.                     new java.util.concurrent.atomic.AtomicLong(0); 
  69.  
  70.     //in overwrite mode,all node's value can not  has same    value 
  71.     //in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode. 
  72.     private volatile boolean overrideMode=true
  73.  
  74.     public RBTree(){ 
  75.         this.root = new RBTreeNode<T>(); 
  76.     } 
  77.  
  78.     public RBTree(boolean overrideMode){ 
  79.         this(); 
  80.         this.overrideMode=overrideMode; 
  81.     } 
  82.  
  83.     public boolean isOverrideMode() { 
  84.         return overrideMode; 
  85.     } 
  86.  
  87.     public void setOverrideMode(boolean overrideMode) { 
  88.         this.overrideMode = overrideMode; 
  89.     } 
  90.  
  91.     /** 
  92.      * number of tree number 
  93.      * @return 
  94.      */ 
  95.     public long getSize() { 
  96.         return size.get(); 
  97.     } 
  98.     /** 
  99.      * get the root node 
  100.      * @return 
  101.      */ 
  102.     private RBTreeNode<T> getRoot(){ 
  103.         return root.getLeft(); 
  104.     } 
  105.  
  106.     /** 
  107.      * add value to a new node,if this value exist in this tree, 
  108.      * if value exist,it will return the exist value.otherwise return null 
  109.      * if override mode is true,if value exist in the tree, 
  110.      * it will override the old value in the tree 
  111.      *  
  112.      * @param value 
  113.      * @return 
  114.      */ 
  115.     public T addNode(T value){ 
  116.         RBTreeNode<T> t = new RBTreeNode<T>(value); 
  117.         return addNode(t); 
  118.     } 
  119.     /** 
  120.      * find the value by give value(include key,key used for search, 
  121.      * other field is not used,@see compare method).if this value not exist return null 
  122.      * @param value 
  123.      * @return 
  124.      */ 
  125.     public T find(T value){ 
  126.         RBTreeNode<T> dataRoot = getRoot(); 
  127.         while(dataRoot!=null){ 
  128.             int cmp = dataRoot.getValue().compareTo(value); 
  129.             if(cmp<0){ 
  130.                 dataRoot = dataRoot.getRight(); 
  131.             }else if(cmp>0){ 
  132.                 dataRoot = dataRoot.getLeft(); 
  133.             }else
  134.                 return dataRoot.getValue(); 
  135.             } 
  136.         } 
  137.         return null
  138.     } 
  139.     /** 
  140.      * remove the node by give value,if this value not exists in tree return null 
  141.      * @param value include search key 
  142.      * @return the value contain in the removed node 
  143.      */ 
  144.     public T remove(T value){ 
  145.         RBTreeNode<T> dataRoot = getRoot(); 
  146.         RBTreeNode<T> parent = root; 
  147.  
  148.         while(dataRoot!=null){ 
  149.             int cmp = dataRoot.getValue().compareTo(value); 
  150.             if(cmp<0){ 
  151.                 parent = dataRoot; 
  152.                 dataRoot = dataRoot.getRight(); 
  153.             }else if(cmp>0){ 
  154.                 parent = dataRoot; 
  155.                 dataRoot = dataRoot.getLeft(); 
  156.             }else
  157.                 if(dataRoot.getRight()!=null){ 
  158.                     RBTreeNode<T> min = removeMin(dataRoot.getRight()); 
  159.                     //x used for fix color balance 
  160.                     RBTreeNode<T> x = min.getRight()==null ? min.getParent() : min.getRight(); 
  161.                     boolean isParent = min.getRight()==null
  162.  
  163.                     min.setLeft(dataRoot.getLeft()); 
  164.                     setParent(dataRoot.getLeft(),min); 
  165.                     if(parent.getLeft()==dataRoot){ 
  166.                         parent.setLeft(min); 
  167.                     }else
  168.                         parent.setRight(min); 
  169.                     } 
  170.                     setParent(min,parent); 
  171.  
  172.                     boolean curMinIsBlack = min.isBlack(); 
  173.                     //inherit dataRoot's color 
  174.                     min.setRed(dataRoot.isRed()); 
  175.  
  176.                     if(min!=dataRoot.getRight()){ 
  177.                         min.setRight(dataRoot.getRight()); 
  178.                         setParent(dataRoot.getRight(),min); 
  179.                     } 
  180.                     //remove a black node,need fix color 
  181.                     if(curMinIsBlack){ 
  182.                         if(min!=dataRoot.getRight()){ 
  183.                             fixRemove(x,isParent); 
  184.                         }else if(min.getRight()!=null){ 
  185.                             fixRemove(min.getRight(),false); 
  186.                         }else
  187.                             fixRemove(min,true); 
  188.                         } 
  189.                     } 
  190.                 }else
  191.                     setParent(dataRoot.getLeft(),parent); 
  192.                     if(parent.getLeft()==dataRoot){ 
  193.                         parent.setLeft(dataRoot.getLeft()); 
  194.                     }else
  195.                         parent.setRight(dataRoot.getLeft()); 
  196.                     } 
  197.                     //current node is black and tree is not empty 
  198.                     if(dataRoot.isBlack() && !(root.getLeft()==null)){ 
  199.                         RBTreeNode<T> x = dataRoot.getLeft()==null  
  200.                                             ? parent :dataRoot.getLeft(); 
  201.                         boolean isParent = dataRoot.getLeft()==null
  202.                         fixRemove(x,isParent); 
  203.                     } 
  204.                 } 
  205.                 setParent(dataRoot,null); 
  206.                 dataRoot.setLeft(null); 
  207.                 dataRoot.setRight(null); 
  208.                 if(getRoot()!=null){ 
  209.                     getRoot().setRed(false); 
  210.                     getRoot().setParent(null); 
  211.                 } 
  212.                 size.decrementAndGet(); 
  213.                 return dataRoot.getValue(); 
  214.             } 
  215.         } 
  216.         return null
  217.     } 
  218.     /** 
  219.      * fix remove action 
  220.      * @param node 
  221.      * @param isParent 
  222.      */ 
  223.     private void fixRemove(RBTreeNode<T> node,boolean isParent){ 
  224.         RBTreeNode<T> cur = isParent ? null : node; 
  225.         boolean isRed = isParent ? false : node.isRed(); 
  226.         RBTreeNode<T> parent = isParent ? node : node.getParent(); 
  227.  
  228.         while(!isRed && !isRoot(cur)){ 
  229.             RBTreeNode<T> sibling = getSibling(cur,parent); 
  230.             //sibling is not null,due to before remove tree color is balance 
  231.  
  232.             //if cur is a left node 
  233.             boolean isLeft = parent.getRight()==sibling; 
  234.             if(sibling.isRed() && !isLeft){//case 1 
  235.                 //cur in right 
  236.                 parent.makeRed(); 
  237.                 sibling.makeBlack(); 
  238.                 rotateRight(parent); 
  239.             }else if(sibling.isRed() && isLeft){ 
  240.                 //cur in left 
  241.                 parent.makeRed(); 
  242.                 sibling.makeBlack(); 
  243.                 rotateLeft(parent); 
  244.             }else if(isBlack(sibling.getLeft()) && isBlack(sibling.getRight())){//case 2 
  245.                 sibling.makeRed(); 
  246.                 cur = parent; 
  247.                 isRed = cur.isRed(); 
  248.                 parent=parent.getParent(); 
  249.             }else if(isLeft && !isBlack(sibling.getLeft())  
  250.                                     && isBlack(sibling.getRight())){//case 3 
  251.                 sibling.makeRed(); 
  252.                 sibling.getLeft().makeBlack(); 
  253.                 rotateRight(sibling); 
  254.             }else if(!isLeft && !isBlack(sibling.getRight())  
  255.                                             && isBlack(sibling.getLeft()) ){ 
  256.                 sibling.makeRed(); 
  257.                 sibling.getRight().makeBlack(); 
  258.                 rotateLeft(sibling); 
  259.             }else if(isLeft && !isBlack(sibling.getRight())){//case 4 
  260.                 sibling.setRed(parent.isRed()); 
  261.                 parent.makeBlack(); 
  262.                 sibling.getRight().makeBlack(); 
  263.                 rotateLeft(parent); 
  264.                 cur=getRoot(); 
  265.             }else if(!isLeft && !isBlack(sibling.getLeft())){ 
  266.                 sibling.setRed(parent.isRed()); 
  267.                 parent.makeBlack(); 
  268.                 sibling.getLeft().makeBlack(); 
  269.                 rotateRight(parent); 
  270.                 cur=getRoot(); 
  271.             } 
  272.         } 
  273.         if(isRed){ 
  274.             cur.makeBlack(); 
  275.         } 
  276.         if(getRoot()!=null){ 
  277.             getRoot().setRed(false); 
  278.             getRoot().setParent(null); 
  279.         } 
  280.  
  281.     } 
  282.     //get sibling node 
  283.     private RBTreeNode<T> getSibling(RBTreeNode<T> node,RBTreeNode<T> parent){ 
  284.         parent = node==null ? parent : node.getParent(); 
  285.         if(node==null){ 
  286.             return parent.getLeft()==null ? parent.getRight() : parent.getLeft(); 
  287.         } 
  288.         if(node==parent.getLeft()){ 
  289.             return parent.getRight(); 
  290.         }else
  291.             return parent.getLeft(); 
  292.         } 
  293.     } 
  294.  
  295.     private boolean isBlack(RBTreeNode<T> node){ 
  296.         return node==null || node.isBlack(); 
  297.     } 
  298.     private boolean isRoot(RBTreeNode<T> node){ 
  299.         return root.getLeft() == node && node.getParent()==null
  300.     } 
  301.     /** 
  302.      * find the successor node 
  303.      * @param node current node's right node 
  304.      * @return 
  305.      */ 
  306.     private RBTreeNode<T> removeMin(RBTreeNode<T> node){ 
  307.         //find the min node 
  308.         RBTreeNode<T> parent = node; 
  309.         while(node!=null && node.getLeft()!=null){ 
  310.             parent = node; 
  311.             node = node.getLeft(); 
  312.         } 
  313.         //remove min node 
  314.         if(parent==node){ 
  315.             return node; 
  316.         } 
  317.  
  318.         parent.setLeft(node.getRight()); 
  319.         setParent(node.getRight(),parent); 
  320.  
  321.         //don't remove right pointer,it is used for fixed color balance 
  322.         //node.setRight(null); 
  323.         return node; 
  324.     } 
  325.  
  326.     private T addNode(RBTreeNode<T> node){ 
  327.         node.setLeft(null); 
  328.         node.setRight(null); 
  329.         node.setRed(true); 
  330.         setParent(node,null); 
  331.         if(root.getLeft()==null){ 
  332.             root.setLeft(node); 
  333.             //root node is black 
  334.             node.setRed(false); 
  335.             size.incrementAndGet(); 
  336.         }else
  337.             RBTreeNode<T> x = findParentNode(node); 
  338.             int cmp = x.getValue().compareTo(node.getValue()); 
  339.  
  340.             if(this.overrideMode && cmp==0){ 
  341.                 T v = x.getValue(); 
  342.                 x.setValue(node.getValue()); 
  343.                 return v; 
  344.             }else if(cmp==0){ 
  345.                 //value exists,ignore this node 
  346.                 return x.getValue(); 
  347.             } 
  348.  
  349.             setParent(node,x); 
  350.  
  351.             if(cmp>0){ 
  352.                 x.setLeft(node); 
  353.             }else
  354.                 x.setRight(node); 
  355.             } 
  356.  
  357.             fixInsert(node); 
  358.             size.incrementAndGet(); 
  359.         } 
  360.         return null
  361.     } 
  362.  
  363.     /** 
  364.      * find the parent node to hold node x,if parent value equals x.value return parent. 
  365.      * @param x 
  366.      * @return 
  367.      */ 
  368.     private RBTreeNode<T> findParentNode(RBTreeNode<T> x){ 
  369.         RBTreeNode<T> dataRoot = getRoot(); 
  370.         RBTreeNode<T> child = dataRoot; 
  371.  
  372.         while(child!=null){ 
  373.             int cmp = child.getValue().compareTo(x.getValue()); 
  374.             if(cmp==0){ 
  375.                 return child; 
  376.             } 
  377.             if(cmp>0){ 
  378.                 dataRoot = child; 
  379.                 child = child.getLeft(); 
  380.             }else if(cmp<0){ 
  381.                 dataRoot = child; 
  382.                 child = child.getRight(); 
  383.             } 
  384.         } 
  385.         return dataRoot; 
  386.     } 
  387.  
  388.     /** 
  389.      * red black tree insert fix. 
  390.      * @param x 
  391.      */ 
  392.     private void fixInsert(RBTreeNode<T> x){ 
  393.         RBTreeNode<T> parent = x.getParent(); 
  394.  
  395.         while(parent!=null && parent.isRed()){ 
  396.             RBTreeNode<T> uncle = getUncle(x); 
  397.             if(uncle==null){//need to rotate 
  398.                 RBTreeNode<T> ancestor = parent.getParent(); 
  399.                 //ancestor is not null due to before before add,tree color is balance 
  400.                 if(parent == ancestor.getLeft()){ 
  401.                     boolean isRight = x == parent.getRight(); 
  402.                     if(isRight){ 
  403.                         rotateLeft(parent); 
  404.                     } 
  405.                     rotateRight(ancestor); 
  406.  
  407.                     if(isRight){ 
  408.                         x.setRed(false); 
  409.                         parent=null;//end loop 
  410.                     }else
  411.                         parent.setRed(false); 
  412.                     } 
  413.                     ancestor.setRed(true); 
  414.                 }else
  415.                     boolean isLeft = x == parent.getLeft(); 
  416.                     if(isLeft){ 
  417.                         rotateRight(parent); 
  418.                     } 
  419.                     rotateLeft(ancestor); 
  420.  
  421.                     if(isLeft){ 
  422.                         x.setRed(false); 
  423.                         parent=null;//end loop 
  424.                     }else
  425.                         parent.setRed(false); 
  426.                     } 
  427.                     ancestor.setRed(true); 
  428.                 } 
  429.             }else{//uncle is red 
  430.                 parent.setRed(false); 
  431.                 uncle.setRed(false); 
  432.                 parent.getParent().setRed(true); 
  433.                 x=parent.getParent(); 
  434.                 parent = x.getParent(); 
  435.             } 
  436.         } 
  437.         getRoot().makeBlack(); 
  438.         getRoot().setParent(null); 
  439.     } 
  440.     /** 
  441.      * get uncle node 
  442.      * @param node 
  443.      * @return 
  444.      */ 
  445.     private RBTreeNode<T> getUncle(RBTreeNode<T> node){ 
  446.         RBTreeNode<T> parent = node.getParent(); 
  447.         RBTreeNode<T> ancestor = parent.getParent(); 
  448.         if(ancestor==null){ 
  449.             return null
  450.         } 
  451.         if(parent == ancestor.getLeft()){ 
  452.             return ancestor.getRight(); 
  453.         }else
  454.             return ancestor.getLeft(); 
  455.         } 
  456.     } 
  457.  
  458.     private void rotateLeft(RBTreeNode<T> node){ 
  459.         RBTreeNode<T> right = node.getRight(); 
  460.         if(right==null){ 
  461.             throw new java.lang.IllegalStateException("right node is null"); 
  462.         } 
  463.         RBTreeNode<T> parent = node.getParent(); 
  464.         node.setRight(right.getLeft()); 
  465.         setParent(right.getLeft(),node); 
  466.  
  467.         right.setLeft(node); 
  468.         setParent(node,right); 
  469.  
  470.         if(parent==null){//node pointer to root 
  471.             //right  raise to root node 
  472.             root.setLeft(right); 
  473.             setParent(right,null); 
  474.         }else
  475.             if(parent.getLeft()==node){ 
  476.                 parent.setLeft(right); 
  477.             }else
  478.                 parent.setRight(right); 
  479.             } 
  480.             //right.setParent(parent); 
  481.             setParent(right,parent); 
  482.         } 
  483.     } 
  484.  
  485.     private void rotateRight(RBTreeNode<T> node){ 
  486.         RBTreeNode<T> left = node.getLeft(); 
  487.         if(left==null){ 
  488.             throw new java.lang.IllegalStateException("left node is null"); 
  489.         } 
  490.         RBTreeNode<T> parent = node.getParent(); 
  491.         node.setLeft(left.getRight()); 
  492.         setParent(left.getRight(),node); 
  493.  
  494.         left.setRight(node); 
  495.         setParent(node,left); 
  496.  
  497.         if(parent==null){ 
  498.             root.setLeft(left); 
  499.             setParent(left,null); 
  500.         }else
  501.             if(parent.getLeft()==node){ 
  502.                 parent.setLeft(left); 
  503.             }else
  504.                 parent.setRight(left); 
  505.             } 
  506.             setParent(left,parent); 
  507.         } 
  508.     } 
  509.  
  510.     private void setParent(RBTreeNode<T> node,RBTreeNode<T> parent){ 
  511.         if(node!=null){ 
  512.             node.setParent(parent); 
  513.             if(parent==root){ 
  514.                 node.setParent(null); 
  515.             } 
  516.         } 
  517.     } 
  518.     /** 
  519.      * debug method,it used print the given node and its children nodes, 
  520.      * every layer output in one line 
  521.      * @param root 
  522.      */ 
  523.     public void printTree(RBTreeNode<T> root){ 
  524.         java.util.LinkedList<RBTreeNode<T>> queue =new java.util.LinkedList<RBTreeNode<T>>(); 
  525.         java.util.LinkedList<RBTreeNode<T>> queue2 =new java.util.LinkedList<RBTreeNode<T>>(); 
  526.         if(root==null){ 
  527.             return ; 
  528.         } 
  529.         queue.add(root); 
  530.         boolean firstQueue = true
  531.  
  532.         while(!queue.isEmpty() || !queue2.isEmpty()){ 
  533.             java.util.LinkedList<RBTreeNode<T>> q = firstQueue ? queue : queue2; 
  534.             RBTreeNode<T> n = q.poll(); 
  535.  
  536.             if(n!=null){ 
  537.                 String pos = n.getParent()==null ? "" : ( n == n.getParent().getLeft()  
  538.                                                                         ? " LE" : " RI"); 
  539.                 String pstr = n.getParent()==null ? "" : n.getParent().toString(); 
  540.                 String cstr = n.isRed()?"R":"B"
  541.                 cstr = n.getParent()==null ? cstr : cstr+" "
  542.                 System.out.print(n+"("+(cstr)+pstr+(pos)+")"+"\t"); 
  543.                 if(n.getLeft()!=null){ 
  544.                     (firstQueue ? queue2 : queue).add(n.getLeft()); 
  545.                 } 
  546.                 if(n.getRight()!=null){ 
  547.                     (firstQueue ? queue2 : queue).add(n.getRight()); 
  548.                 } 
  549.             }else
  550.                 System.out.println(); 
  551.                 firstQueue = !firstQueue; 
  552.             } 
  553.         } 
  554.     } 
  555.  
  556.     public static void main(String[] args) { 
  557.         RBTree<String> bst = new RBTree<String>(); 
  558.         bst.addNode("d"); 
  559.         bst.addNode("d"); 
  560.         bst.addNode("c"); 
  561.         bst.addNode("c"); 
  562.         bst.addNode("b"); 
  563.         bst.addNode("f"); 
  564.  
  565.         bst.addNode("a"); 
  566.         bst.addNode("e"); 
  567.  
  568.         bst.addNode("g"); 
  569.         bst.addNode("h"); 
  570.  
  571.         bst.remove("c"); 
  572.  
  573.         bst.printTree(bst.getRoot()); 
  574.     } 

代码调试的时候,printTree输出格式如下:


  1. d(B) 
  2. b(B d LE) g(R d RI) 
  3. a(R b LE) e(B g LE) h(B g RI) 
  4. f(R e RI) 

括号左边表示元素的内容。括号内的第一个元素表示颜色,B表示black,R表示red;第二个元素表示父元素的值;第三个元素表示左右,LE表示在父元素的左边。RI表示在父元素的右边。

第一个元素d是root节点,由于它没有父节点,所以括号内只有一个元素。

总结

作为平衡二叉查找树里面众多的实现之一,红黑树无疑是最简洁、实现最为简单的。红黑树通过引入颜色的概念,通过颜色这个约束条件的使用来保持树的高度平衡。作为平衡二叉查找树,旋转是一个必不可少的操作。通过旋转可以降低树的高度,在红黑树里面还可以转换颜色。

红黑树里面的插入和删除的操作比较难理解,这时要注意记住一点:操作之前红黑树是平衡的,颜色是符合定义的。在操作的时候就需要向兄弟节点、父节点、侄子节点借调和互换颜色,要达到这个目的,就需要不断的进行旋转。所以红黑树的插入删除操作需要不停的旋转,一旦借调了别的节点,删除和插入的节点就会达到局部的平衡(局部符合红黑树的定义),但是被借调的节点就不会平衡了,这时就需要以被借调的节点为起点继续进行调整,直到整棵树都是平衡的。在整个修复的过程中,插入具体的分为3种情况,删除分为4种情况。

整个红黑树的查找,插入和删除都是O(logN)的,原因就是整个红黑树的高度是logN,查找从根到叶,走过的路径是树的高度,删除和插入操作是从叶到根的,所以经过的路径都是logN。


作者:振兴

来源:51CTO

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java实现单词计数MapReduce
本文分享实现单词计数MapReduce的方法
0 0
JAVA 实现上传图片添加水印(详细版)(上)
JAVA 实现上传图片添加水印(详细版)
0 0
Java 实现汉字按照首字母分组排序
Java 实现汉字按照首字母分组排序
0 0
Java实现图书管理系统
本篇文章是对目前Java专栏已有内容的一个总结练习,希望各位小主们在学习完面向对象的知识后,可以阅览本篇文章后,自己也动手实现一个这样的demo来加深总结应用已经学到知识并进行巩固。
0 0
java实现spring boot项目启动时,重启Windows进程
java实现spring boot项目启动时,重启Windows进程
0 0
Java实现拼图小游戏(1)—— JFrame的认识及界面搭建
如果要在某一个界面里面添加功能的话,都在一个类中,会显得代码难以阅读,而且修改起来也会很困难,所以我们将游戏主界面、登录界面、以及注册界面都单独编成一个类,每一个类都继承JFrame父类,并且在类中创建方法来来实现页面
0 0
Java网络编程:UDP/TCP实现实时聊天、上传图片、下载资源等
ip地址的分类: 1、ipv4、ipv6 127.0.0.1:4个字节组成,0-255,42亿;30亿都在北美,亚洲就只有4亿 2011年就用尽了。
0 0
Java实现拼图小游戏(7)—— 计步功能及菜单业务的实现
注意由于我们计步功能的步数要在重写方法中用到,所以不能将初始化语句写在方法体内,而是要写在成员位置。在其名字的时候也要做到“见名知意”,所以我们给它起名字为step
0 0
Java实现拼图小游戏(7)—— 作弊码和判断胜利
当我们好不容易把拼图复原了,但是一点提示也没有,完全看不出来是成功了,那么我们就需要有判断胜利的功能去弹出“成功”类的图片,以便于玩家选择是重新开始还是退出小游戏
0 0
Java实现拼图小游戏(7)——查看完整图片(键盘监听实例2)
由于在移动和图片中我们已经添加了键盘监听,也继承了键盘监听的接口,那么我们只需要在重写方法内输入我们的代码即可
0 0
+关注
行者武松
杀人者,打虎武松也。
文章
问答
文章排行榜
最热
最新
相关电子书
更多
JAVA 应用排查全景图
立即下载
Java工程师必读手册
立即下载
Java应用提速(速度与激情)
立即下载