• <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
            <2007年3月>
            25262728123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            潛心看書(shū)研究!

            常用鏈接

            留言簿(19)

            隨筆分類(lèi)(81)

            文章分類(lèi)(89)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217820
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            基本測(cè)試沒(méi)問(wèn)題, 有bug請(qǐng)指出:)

            #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;? // 默認(rèn)空樹(shù)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 閱讀(1170) 評(píng)論(4)  編輯 收藏 引用 所屬分類(lèi): 算法&ACM

            FeedBack:
            # re: 終于把RBTree敲出來(lái)了, 累. 2006-09-15 10:25 small-fat
            .......呵呵,頂一下,牛牛..  回復(fù)  更多評(píng)論
              
            # re: 終于把RBTree敲出來(lái)了, 累. 2006-09-15 12:48 chenger
            用數(shù)組?感覺(jué)一般只有在做算法題時(shí)才這么干  回復(fù)  更多評(píng)論
              
            # re: 終于把RBTree敲出來(lái)了, 累. 2006-09-15 12:57 
            因?yàn)橛脭?shù)組可以換速度。。  回復(fù)  更多評(píng)論
              
            # re: 終于把RBTree敲出來(lái)了, 累. 2006-09-15 14:29 Optimistic
            偶看了都覺(jué)得累呀。。。。  回復(fù)  更多評(píng)論
              
            久久久精品无码专区不卡| 99久久精品免费观看国产| 色偷偷偷久久伊人大杳蕉| 久久线看观看精品香蕉国产| 精品久久久久久无码国产| 久久久久久精品久久久久| 久久精品国产99国产精品澳门| 午夜视频久久久久一区 | 91精品免费久久久久久久久| 伊人久久大香线蕉精品不卡| 久久久国产精品福利免费| 伊人久久一区二区三区无码| 久久精品国产半推半就| 无码AV中文字幕久久专区| 久久久国产精品| 51久久夜色精品国产| 一本色道久久综合狠狠躁| 久久久噜噜噜久久| 91久久精品电影| 潮喷大喷水系列无码久久精品| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 99久久无码一区人妻a黑| 狠狠综合久久综合88亚洲| 国产免费福利体检区久久| 国产精品久久久久久福利漫画| 日韩人妻无码一区二区三区久久99| 久久99精品国产99久久6| 久久九九有精品国产23百花影院| 人妻精品久久无码区| 国产色综合久久无码有码| 国内精品久久久久影院老司| 欧美午夜精品久久久久久浪潮| 91久久九九无码成人网站| 精品久久久久久综合日本| 99久久国语露脸精品国产| 狠狠色丁香久久综合婷婷| 日本道色综合久久影院| 久久99精品国产99久久6| 亚洲精品国产综合久久一线| 亚洲伊人久久成综合人影院 | 亚洲精品97久久中文字幕无码|