• <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>
            #include <iostream>

            using namespace std;

            typedef 
            int Type;

            struct Node{
                Type key;
                
            int  height;
                Node
            * lchild, *rchild;
                Node(){}
                Node( 
            int k, int h, Node* l, Node* r ):
                    key(k), height(h), lchild(l), rchild(r) {}
            };

            class AVLTree{
                
            private:
                    Node
            * _null;    //   規(guī)定的空結(jié)點
                    Node* root;     //   根結(jié)點 
                    
                    
            void left_single_rotate( Node*& r );     //  左單旋轉(zhuǎn) 
                    void left_double_rotate( Node*& r );     //  左雙旋轉(zhuǎn) 
                    void right_single_rotate( Node*& r );    //  右單旋轉(zhuǎn) 
                    void right_double_rotate( Node*& r );    //  右雙旋轉(zhuǎn) 
                    
                    
            void erase_rotate_help( Node*& r );      //  刪除操作中的旋轉(zhuǎn) 
                    
                    
            void travel( int, Node* root );          //  遍歷樹 
                    
                    
            void insert_help( Node*& r, Type key );  //  插入 
                    void erase_help ( Node*& r, Type key );  //  刪除 
                
                
            public:
                    AVLTree(){ _null
            = new Node( 00, NULL, NULL ); root= _null; }
                    
                    
            void travel();                           //  遍歷樹 
                    void insert( Type key );                 //  插入數(shù)據(jù) 
                    void erase ( Type key );                 //  刪除數(shù)據(jù) 
            };


            //   左單旋轉(zhuǎn)實現(xiàn) 
            void AVLTree::left_single_rotate( Node*& r ){
                Node
            * tmp= r->rchild;
                r
            ->rchild= tmp->lchild; 
                r
            ->height= max( r->lchild->height, r->rchild->height )+ 1;
                
                tmp
            ->lchild= r; r= tmp;
                r
            ->height= max( r->lchild->height, r->rchild->height )+ 1;
            }

            //  右單旋轉(zhuǎn)實現(xiàn) 
            void AVLTree::right_single_rotate( Node*& r ){
                Node
            * tmp= r->lchild;
                r
            ->lchild= tmp->rchild;
                r
            ->height= max( r->lchild->height, r->rchild->height )+ 1;
                
                tmp
            ->rchild= r; r= tmp;
                r
            ->height= max( r->lchild->height, r->rchild->height )+ 1;
            }

            //  左雙旋轉(zhuǎn)實現(xiàn)
            void AVLTree::left_double_rotate( Node*& r ){
                right_single_rotate( r
            ->rchild );
                left_single_rotate( r );
            }

            //  右雙旋轉(zhuǎn)實現(xiàn)
            void AVLTree::right_double_rotate( Node*& r ){
                left_single_rotate( r
            ->lchild );
                right_single_rotate( r );
            }

            void AVLTree::travel( int parent, Node* r ){
                
            if( r!= _null ){
                    travel( r
            ->key, r->lchild );
                    cout 
            << parent << ' ' << r->key << ' ' << r->height << endl;
                    travel( r
            ->key, r->rchild ); }
            }

            void AVLTree::travel(){
                travel( 
            -1, root ); }

            void AVLTree::insert_help( Node*& r, Type key ){
                
            if( r== _null ){
                    r
            = new Node( key, 1, _null, _null ); 
                    
            return;  }
                    
                
            if( key< r->key )  insert_help( r->lchild, key );
                
            else               insert_help( r->rchild, key );
                
                
            //  這上面一部分同二叉查找樹的代碼 ,AVL樹只是在其基礎(chǔ)上
                
            //  增加了旋轉(zhuǎn)保持平衡的操作 
                
                
                
            //  調(diào)整根結(jié)點的高度,因為增加結(jié)點后,高度可能增加 
                r->height= max( r->lchild->height, r->rchild->height )+ 1;
                
                
            //  如果右子樹不為空 
                if( r->rchild!= _null ){
                    
            // 左子樹的高度加上1等于右子樹的右子樹的高度,則左單旋轉(zhuǎn)
                    if( r->lchild->height+ 1== r->rchild->rchild->height )
                    left_single_rotate( r );
                    
            // 左子樹的高度加上1等于右子樹的左子樹的高度,則左雙旋轉(zhuǎn)
                    else if( r->lchild->height+ 1== r->rchild->lchild->height )
                    left_double_rotate( r );
                }
                
            //  如果左子樹不為空 
                if( r->lchild!= _null ){
                    
            // 右子樹的高度加上1等于左子樹的左子樹的高度,則右單旋轉(zhuǎn)
                    if( r->rchild->height+ 1== r->lchild->lchild->height )
                    right_single_rotate( r );
                    
            // 右子樹的高度加上1等于左子樹的右子樹的高度,則右雙旋轉(zhuǎn)
                    else if( r->rchild->height+ 1== r->lchild->rchild->height )
                    right_double_rotate( r );
                }
            }

            void AVLTree::insert( Type key ){
                insert_help( root, key ); }
                
            void AVLTree::erase_rotate_help( Node*& r ){
                
            //  右子樹高度比左子樹高度大2
                if( r->rchild->height- r->lchild->height== 2  ){
                    
            // 如果右子樹的左子樹的高度不大于右子樹的右子樹的高度則對根左單旋轉(zhuǎn)
                    if(    r->rchild->lchild->height<= r->rchild->rchild->height )
                    left_single_rotate( r );
                    
            // 如果右子樹的左子樹的高度大于右子樹的右子樹的高度則對根左雙旋轉(zhuǎn)
                    else 
                    left_double_rotate( r );
                }
                
            //  左子樹高度比右子樹高度大2 
                else if( r->lchild->height- r->rchild->height== 2  ){
                    
            //  如果左子樹的右子樹的高度不大于左子樹的左子樹的高度則對根右單旋轉(zhuǎn)
                    if( r->lchild->rchild->height<= r->lchild->lchild->height )
                    right_single_rotate( r );
                    
            //  如果左子樹的右子樹的高度大于左子樹的左子樹的高度則對根右雙旋轉(zhuǎn)
                    else 
                    right_double_rotate( r );
                }
            }
                
            void AVLTree::erase_help( Node*& r, Type key ){
                
            if( r== _null ) return;  //  沒有找到要刪除的結(jié)點則直接退出 
                
                
            if( r->key== key ){
                    
            if( r->rchild== _null ){
                        Node
            * tmp= r;
                        r
            = r->lchild; delete tmp;
                    }
                    
            else {
                        Node
            * tmp= r->rchild;
                        
            while( tmp->lchild!= _null ) tmp= tmp->lchild;
                        
                        r
            ->key= tmp->key;
                        erase_help( r
            ->rchild, tmp->key );
                        r
            ->height= max( r->lchild->height, r->rchild->height )+ 1;
                    }
                    
            return ;  }
                
                
            if( key< r->key ) erase_help( r->lchild, key );
                
            else              erase_help( r->rchild, key );

                
            //  同樣,這上面一部分同二叉查找樹的代碼 ,AVL樹只是在其基礎(chǔ)上
                
            //  增加了旋轉(zhuǎn)保持平衡的操作 
                
                
            //  調(diào)整高度 
                r->height= max( r->lchild->height, r->rchild->height )+ 1;
                
                
            //  有可能在左子樹中把結(jié)點刪除導(dǎo)致左子樹不平衡
                
            //  故先檢測左子樹是否已經(jīng)平衡,否 則調(diào)整 
                if( r->lchild!= _null ) erase_rotate_help( r->lchild );
                
                
            //  同樣右子樹中也有可能不平衡,檢測右子樹并調(diào)整 
                if( r->rchild!= _null ) erase_rotate_help( r->rchild );
                
                
            //  檢測根并調(diào)整 
                erase_rotate_help( r );
            }

            void AVLTree::erase( Type key ){
                erase_help( root, key ); }

            int main(){
                AVLTree test;
                freopen(
            "a.txt","w",stdout);
                
            forint i= 0; i< 100000++i )
                
            if( i& 1 ) test.insert( rand() );
                
            else       test.erase ( rand() );
                
                test.travel();

                
            return 0;
            }

            posted on 2009-05-07 22:03 Darren 閱讀(2605) 評論(6)  編輯 收藏 引用

            評論:
            # re: AVL樹的插入和刪除操作 2009-05-10 23:53 | 打醬油
            傳說中的手寫AVL樹?Orz。。。  回復(fù)  更多評論
              
            # re: AVL樹的插入和刪除操作 2009-05-22 11:42 | superlong
            拿走當(dāng)模板  回復(fù)  更多評論
              
            # re: AVL樹的插入和刪除操作 2009-05-22 12:02 | Darren
            @superlong
            只寫了個插入和刪除操作
            估計實際應(yīng)用還得增加些其它函數(shù)
              回復(fù)  更多評論
              
            # re: AVL樹的插入和刪除操作 2009-07-30 13:13 | 打醬油
            再給個返回最接近的值的操作吧。。。  回復(fù)  更多評論
              
            # re: AVL樹的插入和刪除操作[未登錄] 2012-02-28 10:53 | 小強
            代碼有錯,erase_help操作導(dǎo)致右兒子指針可能指向一個沒有分配存儲的地址  回復(fù)  更多評論
              
            # re: AVL樹的插入和刪除操作 2013-12-11 23:28 | jasonkent27@163.com
            樓主,請問一下,你的程序沒有報空指針異常嗎?
            程序中你這樣寫:
            if( r->rchild!= _null ){

            if( r->lchild->height+ 1== r->rchild->rchild->height )
            left_single_rotate( r );

            else if( r->lchild->height+ 1== r->rchild->lchild->height )
            left_double_rotate( r );
            }

            有沒有想過r->lchild為空 或者r->rchild-lchild為空的情況,為什么你的程序忽略的這些判斷也可以運行而不報錯?

            非常開心能和樓主交流!
            by jasonkent27@163.com  回復(fù)  更多評論
              

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            大香伊人久久精品一区二区| 精品久久人妻av中文字幕| 国产精品久久久久久搜索| 2021久久国自产拍精品| 久久九九精品99国产精品| 蜜桃麻豆www久久| 久久久久久极精品久久久| 久久这里都是精品| www.久久热.com| 免费国产99久久久香蕉| 国内精品久久久久久麻豆| 亚洲乱码中文字幕久久孕妇黑人| 久久青青草原精品国产| 久久精品国产亚洲av麻豆小说 | 2021久久精品国产99国产精品| 精品久久久久久久久午夜福利| 91精品国产乱码久久久久久| 国产精品久久久久久一区二区三区| 777久久精品一区二区三区无码| 久久国产亚洲精品| 亚洲中文字幕无码久久综合网| 久久人人爽人人爽AV片| 国产精品久久久久久久久| 国产精品综合久久第一页| 97久久国产亚洲精品超碰热| 国产一区二区精品久久凹凸 | 国产精品久久久久乳精品爆| 久久se精品一区二区影院| 精品久久久久久久国产潘金莲| 精品无码久久久久国产| 久久国产高清一区二区三区| 久久天堂AV综合合色蜜桃网| 97精品依人久久久大香线蕉97| 精品亚洲综合久久中文字幕| 久久A级毛片免费观看| 久久夜色撩人精品国产| 国产精品禁18久久久夂久| 热综合一本伊人久久精品| 热久久国产欧美一区二区精品| 久久九九亚洲精品| 久久久久久久久久久久中文字幕|