随笔 - 87  文章 - 279  trackbacks - 0
<2006年9月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 194142
  • 排名 - 119

最新评论

阅读排行榜

评论排行榜

基本测试没问题, 有bug请指出:)

#include  < iostream >
using   namespace  std;

const   int  MAXSIZE  =   100 ;
const   int  R  =   0 ;
const   int  B     =   1 ;
const   int  NIL  =   0 ;

class  RBTree
{
public :
    RBTree();
    
int  Root();
    
int  Size();
    
int  Key( int );
    
int  Pointer( int );
    
int  Search( int int );
    
int  Minimum( int );
    
int  Maximum( int );
    
int  successor( int );
    
int  predecessor( int );
    
void  LeftRotate( int );
    
void  RightRotate( int );
    
void  Insert( int );
    
void  InsertByPointer( int );
    
void  InsertFixup( int );
    
void  Delete( int );
    
void  DeleteByPointer( int );
    
void  DeleteFixup( int );
    
void  Travel( int );
private :
    
int  key[MAXSIZE];
    
int  left[MAXSIZE];
    
int  right[MAXSIZE];
    
int  color[MAXSIZE];
    
int  p[MAXSIZE];
    
int  stack[MAXSIZE];
    
int  root;
    
int  top;
    
int  size;
}
;

RBTree::RBTree()
{
    root 
=  NIL;  // 默认空树root为NIL;
    top  =   0 ;
    size 
=   0 ;
    memset(right, NIL, 
sizeof (right));
    memset(left, NIL, 
sizeof (left));
    memset(p, NIL, 
sizeof (p));
    color[NIL] 
=  B;
}


int  RBTree::Root()
{
    
return  root;
}


int  RBTree::Size()
{
    
return  size;
}


int  RBTree::Key( int  x)
{
    
return  key[x];
}


int  RBTree::Pointer( int  k)
{
    
return  Search(Root(), k);
}


int  RBTree::Minimum( int  x)
{
    
while  (left[x]  !=  NIL)
        x 
=  left[x];
    
return  x;
}


int  RBTree::Maximum( int  x)
{
    
while  (right[x]  !=  NIL)
        x 
=  right[x];
    
return  x;
}


int  RBTree::Search( int  x,  int  k)
{
    
while  (x  !=  NIL  &&  k  !=  key[x])
    
{
        
if  (k  <  key[x])
            x 
=  left[x];
        
else
            x 
=  right[x];
    }

    
return  x;
}


int  RBTree::successor( int  x)
{
    
if  (right[x]  !=  NIL)
        
return  Minimum(right[x]);
    
int  y  =  p[x];
    
while  (y  !=  NIL  &&  x  ==  right[y])
    
{
        x 
=  y;
        y 
=  p[y];
    }

    
return  y;
}


int  RBTree::predecessor( int  x)
{
    
if  (left[x]  !=  NIL)
        
return  Maximum(left[x]);
    
int  y  =  p[x];
    
while  (y  !=  NIL  &&  x  ==  left[y])
    
{
        x 
=  y;
        y 
=  p[y];
    }

    
return  y;
}



void  RBTree::LeftRotate( int  x)
{
    
int  y  =  right[x];
    right[x] 
=  left[y];
    p[left[y]] 
=  x;
    p[y] 
=  p[x];
    
if  (p[x]  ==  NIL)
        root 
=  y;
    
else
    
{
        
if  (x  ==  left[p[x]])
            left[p[x]] 
=  y;
        
else
            right[p[x]] 
=  y;
    }

    left[y] 
=  x;
    p[x] 
=  y;
}


void  RBTree::RightRotate( int  x)
{
    
int  y  =  left[x];
    left[x] 
=  right[y];
    p[right[y]] 
=  x;
    p[y] 
=  p[x];
    
if  (p[x]  ==  NIL)
        root 
=  y;
    
else
    
{
        
if  (x  ==  left[p[x]])
            left[p[x]] 
=  y;
        
else
            right[p[x]] 
=  y;
    }

    right[y] 
=  x;
    p[x] 
=  y;
}


void  RBTree::Insert( int  k)
{
    
int  z;
    
if  (top  >   0 )
        z 
=  stack[ -- top];
    
else
        z 
=   ++ size;
    key[z] 
=  k;
    InsertByPointer(z);
}


