waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks
          轉自:http://www.aygfsteel.com/javacap/archive/2007/12/20/169120.html
          紅黑樹可能是要考慮情況最多的BST樹了,它有自己的規則(見代碼的注釋),通過這些規則可以保證花費較小的代價來達到相對平衡。
          注意,紅黑樹仍然不是平衡樹,但是統計性能要好于AVL樹。
          要保持紅黑樹的規則,主要通過兩類操作,一類是換色,一類還是旋轉。
          紅黑樹插入主要要解決紅-紅沖突,而刪除主要則解決“雙黑”

          同樣,紅黑樹的刪除節點實現是最復雜的,不過,復雜也就在于考慮的情況多,掌握了這幾種情況實現還是不困難。
          其實,紅黑樹其實是一顆擴充的二叉樹,所以也是滿二叉樹,其空節點可以看做是擴充的葉節點。但是紅黑樹的擴充葉節點是有特殊意義的。


          下面是代碼:

          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> g=p.parent;
                  RBNode
          <E> cur=(RBNode<E>)p.left;
                  
                  p.left
          =cur.right;
                  
          if(cur.right!=null)((RBNode<E>)cur.right).parent=p;
                  
                  cur.right
          =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> _insert(RBNode<E> cur,E ele)
              {
                  
                  RBNode
          <E> parent=null;
                  
          int cmp;
                  
          boolean left=false;
                  
          while(!cur.isNull()&&(cmp=ele.compareTo(cur.key))!=0)
                  {
                      parent
          =cur;
                      
          if(cmp<0)
                      {
                          cur
          =(RBNode<E>)cur.left;
                          left
          =true;
                          
                      }
                      
          else {cur=(RBNode<E>)cur.right;left=false;}
                      
                  }
                  
          if(!cur.isNull())throw new IllegalArgumentException("can't insert duplicate key!");
                  cur
          =newNormalNode(parent,ele,RBNode.RED);
                  
          if(left)parent.left=cur;
                  
          else parent.right=cur;
                  
          return cur;
              }

              
          /**
               * 
               
          */
              
          public RBTree() {
                      root
          =null;
              }

          }
          posted on 2009-04-15 22:16 weesun一米陽光 閱讀(361) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 广西| 阜康市| 资溪县| 巴楚县| 玉屏| 宿州市| 灵川县| 同心县| 鸡西市| 莱阳市| 资兴市| 邹城市| 铜陵市| 星子县| 石狮市| 抚松县| 共和县| 高州市| 罗山县| 星子县| 鸡泽县| 民丰县| 六枝特区| 桃江县| 温宿县| 延津县| 兴海县| 巴林左旗| 咸丰县| 勐海县| 浏阳市| 广南县| 怀仁县| 天台县| 新乡县| 永靖县| 偏关县| 综艺| 敦化市| 临猗县| 沁水县|