随笔 - 87  文章 - 279  trackbacks - 0
<2024年12月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214815
  • 排名 - 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> *y = x->right;
    x->right = y->left;
    y->left->p = x;
    y->p = x->p;
    if (x->p == NIL) root = y;
    else {
        if (x == x->p->left) x->p->left = y;
        else x->p->right = y;
    }
    y->left = x;
    x->p = y;
}


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

template <class KT, class RT>
void RBTree<KT, RT>::insert(RBTreeNode<KT, RT> *z) {
    RBTreeNode<KT, RT> *y = NIL, *x = 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->p = 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->p == 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->p = y->p;
    if (y->p == 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> *x = 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<int, int> *h[100], *tmp;
    RBTree<int, int> *t;
    t = new RBTree<int, int>;
    for (i=0; i<10; i++) {
        h[i] = new RBTreeNode<int, int>(10+i/2, 10000+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/2, 10000+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 豪 阅读(1822) 评论(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   博问   Chat2DB   管理


Copyright ©2024 豪 Powered by: 博客园 模板提供：沪江博客