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

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214423
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

RBTree.h

 

#ifndef RBTREE_H
#define RBTREE_H

const int RED = 0;
const int BLACK = 1;

template 
<class KT, class RT>
class RBTreeNode {
public:
    
//RBTree关键字
    KT key;
    
//RBTree记录
    RT rec;
    
//RBTree左儿子指针
    RBTreeNode<KT, RT> *left;
    
//RBTree右儿子指针
    RBTreeNode<KT, RT> *right;
    
//RBTree父节点指针
    RBTreeNode<KT, RT> *p;
    
//RBTree下一节点指针,该节点和下一节点有相同key值
    RBTreeNode<KT, RT> *nxt;
    
//RBTree上一节点指针,该节点和上一节点有相同key值
    RBTreeNode<KT, RT> *pre;
    
//节点颜色
    int color;
    
//节点构造函数
    RBTreeNode(KT ckey, RT crec, int col) {color=col; key=ckey; rec=crec; left=NULL; right=NULL; p=NULL; nxt=NULL; pre=NULL;};
    RBTreeNode(
int col) {color = col; left=NULL; right=NULL; p=NULL; nxt=NULL; pre=NULL;};
}
;


template 
<class KT, class RT>
class RBTree {
public:
    
//RBTree哨兵指针
    RBTreeNode<KT, RT> *NIL;
    
//RBTree树根指针
    RBTreeNode<KT, RT> *root;
    
//RBTree构造函数
    RBTree();
    
//RBTree析构函数
    ~RBTree();
    
//RBTree中序遍历函数
    void travel(RBTreeNode<KT, RT> *v,int);
    
//RBTree左旋操作
    void leftRotate(RBTreeNode<KT, RT> *z);
    
//RBTree右旋操作
    void rightRotate(RBTreeNode<KT, RT> *z);
    
//RBTree插入函数
    void insert(RBTreeNode<KT, RT> *z);
    
//RBTree插入调整函数
    void insertFixUp(RBTreeNode<KT, RT> *z);
    
//RBTree查找x节点后继节点函数
    RBTreeNode<KT, RT>* successor(RBTreeNode<KT, RT> *x);
    
//RBTree查找以x为根的子树中的最小值节点函数
    RBTreeNode<KT, RT>* getMin(RBTreeNode<KT, RT> *x);
    
//RBTree删除节点函数
    void del(RBTreeNode<KT, RT> *z);
    
//RBTree删除链表头节点函数
    void delFirst(RBTreeNode<KT, RT> *z);
    
//RBTree删除链表头节点调整函数
    void delFirstFixUp(RBTreeNode<KT, RT> *z);
    
//RBTree删除链表内部节点调整函数
    void delInter(RBTreeNode<KT, RT> *z);
    
//RBTree查找节点(包括链表内部节点);
    RBTreeNode<KT, RT> * find(KT fkey, RT frec);
}
;


template 
<class KT, class RT>
RBTree
<KT, RT>::RBTree() {
    NIL 
= new RBTreeNode<KT, RT>(BLACK);
    root 
= NIL;
}



template 
<class KT, class RT>
RBTree
<KT, RT>::~RBTree() {
    delete NIL;
}



template 
<class KT, class RT>
void RBTree<KT, RT>::travel(RBTreeNode<KT, RT> *v, int tc) {
    RBTreeNode
<KT, RT> *p;
    
if (v == NIL) return ;
    
if (tc>ans) ans=tc;
    printf(
"");
    travel(v
->left,tc+1);
    printf(
" %d ", v->key);
    p 
= v->nxt;
    
while (p) {
        printf(
", %d ", p->key);
        p 
= p->nxt;
    }

    travel(v
->right,tc+1);
    printf(
" )");
}



template 
<class KT, class RT>
void RBTree<KT, RT>::leftRotate(RBTreeNode<KT, RT> *x) {
    RBTreeNode
<KT, RT> *= x->right;
    x
->right = y->left;
    y
->left->= x;
    y
->= x->p;
    
if (x->== NIL) root = y;
    
else {
        
if (x == x->p->left) x->p->left = y;
        
else x->p->right = y;
    }

    y
->left = x;
    x
->= y;
}



template 
<class KT, class RT>
void RBTree<KT, RT>::rightRotate(RBTreeNode<KT, RT> *x) {
    RBTreeNode
<KT, RT> *= x->left;
    x
->left = y->right;
    y
->right->= x;
    y
->= x->p;
    
if (x->== NIL) root = y;
    
else {
        
if (x == x->p->left) x->p->left = y;
        
else x->p->right = y;
    }

    y
->right = x;
    x
->= y;
}


