• <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


             
	

            

            
	
		
            
			
            
	
            
		
            <2011年4月>
            
	
            日一二三四五六
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567
            

            

            
			


            
	潛心看書研究！

            

			

            常用鏈接
            


            留言簿(19)
            




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




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            積分與排名
            

              
	
            • 
		積分 -
		217765
	
            • 
		排名 -
		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關(guān)鍵字
                KT key;
                            //RBTree記錄
                RT rec;
                            //RBTree左兒子指針
                RBTreeNode<KT, RT> *left;
                            //RBTree右兒子指針
                RBTreeNode<KT, RT> *right;
                            //RBTree父節(jié)點(diǎn)指針
                RBTreeNode<KT, RT> *p;
                            //RBTree下一節(jié)點(diǎn)指針，該節(jié)點(diǎn)和下一節(jié)點(diǎn)有相同key值
                RBTreeNode<KT, RT> *nxt;
                            //RBTree上一節(jié)點(diǎn)指針，該節(jié)點(diǎn)和上一節(jié)點(diǎn)有相同key值
                RBTreeNode<KT, RT> *pre;
                            //節(jié)點(diǎn)顏色
                int color;
                            //節(jié)點(diǎn)構(gòu)造函數(shù)
                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構(gòu)造函數(shù)
                RBTree();
                            //RBTree析構(gòu)函數(shù)
                ~RBTree();
                            //RBTree中序遍歷函數(shù)
                void travel(RBTreeNode<KT, RT> *v,int);
                            //RBTree左旋操作
                void leftRotate(RBTreeNode<KT, RT> *z);
                            //RBTree右旋操作
                void rightRotate(RBTreeNode<KT, RT> *z);
                            //RBTree插入函數(shù)
                void insert(RBTreeNode<KT, RT> *z);
                            //RBTree插入調(diào)整函數(shù)
                void insertFixUp(RBTreeNode<KT, RT> *z);
                            //RBTree查找x節(jié)點(diǎn)后繼節(jié)點(diǎn)函數(shù)
                RBTreeNode<KT, RT>* successor(RBTreeNode<KT, RT> *x);
                            //RBTree查找以x為根的子樹中的最小值節(jié)點(diǎn)函數(shù)
                RBTreeNode<KT, RT>* getMin(RBTreeNode<KT, RT> *x);
                            //RBTree刪除節(jié)點(diǎn)函數(shù)
                void del(RBTreeNode<KT, RT> *z);
                            //RBTree刪除鏈表頭節(jié)點(diǎn)函數(shù)
                void delFirst(RBTreeNode<KT, RT> *z);
                            //RBTree刪除鏈表頭節(jié)點(diǎn)調(diào)整函數(shù)
                void delFirstFixUp(RBTreeNode<KT, RT> *z);
                            //RBTree刪除鏈表內(nèi)部節(jié)點(diǎn)調(diào)整函數(shù)
                void delInter(RBTreeNode<KT, RT> *z);
                            //RBTree查找節(jié)點(diǎn)(包括鏈表內(nèi)部節(jié)點(diǎn));
                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 {
                                    //加入該節(jié)點(diǎn)的鏈表
                        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) {
                                //刪除一個(gè)內(nèi)部節(jié)點(diǎn)
                    delInter(z);
                }             else {
                                //刪除頭節(jié)點(diǎn)
                    if (z->nxt) {
                                    //刪除該節(jié)點(diǎn)后鏈表不為空
                        p = z->nxt;
                        z            ->key = p->key;
                        z            ->rec = p->rec;
                        delInter(p);
                    }             else {
                                    //刪除RBTree上的該節(jié)點(diǎn)
                        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 豪 閱讀(1836) 評論(2)  編輯 收藏 引用  所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法 
            

            







            
	    
    


            
FeedBack:

            
	

		
            
			
            
			
            # re: 紅黑樹（數(shù)據(jù)結(jié)構(gòu)大作業(yè)擴(kuò)展版） 2011-05-12 10:10 云
            
				
            樓主的代碼很工整，與算法導(dǎo)論的一樣，不過

            //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;

            借來用了，謝謝啊！  回復(fù)  更多評論
              
			
            
		
            
	
		
            
			
            
			
            # re: 紅黑樹（數(shù)據(jù)結(jié)構(gòu)大作業(yè)擴(kuò)展版） 2011-05-12 10:15 云
            
				
            再貼送兩個(gè)函數(shù)，這樣可以做很多事情了，哈！代碼的意思和set集里的函數(shù)一樣

            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;

            }  回復(fù)  更多評論
              
			
            
		
            
	




            






            

				
	



            


    
    







	   
	



激情伊人五月天久久综合|
91久久精品电影|
伊人精品久久久久7777|
久久久国产99久久国产一|
久久夜色精品国产噜噜亚洲AV|
无码AV中文字幕久久专区|
久久久精品午夜免费不卡|
国内精品久久久久影院网站|
中文字幕久久精品无码|
精品久久久久久无码人妻热
|
伊人久久大香线蕉综合热线|
久久精品aⅴ无码中文字字幕不卡|
国内精品久久久久伊人av|
青青久久精品国产免费看
|
久久婷婷五月综合色99啪ak|
国内精品伊人久久久影院|
久久久久久免费一区二区三区|
亚洲精品国产第一综合99久久|
99久久人妻无码精品系列蜜桃|
一级做a爰片久久毛片免费陪|
国产午夜福利精品久久|
欧美精品久久久久久久自慰|
一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区
|
精品九九久久国内精品|
亚洲综合伊人久久大杳蕉|
国产成人精品久久亚洲高清不卡|
日本强好片久久久久久AAA|
久久久黄色大片|
尹人香蕉久久99天天拍|
久久亚洲电影|
女同久久|
伊人久久大香线蕉综合网站|
久久亚洲2019中文字幕|
久久精品中文字幕有码|
91精品国产91久久久久久蜜臀|
国产精品无码久久综合|
久久国产乱子伦免费精品|
久久久婷婷五月亚洲97号色|
久久亚洲精品国产精品|
久久久久无码精品国产不卡|
久久国产免费观看精品3|