# 红黑树的Java实现

xiaoxiao2023-11-21  21

package  algorithms.tree; /**  * R-B Tree has following four rules:  * 1)every node is either red or black  * 2)root and empty node (external leaf node) are always black.  * 3)the red node's parent node must be black  * 4)every simple path start from node X to its descendant contains same number of black node  *   *   *  @author  yovn  *   */ public   class  RBTree < extends  Comparable < E >>   extends  DefaultBSTree < E >   implements  BSTree < E >  {                public   static   class  RBPrinter < extends  Comparable < E >>   implements  DefaultBSTree.NodeVisitor < E >     {         @Override          public   void  visit(E ele) {                                   }         @Override          public   void  visitNode(algorithms.tree.DefaultBSTree.BSTNode < E >  node) {             RBNode < E >  n = (RBNode < E > )node;              if ( ! n.isNull())             System.out.print(n.key + " ( " + (n.color == RBNode.RED ? " RED " : " BLACK " ) + " ), " );                      }              }      static   class  RBNode < extends  Comparable < E >>   extends  BSTNode < E >     {          static   final   boolean  RED = false ;          static   final   boolean  BLACK = true ;                                    RBNode < E >  parent;          boolean  color; // red or black                           RBNode(RBNode < E >  p,E key, boolean  color) {              super (key);              this .color = color;              this .parent = p;                      }                                     final   boolean  isNull(){ return  key == null ;}              }                        @Override      public   final   boolean  delete(E ele) {         RBNode < E >  cur;                   int  cmp;          if (root == null ) return   false ;         cur = (RBNode < E > )root;          while ( ! cur.isNull() && (cmp = ele.compareTo(cur.key)) != 0 )         {              if (cmp < 0 )cur = (RBNode < E > )cur.left;              else  cur = (RBNode < E > )cur.right;                          }          if (cur.isNull())         {              // can't find specified key              return   false ;         }          if ( ! ((RBNode < E > )cur.left).isNull() &&! ((RBNode < E > )cur.right).isNull())         {             RBNode < E >  prev = (RBNode < E > )cur.left;                       while ( ! ((RBNode < E > )prev.right).isNull())             {                                  prev = (RBNode < E > )prev.right;             }             cur.key = prev.key;             cur = prev;                  }          if ( ! ((RBNode < E > )cur.left).isNull())         {              if  (cur  ==  root) {                 root  =  cur.left;                 ((RBNode < E > )root).color = RBNode.BLACK;                  return   true ;             }                           if (cur.parent.left == cur)             {                 cur.parent.left = cur.left;                 ((RBNode < E > )cur.left).parent = cur.parent;             }              else             {                 cur.parent.right = cur.left;                 ((RBNode < E > )cur.left).parent = cur.parent;             }              if (cur.color == RBNode.BLACK)             {                 ((RBNode < E > )cur.left).color = RBNode.BLACK;             }         }          else   if ( ! ((RBNode < E > )cur.right).isNull())         {              if  (cur  ==  root) {                 root  =  cur.right;                 ((RBNode < E > )root).color = RBNode.BLACK;                  return   true ;             }                           if (cur.parent.left == cur)             {                 cur.parent.left = cur.right;                 ((RBNode < E > )cur.right).parent = cur.parent;             }              else             {                 cur.parent.right = cur.right;                 ((RBNode < E > )cur.right).parent = cur.parent;             }              if (cur.color == RBNode.BLACK)             {                 ((RBNode < E > )cur.right).color = RBNode.BLACK;             }         }          else         {              if (cur == root)             {                 root = null ;                  return   true ;             }             RBNode < E >  todo;              if (cur.parent.left == cur)             {                 todo = newNullNode(cur.parent);                 cur.parent.left = todo;             }                           else             {                 todo = newNullNode(cur.parent);                 cur.parent.right = todo;             }              if (cur.color == RBNode.BLACK)             {                  // now todo is a double black node, we will eliminate the double black                 fixup_double_black(todo);             }                      }                   return   true ;     }     @Override      public  E findMax() {          if (isEmpty()) return   null ;         BSTNode < E >  node = root;          while ( ! ((RBNode < E > )node.right).isNull())         {             node = node.right;         }          return  node.key;     }     @Override      public  E findMin() {          if (isEmpty()) return   null ;         BSTNode < E >  node = root;          while ( ! ((RBNode < E > )node.left).isNull())         {             node = node.left;         }          return  node.key;     }      private   final  RBNode < E >  newNullNode(RBNode < E >  p)     {          return   new  RBNode < E > (p, null ,RBNode.BLACK);     }           private   final  RBNode < E >  newNormalNode(RBNode < E >  p,E key,  boolean  color)     {         RBNode < E >  node =   new  RBNode < E > (p,key,color);         node.left = newNullNode(node);         node.right = newNullNode(node);          return  node;     }      private   final   void  fixup_double_black(RBNode < E >  cur) {                  RBNode < E >  sibling;         RBNode < E >  p;               while (cur != root) // until its parent,parent maybe double black          {             p = cur.parent;              if (p.left == cur)             {                 sibling = (RBNode < E > )p.right;                  if (sibling.color == RBNode.RED)                 {                     rotate_from_right(p);                     p.color = RBNode.RED;                     sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation                      // this case  transformed to another case handled in other place                 }                  else                   {                      if (((RBNode < E > )sibling.right).color == RBNode.RED)                     {                         rotate_from_right(p);                         sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.                         p.color = RBNode.BLACK;                         ((RBNode < E > )sibling.right).color = RBNode.BLACK;                          // ok done!                          return ;                                              }                      else   if (((RBNode < E > )sibling.left).color == RBNode.RED)                     {                         rotate_from_left(sibling);                         sibling.color = RBNode.RED;                         sibling.parent.color = RBNode.BLACK; // its parent was previously be its left child, remember we have done a left rotation from sibling                                                   //  now transformed to previous case, double black 's sibling(black) have right child colored red                                              }                      else   //   sibling's two children are both black                     {                          // re-coloring the sibling and parent                         sibling.color = RBNode.RED;                          if (p.color == RBNode.BLACK)                         {                             cur = p;                              // now the cur node was not double black node ,but p was a double black                         }                          else                         {                             p.color = RBNode.BLACK; // eliminated the double black node                               return ;                         }                     }                 }             }              else             {                 sibling = (RBNode < E > )p.left;                  if (sibling.color == RBNode.RED)                 {                     rotate_from_left(p);                     p.color = RBNode.RED;                     sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation                      // this case  transformed to another case handled in other place                 }                  else                   {                      if (((RBNode < E > )sibling.left).color == RBNode.RED)                     {                         rotate_from_left(p);                         sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.                         p.color = RBNode.BLACK;                         ((RBNode < E > )sibling.left).color = RBNode.BLACK;                          // ok done!                          return ;                                              }                      else   if (((RBNode < E > )sibling.right).color == RBNode.RED)                     {                         rotate_from_right(sibling);                         sibling.color = RBNode.RED;                         sibling.parent.color = RBNode.BLACK; // its parent was previously be its right child, remember we have done a left rotation from sibling                                               //  now transformed to previous case, double black 's sibling(black) have right child colored red                                              }                      else   //   sibling's two children are both black                     {                          // re-coloring the sibling and parent                         sibling.color = RBNode.RED;                          if (p.color == RBNode.BLACK)                         {                             cur = p;                              // now the cur node was not double black node ,but p was a double black                         }                          else                         {                             p.color = RBNode.BLACK; // eliminated the double black node                               return ;                         }                     }                 }             }         }              }          @Override      public   final   void  insert(E ele) {          if (root == null )         {             root = newNormalNode( null ,ele,RBNode.BLACK); // now root's black-height(bh) is 1              return ;         }         RBNode < E >  ret = _insert((RBNode < E > )root,ele); // first insert it         _insert_fixup(ret); // fix-up the R-B tree from node cur;     }                private   final   void  _insert_fixup(RBNode < E >  cur) {                  RBNode < E >  p,g;               // we should fix until it is black colored          while (cur != root && cur.color == RBNode.RED)         {             p = cur.parent;              if (p.color == RBNode.BLACK)             {                  // that's fine, the insertion will not change any black height, and will not violate any rule.                  return ;             }             g = p.parent; // we can assume the p is not null now.                           if (p == g.left)             {                 RBNode < E >  uncle = (RBNode < E >  )g.right;                  if (uncle.color == RBNode.RED)                 {                      // re-coloring                     g.color = RBNode.RED;                     uncle.color = p.color = RBNode.BLACK;                                           // now the g maybe conflict with its parent;                     cur = g;                 }                  else                 {                      if (cur == p.right)                     {                          // this case we should do left rotation, and then it will transform to next case                         cur = rotate_from_right(p);                         cur = (RBNode < E > )cur.left;                          // transformed to next case                         }                                          cur = rotate_from_left(g);                     cur.color = RBNode.BLACK;                     ((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;                                                                       }                              }              else             {                 RBNode < E >  uncle = (RBNode < E >  )g.left;                  if (uncle.color == RBNode.RED)                 {                      // re-coloring                     g.color = RBNode.RED;                     uncle.color = p.color = RBNode.BLACK;                                           // now the g maybe conflict with its parent;                     cur = g;                 }                  else                 {                      if (cur == p.left)                     {                          // this case we should do right rotation, and then it will transform to next case                         cur = rotate_from_left(p);                         cur = (RBNode < E > )cur.right;                          // transformed to next case                         }                                          cur = rotate_from_right(g);                     cur.color = RBNode.BLACK;                     ((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;                                                                       }             }                          }         ((RBNode < E > )root).color = RBNode.BLACK;                       }      private   final  RBNode < E >  rotate_from_right(RBNode < E >  p) {                  RBNode < E >  g = p.parent;         RBNode < E >  cur = (RBNode < E > )p.right;                  p.right = cur.left;          if (cur.left != null )((RBNode < E > )cur.left).parent = p;                  cur.left = p;         p.parent = cur;                            if (g != null )         {              if (g.left == p)g.left = cur;              else  g.right = cur;         }          else  root = cur;                  cur.parent = g;          return  cur;                   }      private   final  RBNode < E >  rotate_from_left(RBNode < E >  p) {         RBNode < E > 相关资源：红黑树的Java实现参考源码