template 
<class KT, class RT>
void RBTree<KT, RT>::insert(RBTreeNode<KT, RT> *z) {
    RBTreeNode
<KT, RT> *= NIL, *= root;
    
while (x != NIL) {
        y 
= x;
        
if (z->key < x->key) x = x->left;
        
else if (z->key > x->key) x = x->right;
        
else {
            
//加入该节点的链表
            z->nxt = x->nxt;
            x
->nxt = z;
            z
->pre = x;
            
if (z->nxt) z->nxt->pre = z;
            
return ;
        }

    }

    z
->= y;
    
if (y == NIL) {
        root 
= z;
    }
 else {
        
if (z->key < y->key) y->left = z;
        
else y->right = z;
    }

    z
->left = NIL;
    z
->right = NIL;
    z
->color = RED;
    insertFixUp(z);
}



template 
<class KT, class RT>
void RBTree<KT, RT>::insertFixUp(RBTreeNode<KT, RT> *z) {
    RBTreeNode
<KT, RT> *y;
    
while (z->p->color == RED) {
        
if (z->== z->p->p->left) {
            y 
= z->p->p->right;
            
if (y->color == RED) {
                z
->p->color = BLACK;
                y
->color = BLACK;
                z
->p->p->color = RED;
                z 
= z->p->p;
            }
 else {
                
if (z == z->p->right) {
                    z 
= z->p;
                    leftRotate(z);
                }

                z
->p->color = BLACK;
                z
->p->p->color = RED;
                rightRotate(z
->p->p);
            }

        }
 else {
            y 
= z->p->p->left;
            
if (y->color == RED) {
                z
->p->color = BLACK;
                y
->color = BLACK;
                z
->p->p->color = RED;
                z 
= z->p->p;
            }
 else {
                
if (z == z->p->left) {
                    z 
= z->p;
                    rightRotate(z);
                }

                z
->p->color = BLACK;
                z
->p->p->color = RED;
                leftRotate(z
->p->p);
            }

        }

    }

    root
->color = BLACK;
}



template 
<class KT, class RT>
RBTreeNode
<KT, RT>* RBTree<KT, RT>::getMin(RBTreeNode<KT, RT> *x) {
    
while (x->left != NIL) x = x->left;
    
return x;
}



template 
<class KT, class RT>
RBTreeNode
<KT, RT>* RBTree<KT, RT>::successor(RBTreeNode<KT, RT> *x) {
    RBTreeNode
<KT, RT> *y;
    
if (x->right != NIL) return getMin(x->right);
    y 
= x->p;
    
while (y != NIL && x == y->right) {
        x 
= y;
        y 
= y->p;
    }

    
return y;
}



template 
<class KT, class RT>
void RBTree<KT, RT>::delFirst(RBTreeNode<KT, RT> *z) {
    RBTreeNode
<KT, RT> *x, *y; 
    
if (z->left == NIL || z->right == NIL) y = z;
    
else y = successor(z);
    
if (y->left != NIL) x = y->left;
    
else x = y->right;
    x
->= y->p;
    
if (y->== NIL) root = x;
    
else {
        
if (y == y->p->left) y->p->left = x;
        
else y->p->right = x;
    }

    
if (y != z) z->key = y->key;
    
if (y->color == BLACK) delFirstFixUp(x);
    delete y;
}



template 
<class KT, class RT>
void RBTree<KT, RT>::delFirstFixUp(RBTreeNode<KT, RT> *x) {
    RBTreeNode
<KT, RT> *w; 
    
while (x != root && x->color == BLACK) {
        
if (x == x->p->left) {
            w 
= x->p->right;
            
if (w->color == RED) {
                w
->color = BLACK;
                x
->p->color = RED;
                leftRotate(x
->p);
                w 
= x->p->right;
            }

            
if (w->left->color == BLACK && w->right->color == BLACK) {
                w
->color = RED;
                x 
= x->p;
            }
 else {
                
if (w->right->color == BLACK) {
                    w
->left->color = BLACK;
                    w
->color = RED;
                    rightRotate(w);
                    w 
= x->p->right;
                }

                w
->color = x->p->color;
                x
->p->color = BLACK;
                w
->right->color = BLACK;
                leftRotate(x
->p);
                x 
= root;                    
            }

        }
 else {
            w 
= x->p->left;
            
if (w->color == RED) {
                w
->color = BLACK;
                x
->p->color = RED;
                rightRotate(x
->p);
                w 
= x->p->left;
            }

            
if (w->left->color == BLACK && w->right->color == BLACK) {
                w
->color = RED;
                x 
= x->p;
            }
 else {
                
if (w->left->color == BLACK) {
                    w
->right->color = BLACK;
                    w
->color = RED;
                    leftRotate(w);
                    w 
= x->p->left;
                }

                w
->color = x->p->color;
                x
->p->color = BLACK;
                w
->left->color = BLACK;
                rightRotate(x
->p);
                x 
= root;                    
            }

        }

    }

    x
->color = BLACK;
}



