• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        




            
	
		


            隨筆 - 87 
文章 - 279 
trackbacks - 0


             
	

            

            
	
		
            
			
            
	
            
		
            <2025年5月>
            
	
            日一二三四五六
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567
            

            

            
			


            
	潛心看書研究！

            

			

            常用鏈接
            


            留言簿(19)
            




		
            隨筆分類(81)
            
		
				
			
	
		
            文章分類(89)
            
		
				
			
	
		
            相冊
            
		
				
			
	
		
            ACM OJ
            
		
				
			
	
		
            My friends
            
		
				
			
	




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            積分與排名
            

              
	
            • 
		積分 -
		216680
	
            • 
		排名 -
		117
	
              • 

            


            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


            		
	

            

            
	
					


            
	
	
            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 豪 閱讀(1832) 評論(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;

            }  回復  更多評論
              
			
            
		
            
	




            






            

				
	



            


    
    







	   
	



亚洲国产精品久久久天堂|
久久亚洲精品国产精品|
久久精品欧美日韩精品|
国产一区二区久久久|
久久精品国产黑森林|
精品久久一区二区|
99久久99这里只有免费费精品|
中文字幕亚洲综合久久菠萝蜜|
久久精品国产99国产精品|
久久久久国色AV免费观看|
久久久久国产精品三级网|
久久久久人妻精品一区三寸蜜桃|
99久久国产综合精品成人影院|
久久精品成人免费网站|
亚洲国产成人久久综合一
|
精品久久久一二三区|
亚洲精品99久久久久中文字幕|
久久成人18免费网站|
欧美一级久久久久久久大|
亚洲国产日韩欧美综合久久|
亚洲婷婷国产精品电影人久久|
一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区|
狠狠人妻久久久久久综合蜜桃|
国产精品一区二区久久精品无码|
99久久精品免费看国产免费|
久久久久久久国产免费看|
亚洲欧美一级久久精品|
中文字幕乱码人妻无码久久|
亚洲av日韩精品久久久久久a|
久久人人爽人人爽人人片AV不|
丁香狠狠色婷婷久久综合|
岛国搬运www久久|
亚洲第一永久AV网站久久精品男人的天堂AV|
久久影院久久香蕉国产线看观看|
色老头网站久久网|
97久久香蕉国产线看观看|
久久亚洲国产精品123区|
久久久www免费人成精品|
国产成人精品久久一区二区三区|
久久本道久久综合伊人|
日韩精品久久无码人妻中文字幕|