void  RBTree::Delete( int  k)
{
    
int  z  =  Search(Root(), k);
    
if  (z  !=  NIL)
    
{
        stack[top
++ =  z;
        size
-- ;
        DeleteByPointer(z);
    }

}


void  RBTree::InsertByPointer( int  z)
{
    
int  y  =  NIL;
    
int  x  =  root;
    
while  (x  !=  NIL)
    
{
        y 
=  x;
        
if  (key[z]  <  key[x])
            x 
=  left[x];
        
else
            x 
=  right[x];
    }

    p[z] 
=  y;
    
if  (y  ==  NIL)
        root 
=  z;
    
else
    
{
        
if  (key[z]  <  key[y])
            left[y] 
=  z;
        
else
            right[y] 
=  z;
    }

    left[z] 
=  NIL;
    right[z] 
=  NIL;
    color[z] 
=  R;
    InsertFixup(z);
}


void  RBTree::InsertFixup( int  z)
{
    
int  y;
    
while  (color[p[z]]  ==  R)
    
{
        
if  (p[z]  ==  left[p[p[z]]])
        
{
            y 
=  right[p[p[z]]];
            
if  (color[y]  ==  R)
            
{
                color[p[z]] 
=  B;
                color[y] 
=  B;
                color[p[p[z]]] 
=  R;
                z 
=  p[p[z]];
            }

            
else
            
{
                
if  (z  ==  right[p[z]])
                
{
                    z 
=  p[z];
                    LeftRotate(z);
                }

                color[p[z]] 
=  B;
                color[p[p[z]]] 
=  R;
                RightRotate(p[p[z]]);
            }

        }

        
else
        
{
            y 
=  left[p[p[z]]];
            
if  (color[y]  ==  R)
            
{
                color[p[z]] 
=  B;
                color[y] 
=  B;
                color[p[p[z]]] 
=  R;
                z 
=  p[p[z]];
            }

            
else
            
{
                
if  (z  ==  left[p[z]])
                
{
                    z 
=  p[z];
                    RightRotate(z);
                }

                color[p[z]] 
=  B;
                color[p[p[z]]] 
=  R;
                LeftRotate(p[p[z]]);
            }

        }

    }

    color[root] 
=  B;
}


void  RBTree::DeleteByPointer( int  z)
{
    
int  x, y;
    
if  (left[z]  ==  NIL  ||  right[z]  ==  NIL)
        y 
=  z;
    
else
        y 
=  successor(z);
    
if  (left[y]  !=  NIL)
        x 
=  left[y];
    
else
        x 
=  right[y];
    p[x] 
=  p[y];
    
if  (p[y]  ==  NIL)
        root 
=  x;
    
else
    
{
        
if  (y  ==  left[p[y]])
            left[p[y]] 
=  x;
        
else
            right[p[y]] 
=  x;
    }

    
if  (y  !=  z)
        key[z] 
=  key[y];
    
if  (color[y]  ==  B)
        DeleteFixup(x);
}


void  RBTree::DeleteFixup( int  x)
{
    
int  y, w;
    
while  (x  !=  root  &&  color[x]  ==  B)
    
{
        
if  (x  ==  left[p[x]])
        
{
            w 
=  right[p[x]];
            
if  (color[w]  =  R)
            
{
                color[w] 
=  B;
                color[p[x]] 
=  R;
                LeftRotate(p[x]);
                w 
=  right[p[x]];
            }

            
if  (color[left[w]]  ==  B  &&  color[right[w]]  ==  B)
            
{
                color[w] 
=  R;
                x 
=  p[x];
            }

            
else
            
{
                
if  (color[right[w]]  ==  B)
                
{
                    color[left[w]] 
=  B;
                    color[w] 
=  R;
                    RightRotate(w);
                    w 
=  right[p[x]];
                }

                color[w] 
=  color[p[x]];
                color[p[x]] 
=  B;
                color[right[w]] 
=  B;
                LeftRotate(p[x]);
                x 
=  root;
            }

        }

        
else
        
{
            w 
=  left[p[x]];
            
if  (color[w]  =  R)
            
{
                color[w] 
=  B;
                color[p[x]] 
=  R;
                RightRotate(p[x]);
                w 
=  left[p[x]];
            }

            
if  (color[right[w]]  ==  B  &&  color[left[w]]  ==  B)
            
{
                color[w] 
=  R;
                x 
=  p[x];
            }

            
else
            
{
                
if  (color[left[w]]  ==  B)
                
{
                    color[right[w]] 
=  B;
                    color[w] 
=  R;
                    LeftRotate(w);
                    w 
=  left[p[x]];
                }

                color[w] 
=  color[p[x]];
                color[p[x]] 
=  B;
                color[left[w]] 
=  B;
                RightRotate(p[x]);
                x 
=  root;
            }

        }

    }

    color[x] 
=  B;
}

void  RBTree::Travel( int  x)
{
    
if  (x  !=  NIL)
    
{
        cout 
<<   ' ( ' ;
        Travel(left[x]);
        cout 
<<   '   '   <<  key[x]  <<   '   ' ;
        Travel(right[x]);
        cout 
<<   ' ) ' ;
    }

}


int  main()
{
    RBTree T;

    
for  ( int  i = 1 ; i <= 10 ; i ++ )
        T.Insert(i
* 10 );
    
for  ( int  i = 1 ; i <= 10 ; i ++ )
    
{
        T.Delete(i
* 10 );
        T.Travel(T.Root());
        cout 
<<  endl;
    }

    
return   0 ;
}
posted on 2006-09-15 01:15 阅读(1046) 评论(4)  编辑 收藏 引用 所属分类: 算法&ACM

FeedBack:
# re: 终于把RBTree敲出来了, 累. 2006-09-15 10:25 small-fat
.......呵呵,顶一下,牛牛..  回复  更多评论
  
# re: 终于把RBTree敲出来了, 累. 2006-09-15 12:48 chenger
用数组?感觉一般只有在做算法题时才这么干  回复  更多评论
  
# re: 终于把RBTree敲出来了, 累. 2006-09-15 12:57 
因为用数组可以换速度。。  回复  更多评论
  
# re: 终于把RBTree敲出来了, 累. 2006-09-15 14:29 Optimistic
偶看了都觉得累呀。。。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理