template 
<class KT, class RT>
RBTreeNode
<KT, RT>* RBTree<KT, RT>::find(KT fkey, RT frec) {
    RBTreeNode
<KT, RT> *= root;
    
while (x) {
        
if (fkey < x->key) x = x->left;
        
else if (fkey > x->key) x = x->right;
        
else {
            
while (x && x->rec != frec) x = x->nxt;
            
return x;
        }

    }

    
return x;
}


template 
<class KT, class RT>
void RBTree<KT, RT>::delInter(RBTreeNode<KT, RT> *z) {
    RBTreeNode
<KT, RT> *pz = z->pre;
    pz
->nxt = z->nxt;
    
if (z->nxt) z->nxt->pre = pz;
    delete z;
}



template 
<class KT, class RT>
void RBTree<KT, RT>::del(RBTreeNode<KT, RT> *z) {
    RBTreeNode
<KT, RT> *p;
    
if (z->pre) {
        
//删除一个内部节点
        delInter(z);
    }
 else {
        
//删除头节点
        if (z->nxt) {
            
//删除该节点后链表不为空
            p = z->nxt;
            z
->key = p->key;
            z
->rec = p->rec;
            delInter(p);
        }
 else {
            
//删除RBTree上的该节点
            delFirst(z);
        }

    }

}


#endif


test.cpp
#include <iostream>
#include 
"RBTree.h"
using namespace std;
int ans=0;
int main() {
    
int i;
    RBTreeNode
<intint> *h[100], *tmp;
    RBTree
<intint> *t;
    t 
= new RBTree<intint>;
    
for (i=0; i<10; i++{
        h[i] 
= new RBTreeNode<intint>(10+i/210000+i, RED);
        t
->insert(h[i]);
        ans
=0;
        t
->travel(t->root,0);
        printf(
"\n");
        printf(
"hight=%d\n", ans);
    }


    
for (i=0; i<10; i++{
        tmp 
= t->find(10+i/210000+i);
        
if (tmp) t->del(tmp);
        ans
=0;
        t
->travel(t->root,0);
        printf(
"\n");
        printf(
"hight=%d\n", ans);
    }

    system(
"pause");
    
return 0;
}

posted on 2007-09-23 21:32 阅读(1819) 评论(2)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: 红黑树(数据结构大作业扩展版) 2011-05-12 10:10 
楼主的代码很工整,与算法导论的一样,不过
//RBTree左旋操作
void leftRotate(RBTreeNode<KT, RT> *z);
//RBTree右旋操作
void rightRotate(RBTreeNode<KT, RT> *z);
操作写少了一句判断
左旋为
if(y->left != NIL)
y->left->p = x;
右旋为
if(y->right != NIL)
y->right->p = x;
借来用了,谢谢啊!  回复  更多评论
  
# re: 红黑树(数据结构大作业扩展版) 2011-05-12 10:15 
再贴送两个函数,这样可以做很多事情了,哈!代码的意思和set集里的函数一样
template <class KT, class RT>
RBTreeNode<KT, RT>* RBTree<KT, RT>::lower_bound(KT fkey, RT frec) {
RBTreeNode<KT, RT> *x = root;
RBTreeNode<KT, RT> *y = x;
bool f=0;

while (x != NIL) {
if (fkey > x->key) {x = x->right;}
else if (fkey < x->key) { y = x; x = x->left; f=1;}
else {
y = x;
while (x != NULL && x->rec != frec) {y = x; x = x->nxt;}
return y;
}
}
if(f) return y;
else return NIL;
}

template <class KT, class RT>
RBTreeNode<KT, RT>* RBTree<KT, RT>::upper_bound(KT fkey, RT frec) {
RBTreeNode<KT, RT> *x = root;
RBTreeNode<KT, RT> *y = x;
bool f=0;

while (x != NIL) {
if (fkey < x->key) { x = x->left; }
else if (fkey > x->key) { y = x; x = x->right; f=1;}
else {
while (x != NULL && x->rec != frec) {y = x; x = x->nxt;}
return y;
}
}
if(f) return y;
else return NIL;
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理