青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Jiang's C++ Space

創(chuàng)作,也是一種學(xué)習(xí)的過(guò)程。

   :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::

這篇將是最有難度和挑戰(zhàn)性的一篇,做好心理準(zhǔn)備!

十、二叉查找樹(BST)

前一篇介紹了樹,卻未介紹樹有什么用。但就算我不說(shuō),你也能想得到,看我們Windows的目錄結(jié)構(gòu),其實(shí)就是樹形的,一個(gè)典型的分類應(yīng)用。當(dāng)然除了分類,樹還有別的作用,我們可以利用樹建立一個(gè)非常便于查找取值又非常便于插入刪除的數(shù)據(jù)結(jié)構(gòu),這就是馬上要提到的二叉查找樹(Binary Search Tree),這種二叉樹有個(gè)特點(diǎn):對(duì)任意節(jié)點(diǎn)而言,左子(當(dāng)然了,存在的話)的值總是小于本身,而右子(存在的話)的值總是大于本身。

這種特性使得我們要查找其中的某個(gè)值都很容易,從根開始,小的往左找,大的往右找,不大不小的就是這個(gè)節(jié)點(diǎn)了;插入一樣的道理,從根開始,小的往左,大的往右,直到葉子,就插入,算法比較簡(jiǎn)單,不一一列了,它們的時(shí)間復(fù)雜度期望為Ο(logn)。(為什么是“期望”,后面會(huì)講)

刪除則稍微麻煩點(diǎn),因?yàn)槲覀儎h的不一定是葉子,如果只是葉子,那就好辦,如果不是呢?我們最通常的做法就是把這個(gè)節(jié)點(diǎn)往下挪,直到它變?yōu)槿~子為止,看圖。


也許你要問(wèn),如果和左子樹最大節(jié)點(diǎn)交換后,要?jiǎng)h除的節(jié)點(diǎn)依然不是葉子,那怎么辦呢?那繼續(xù)唄,看圖:

那左子樹不存在的情況下呢?你可以查找右子樹的最小節(jié)點(diǎn),和上面是類似的,圖我就不畫了。

十一、平衡二叉查找樹(AVL)

前面說(shuō)了,二叉查找樹方便查找取值插入刪除,其復(fù)雜度不過(guò)為Ο(logn),但這是個(gè)“期望值”,因?yàn)槲覀円灿斜容^差的情況,比如下面這棵樹:

說(shuō)是樹,其實(shí)已經(jīng)退化為鏈表了,但從概念上來(lái)說(shuō)它依然是一棵二叉查找樹,這棵樹怎么形成的呢?很簡(jiǎn)單,我們只要按著1,2,3,4,5,6,7這樣的順序往一個(gè)空的二叉查找樹里添加元素,就形成了。這樣我們?cè)偬砑?,9,10……那真的就變成了一個(gè)鏈表結(jié)構(gòu),那插入的復(fù)雜度也就變成了Ο(n)。導(dǎo)致這種糟糕的原因是這棵樹非常不平衡,右樹的重量遠(yuǎn)大于左樹,所以我們提出了一種叫“平衡二叉查找樹”的結(jié)構(gòu),平衡二叉查找樹英文叫AVL,而不是我本來(lái)以為的什么Balance BST,AVL來(lái)自于人名,我這里就不追究了。

平衡,顧名思義,就是兩邊看起來(lái)比較對(duì)稱,但很多時(shí)候我們是做不到絕對(duì)的對(duì)稱(絕對(duì)對(duì)稱即對(duì)任意子樹而言,左右節(jié)點(diǎn)的數(shù)量都相等),因?yàn)橹挥?2^n-1)元素?cái)?shù)目的二叉樹才能做到絕對(duì)對(duì)稱,所以我們使用了“高度”(height)這么個(gè)概念,某節(jié)點(diǎn)的高度指的是它離它的子樹的葉子的最遠(yuǎn)距離:


那么我再引申出兩個(gè)概念,左高和右高:
左高 = 左節(jié)點(diǎn)空 ? 0 : (左節(jié)點(diǎn)高+1)
右高 = 右節(jié)點(diǎn)空 ? 0 : (右節(jié)點(diǎn)高+1)

那我們就可以給AVL下個(gè)定義了,對(duì)AVL的任意節(jié)點(diǎn)而言:

ABS(左高 - 右高) <= 1

做到了這點(diǎn),這棵樹看起來(lái)就比較平衡了,如何生成一棵AVL樹呢?算法十分不簡(jiǎn)單,那我們先通過(guò)圖來(lái)獲得一些最直觀的認(rèn)識(shí),就先按1,2,3,4……這樣的自然數(shù)順序加入到樹中,下圖體現(xiàn)出了樹的構(gòu)造變化:

隨著新節(jié)點(diǎn)的加入,樹自動(dòng)調(diào)整自身結(jié)構(gòu),達(dá)到新的平衡狀態(tài),這就是我們想要的AVL樹。我們先要分析,為什么樹會(huì)失衡?是由于插入了一個(gè)元素,對(duì)吧,那我們能不能把不同的插入情況全部概括起來(lái)并作出統(tǒng)一的調(diào)整來(lái)使得樹重新平衡?答案是肯定的,也有人幫我們研究好了,只是證明這個(gè)過(guò)程需要一些數(shù)學(xué)功底,我是不行的了,所以直接給出算法示意圖和范例。

LL型調(diào)整:


再給一個(gè)LL型調(diào)整的實(shí)例:

RR型調(diào)整,其實(shí)就是LL型調(diào)整的鏡像而已:


這是一個(gè)RR型調(diào)整的實(shí)例:

接下去就是LR型調(diào)整:

這是一個(gè)LR型調(diào)整的實(shí)例:

RL型調(diào)整是LR型調(diào)整的鏡像,所以不再畫圖了。

至于如何選擇不同的調(diào)整類型,我后面將給出代碼,看“DoBalance”這個(gè)函數(shù)的實(shí)現(xiàn),很清晰的。那接下去我們還要面臨一個(gè)比較困難的問(wèn)題,就是刪除及刪除平衡,因?yàn)椴还馐遣迦朐乜赡軐?dǎo)致不平衡,刪除也會(huì)。不過(guò)我們都有個(gè)同樣的前提,就是無(wú)論是插入前還是刪除前的二叉樹,都是平衡的。

我參考的書上說(shuō)刪除和插入其實(shí)是很類似的,具體實(shí)現(xiàn)卻沒(méi)說(shuō),我后來(lái)寫代碼蠻辛苦的,最后發(fā)現(xiàn)確實(shí)差別不大,但在調(diào)整相關(guān)節(jié)點(diǎn)高度的時(shí)候確實(shí)有點(diǎn)細(xì)微上的差別,這個(gè)在我的代碼里也能看得出來(lái)。下面我就給出我的代碼,我已經(jīng)通過(guò)了初步的測(cè)試,不過(guò)也許代碼還有bug,如果發(fā)現(xiàn)了,請(qǐng)留言。

代碼比較長(zhǎng),其中還利用了之前的堆棧和隊(duì)列結(jié)構(gòu),可以算是復(fù)習(xí),如果覺(jué)得代碼晦澀難懂,也可以跳過(guò),有些怕自己的代碼寫得不夠好……

另附帶一些代碼說(shuō)明:
1,TreeNode目前只帶一個(gè)“數(shù)據(jù)”,就是iData,所以交換節(jié)點(diǎn)位置時(shí)候,為了方便,只需要交換這個(gè)數(shù)據(jù);
2,代碼中的pMinBST指向的是“最小不平衡樹”,即:從插入或刪除的位置開始往上查找出現(xiàn)的第一個(gè)不平衡的節(jié)點(diǎn);
3,“往上查找”就需要借助一個(gè)Stack結(jié)構(gòu);
4,AVL樹的析構(gòu)采用了后序遍歷,由于是析構(gòu),之后不再用到,所以后序遍歷時(shí)候改變了節(jié)點(diǎn)指針的值,后續(xù)遍歷使用了Queue結(jié)構(gòu);
5,刪除節(jié)點(diǎn)時(shí)候,尋找并交換葉子節(jié)點(diǎn)的操作有些晦澀,往左尋找最大節(jié)點(diǎn),為什么找到了最大并交換,而它還不是葉子的時(shí)候,我只需要再往左找并交換一次就可以了呢?因?yàn)槲覄h除到時(shí)候有個(gè)前提:這棵樹是平衡的,往右尋找最小節(jié)點(diǎn)的道理跟這個(gè)一樣的;
6,有什么問(wèn)題請(qǐng)留言。

#include "stdio.h"

// TreeNode
//////////////////////////////////////////////////////////////////////////
struct TreeNode
{
    TreeNode(
int iVal);
    
int UpdateHeight();
    
int GetLeftHeight();
    
int GetRightHeight();
    
int GetDiff(); //Left Height - Right height

    
int iData;

    
int iHeight;
    TreeNode
* pLeft;
    TreeNode
* pRight;
};

TreeNode::TreeNode(
int iVal)
{
    iData 
= iVal;
    iHeight 
= 0;
    pLeft 
= 0;
    pRight 
= 0;
}

int TreeNode::UpdateHeight()
{
    
int iHeightLeft = GetLeftHeight();
    
int iHeightRight = GetRightHeight();
    
if(iHeightLeft==0 && iHeightRight==0)
        iHeight 
= 0;
    
else
        iHeight 
= (iHeightLeft>iHeightRight)?(iHeightLeft):(iHeightRight);
    
return iHeight;
}

int TreeNode::GetLeftHeight()
{
    
if(pLeft!=0)
        
return pLeft->iHeight + 1;
    
else
        
return 0;
}

int TreeNode::GetRightHeight()
{
    
if(pRight!=0)
        
return pRight->iHeight + 1;
    
else
        
return 0;
}

int TreeNode::GetDiff()
{
    
int iHeightLeft = 0;
    
int iHeightRight = 0;
    
    
if(pLeft!=0)
        iHeightLeft 
= pLeft->iHeight + 1;
    
if(pRight!=0)
        iHeightRight 
= pRight->iHeight + 1;

    
return iHeightLeft - iHeightRight;
}

// Stack
//////////////////////////////////////////////////////////////////////////
class Stack
{
public:
    Stack(
int iAmount = 10);
    
~Stack();
    
    
//return 1 means succeeded, 0 means failed.
    int Pop(TreeNode* & val);
    
int Push(TreeNode* val);
    
int Top(TreeNode* & val);

    
//iterator
    int GetTop(TreeNode* &val);
    
int GetNext(TreeNode* &val);
private:
    TreeNode
** m_pData;
    
int m_iCount;
    
int m_iAmount;

    
//iterator
    int m_iCurr;
};

Stack::Stack(
int iAmount)
{
    m_pData 
= new TreeNode*[iAmount];
    m_iCount 
= 0;
    m_iAmount 
= iAmount;
    m_iCurr 
= 0;
}

Stack::
~Stack()
{
    delete m_pData;
}

int Stack::Pop(TreeNode* & val)
{
    
if(m_iCount>0)
    {
        
--m_iCount;
        val 
= m_pData[m_iCount];
        
return 1;
    }
    
return 0;
}

int Stack::Push(TreeNode* val)
{
    
if(m_iCount<m_iAmount)
    {
        m_pData[m_iCount] 
= val;
        
++m_iCount;
        
return 1;
    }
    
return 0;
}

int Stack::Top(TreeNode* & val)
{
    
if(m_iCount>0 && m_iCount<=m_iAmount)
    {
        val 
= m_pData[m_iCount-1];
        
return 1;
    }
    
return 0;
}

int Stack::GetTop(TreeNode* &val)
{
    
if(m_iCount>0 && m_iCount<=m_iAmount)
    {
        val 
= m_pData[m_iCount-1];
        m_iCurr 
= m_iCount - 1;
        
return 1;
    }
    
return 0;
}

int Stack::GetNext(TreeNode* &val)
{
    
if((m_iCurr-1)<(m_iCount-1&& (m_iCurr-1)>=0)
    {
        
--m_iCurr;
        val 
= m_pData[m_iCurr];
        
return 1;
    }
    
return 0;
}

// The Queue
//////////////////////////////////////////////////////////////////////////
class Queue
{
public:
    Queue(
int iAmount=10);
    
~Queue();
    
    
//return 0 means failed, return 1 means succeeded.
    int Enqueue(TreeNode* node);
    
int Dequeue(TreeNode* & node);
private:
    
int m_iAmount;
    
int m_iCount;
    TreeNode
** m_ppFixed; //The pointer array to implement the queue.
    
    
int m_iHead;
    
int m_iTail;
};

Queue::Queue(
int iAmount)
{
    m_iCount 
= 0;
    m_iAmount 
= iAmount;
    m_ppFixed 
= new TreeNode*[iAmount];
    
    m_iHead 
= 0;
    m_iTail 
= iAmount-1;
}

Queue::
~Queue()
{
    delete[] m_ppFixed;
}

int Queue::Enqueue(TreeNode* node)
{
    
if(m_iCount<m_iAmount)
    {
        
++m_iTail;
        
if(m_iTail > m_iAmount-1)
            m_iTail 
= 0;
        m_ppFixed[m_iTail] 
= node;
        
++m_iCount;
        
return 1;
    }
    
else
        
return 0;
}

int Queue::Dequeue(TreeNode* & node)
{
    
if(m_iCount>0)
    {
        node 
= m_ppFixed[m_iHead];
        
++m_iHead;
        
if(m_iHead > m_iAmount-1)
            m_iHead 
= 0;
        
--m_iCount;
        
return 1;
    }
    
else
        
return 0;
}

// AVLTree
//////////////////////////////////////////////////////////////////////////
class CAVLTree
{
public:
    CAVLTree();
    
~CAVLTree();
    
    TreeNode
* Insert(int iVal);
    
int Delete(int iVal);
    TreeNode
* FindNode(int iVal); //the find function, returns 0 means not found.
    
#ifdef _DEBUG
    
void PrintTree();
#endif

protected:
    
//Update the height after insert or delete.
    
//And find the minimum unbalance BST.
    int UpdateHeight(Stack &st, TreeNode* &pMinBST, TreeNode* &pMinBSTParent, int& iLeftRight);

    
//Rotate
    void DoBalance(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight);
    
void LLRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight);
    
void RRRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight);
    
void LRRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight, int iSpecialFlag=0);
    
void RLRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight, int iSpecialFlag=0);
    
    
void SwapTwoNodes(TreeNode *pNode1, TreeNode *pNode2); //Swap their value only.

    TreeNode 
*m_pRoot;
};

CAVLTree::CAVLTree()
{
    m_pRoot 
= NULL;
}

CAVLTree::
~CAVLTree()
{
    Stack st(
40); //2^40 must be enough.

    
//Postorder traverse the tree to release all nodes.
    TreeNode *pNode = m_pRoot;
    TreeNode 
*pTemp;
    
if(pNode==0)
        
return;

    
while (1)
    {
        
if(pNode->pLeft!=0)
        {
            st.Push(pNode);
            pTemp 
= pNode;
            pNode 
= pNode->pLeft;
            pTemp
->pLeft = 0;
            
continue;
        }
        
        
if(pNode->pRight!=0)
        {
            st.Push(pNode);
            pTemp 
= pNode;
            pNode 
= pNode->pRight;
            pTemp
->pRight = 0;
            
continue;
        }
        
        delete pNode;

        
if(0==st.Pop(pNode))
            
break;
    }
}

TreeNode
* CAVLTree::Insert(int iVal)
{
    Stack st(
40); //To record the path.
    TreeNode *pNode = m_pRoot;
    TreeNode 
*pIns;
    
int iLeftOrRight; // 0 means left, 1 means right.
    while (1)
    {
        
if(pNode==0//Insert at this position
        {
            TreeNode 
*pNew = new TreeNode(iVal);
            TreeNode 
*pPrev;
            
if(0!=st.Top(pPrev))
            {
                
if(0==iLeftOrRight)
                    pPrev
->pLeft = pNew;
                
else
                    pPrev
->pRight = pNew;
            }
            
else //The root
            {
                m_pRoot 
= pNew;
                
return m_pRoot;
            }

            pIns 
= pNew;
            
if(0==iLeftOrRight && pPrev->pRight!=0 || 1==iLeftOrRight && pPrev->pLeft!=0//Need not to change.
                return pIns;

            
break;
        }

        
if(iVal<pNode->iData)
        {
            st.Push(pNode);
            pNode 
= pNode->pLeft;
            iLeftOrRight 
= 0;
        }
        
else if(iVal>pNode->iData)
        {
            st.Push(pNode);
            pNode 
= pNode->pRight;
            iLeftOrRight 
= 1;
        }
        
else
            
return pNode;
    }

    TreeNode
* pMinBST;
    TreeNode
* pMinBSTParent;
    
int iLRParent;
    UpdateHeight(st, pMinBST, pMinBSTParent, iLRParent);
    
if(pMinBST!=0//It exists. need balance.
    {
        DoBalance(pMinBST, pMinBSTParent, iLRParent);
    }
    
return pIns;
}

//Update the height after insert or delete.
int CAVLTree::UpdateHeight(Stack &st, TreeNode* &pMinBST, TreeNode* &pMinBSTParent, int& iLRParent)
{
    TreeNode 
*pNode;
    pMinBST 
= 0;
    pMinBSTParent 
= 0;

    
if(0==st.GetTop(pNode))
        
return 0;
    
    
while(1)
    {
        pNode
->UpdateHeight();
        
int iDiff = pNode->GetDiff();
        
if(iDiff>1 || iDiff<-1//unbalance
        {
            pMinBST 
= pNode;
            
if(0!=st.GetNext(pMinBSTParent))
            {
                
if(pMinBSTParent->pLeft==pMinBST)
                    iLRParent 
= 0//left
                else
                    iLRParent 
= 1//right
            }
            
return 0;
        }

        
if(0==st.GetNext(pNode))
            
break;
    }

    
return 0;
}

void CAVLTree::DoBalance(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight)
{
    
if(pNode->GetLeftHeight() < pNode->GetRightHeight())
    {
        
if(pNode->pRight->GetLeftHeight() < pNode->pRight->GetRightHeight())
            RRRotate(pNode, pMinBSTParent, iLeftRight);
        
else if(pNode->pRight->GetLeftHeight() > pNode->pRight->GetRightHeight())
            RLRotate(pNode, pMinBSTParent, iLeftRight);
        
else
            RLRotate(pNode, pMinBSTParent, iLeftRight, 
1);
    }
    
else
    {
        
if(pNode->pLeft->GetLeftHeight() > pNode->pLeft->GetRightHeight())
            LLRotate(pNode, pMinBSTParent, iLeftRight);
        
else if(pNode->pLeft->GetLeftHeight() < pNode->pLeft->GetRightHeight())
            LRRotate(pNode, pMinBSTParent, iLeftRight);
        
else
            LRRotate(pNode, pMinBSTParent, iLeftRight, 
1);
    }
}

//      B               A
//     / \             / \
//    A   BR    =>    AL  B
//   / \              +  / \
//  AL  AR              AR  BR
//  +
void CAVLTree::LLRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight)
{
    
//B, A and AL must be exist. BR and AR may be null.
    TreeNode *pNodeB = pNode;
    TreeNode 
*pNodeA = pNodeB->pLeft;
    TreeNode 
*pNodeAR = pNodeA->pRight;
    pNodeA
->pRight = pNodeB;
    pNodeB
->pLeft = pNodeAR;

    
//Handle the height
    pNodeB->iHeight -= 2;

    
if(pMinBSTParent==0//root
        m_pRoot = pNodeA;
    
else
    {
        
if(iLeftRight==0//left
            pMinBSTParent->pLeft = pNodeA;
        
else
            pMinBSTParent
->pRight = pNodeA;
    }
}

//      A                B
//     / \              / \
//    AL  B      =>    A   BR
//       / \          / \  +
//      BL  BR       AL  BL
//          +
void CAVLTree::RRRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight)
{
    TreeNode 
*pNodeA = pNode;
    TreeNode 
*pNodeB = pNodeA->pRight;
    TreeNode 
*pNodeBL = pNodeB->pLeft;
    pNodeB
->pLeft = pNodeA;
    pNodeA
->pRight = pNodeBL;

    
//Handle the height
    pNodeA->iHeight -= 2;

    
if(pMinBSTParent==0//root
        m_pRoot = pNodeB;
    
else
    {
        
if(iLeftRight==0//left
            pMinBSTParent->pLeft = pNodeB;
        
else
            pMinBSTParent
->pRight = pNodeB;
    }
}

//          C                   B
//         / \                /   \
//        A   CR             A     C
//       / \         =>     / \   / \
//      AL  B              AL BL BR CR
//         / \                   +
//        BL  BR
//            +
// Special flag is used for some kind of delete operation, for example:
//        4                   3
//       / \                 / \
//      2   5(-)    =>      2   4
//     / \                 /
//    1   3               1
void CAVLTree::LRRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight, int iSpecialFlag)
{
    TreeNode 
*pNodeC = pNode;
    TreeNode 
*pNodeA = pNodeC->pLeft;
    TreeNode 
*pNodeB = pNodeA->pRight;
    TreeNode 
*pNodeBL = pNodeB->pLeft;
    TreeNode 
*pNodeBR = pNodeB->pRight;
    pNodeB
->pLeft = pNodeA;
    pNodeB
->pRight = pNodeC;
    pNodeA
->pRight = pNodeBL;
    pNodeC
->pLeft = pNodeBR;

    
//Handle the height
    if(iSpecialFlag==0)
    {
        pNodeA
->iHeight -= 1;
        pNodeB
->iHeight += 1;
    }
    
else
    {
        pNodeB
->iHeight += 2;
    }
    pNodeC
->iHeight -= 2;

    
if(pMinBSTParent==0//root
        m_pRoot = pNodeB;
    
else
    {
        
if(iLeftRight==0//left
            pMinBSTParent->pLeft = pNodeB;
        
else
            pMinBSTParent
->pRight = pNodeB;
    }
}

//          B                   A
//         / \                /   \
//        BL  C              B     C
//           / \      =>    / \   / \
//          A   CR         BL AL AR CR
//         / \                   +
//        AL  AR
//            +
// Special flag is used for some kind of delete operation, for example:
//        3                   4
//       / \                 / \
//   (-)2   5      =>       3   5
//         / \                   \
//        4   6                   6
void CAVLTree::RLRotate(TreeNode *pNode, TreeNode* pMinBSTParent, int iLeftRight, int iSpecialFlag)
{
    TreeNode 
*pNodeB = pNode;
    TreeNode 
*pNodeC = pNodeB->pRight;
    TreeNode 
*pNodeA = pNodeC->pLeft;
    TreeNode 
*pNodeAL = pNodeA->pLeft;
    TreeNode 
*pNodeAR = pNodeA->pRight;
    pNodeA
->pLeft = pNodeB;
    pNodeA
->pRight = pNodeC;
    pNodeC
->pLeft = pNodeAR;
    pNodeB
->pRight = pNodeAL;

    
//Handle the height
    if(iSpecialFlag==0)
    {
        pNodeC
->iHeight -= 1;
        pNodeA
->iHeight += 1;
    }
    
else
    {
        pNodeA
->iHeight += 2;
    }
    pNodeB
->iHeight -= 2;
    
    
if(pMinBSTParent==0//root
        m_pRoot = pNodeA;
    
else
    {
        
if(iLeftRight==0//left
            pMinBSTParent->pLeft = pNodeA;
        
else
            pMinBSTParent
->pRight = pNodeA;
    }
}

int CAVLTree::Delete(int iVal)
{
    
if(m_pRoot==0)
        
return 0;

    Stack st(
40); //To record the path.
    TreeNode *pNode = m_pRoot;
    TreeNode 
*pPrev;
    
int iLeftOrRight; // 0 means left, 1 means right.

    
while (1)
    {
        
if(pNode->iData==iVal) //Yes, it is.
        {
            st.Push(pNode);
            
break;
        }

        
if(iVal<pNode->iData)
        {
            st.Push(pNode);
            
if(pNode->pLeft!=0)
                pNode 
= pNode->pLeft;
            
else
                
return 0;
            iLeftOrRight 
= 0;
        }
        
else //iVal > pNode->iData
        {
            st.Push(pNode);
            
if(pNode->pRight!=0)
                pNode 
= pNode->pRight;
            
else
                
return 0;
            iLeftOrRight 
= 1;
        }
    }
    
    
int iLeafLeftRight;

    
if(pNode->iHeight==0//It is the leaf node.
    {
        
if(0!=st.GetTop(pPrev))
        {
            iLeafLeftRight 
= iLeftOrRight;
        }
        
else //The root, this tree is going to be null.
        {
            delete m_pRoot;
            m_pRoot 
= 0;
            
return 0;
        }
    }
    
else if(pNode->pLeft!=NULL)
    {
        iLeafLeftRight 
= 0;
        
//Move this node to the bottom.
        TreeNode *pBiggestLeft = pNode->pLeft;
        st.Push(pBiggestLeft);
        
while(pBiggestLeft->pRight!=NULL)
        {
            pBiggestLeft 
= pBiggestLeft->pRight;
            st.Push(pBiggestLeft);
            iLeafLeftRight 
= 1;
        }
        SwapTwoNodes(pBiggestLeft, pNode);
        
if(pBiggestLeft->pLeft!=NULL)
        {
            SwapTwoNodes(pBiggestLeft, pBiggestLeft
->pLeft);
            st.Push(pBiggestLeft
->pLeft);
            iLeafLeftRight 
= 0;
        }
    }
    
else //pNode->pRight!=NULL
    {
        iLeafLeftRight 
= 1;
        
//Move this node to the bottom.
        TreeNode *pLeastRight = pNode->pRight;
        st.Push(pLeastRight);
        
while(pLeastRight->pLeft!=NULL)
        {
            pLeastRight 
= pLeastRight->pLeft;
            st.Push(pLeastRight);
            iLeafLeftRight 
= 0;
        }
        SwapTwoNodes(pLeastRight, pNode);
        
if(pLeastRight->pRight!=NULL)
        {
            SwapTwoNodes(pLeastRight, pLeastRight
->pRight);
            st.Push(pLeastRight
->pRight);
            iLeafLeftRight 
= 1;
        }
    }

    
//Delete the leaf.
    TreeNode *pToDel;
    st.Pop(pToDel);
    delete pToDel;
    TreeNode 
*pToChange;
    st.GetTop(pToChange);
    
if(iLeafLeftRight==0)
        pToChange
->pLeft = 0;
    
else
        pToChange
->pRight = 0;

    TreeNode
* pMinBST;
    TreeNode
* pMinBSTParent;
    
int iLRParent;
    UpdateHeight(st, pMinBST, pMinBSTParent, iLRParent);
    
if(pMinBST!=0//It exists. need balance.
    {
        DoBalance(pMinBST, pMinBSTParent, iLRParent);
    }

    
return 0;
}

TreeNode
* CAVLTree::FindNode(int iVal)
{
    TreeNode
* pNode = m_pRoot;
    
while (pNode!=0)
    {
        
if(iVal<pNode->iData)
            pNode 
= pNode->pLeft;
        
else if(iVal>pNode->iData)
            pNode 
= pNode->pRight;
        
else
            
return pNode;
    }

    
return 0;
}

void CAVLTree::SwapTwoNodes(TreeNode *pNode1, TreeNode *pNode2)
{
    
int iDataTmp = pNode1->iData;

    pNode1
->iData = pNode2->iData;

    pNode2
->iData = iDataTmp;
}

#ifdef _DEBUG

void CAVLTree::PrintTree()
{
    printf(
"--------------------\n");
    
if(m_pRoot==0)
    {
        printf(
"null tree.\n");
        
return;
    }
    Queue que(
100);
    que.Enqueue(m_pRoot);
    TreeNode
* pNode;
    
while (0!=que.Dequeue(pNode))
    {
        
if(pNode->pLeft!=0 && pNode->pRight!=0)
        {
            printf(
"%d(%d) -> %d %d\n", pNode->iData, pNode->iHeight, pNode->pLeft->iData, pNode->pRight->iData);
            que.Enqueue(pNode
->pLeft);
            que.Enqueue(pNode
->pRight);
        }
        
else if(pNode->pLeft!=0)
        {
            que.Enqueue(pNode
->pLeft);
            printf(
"%d(%d) -> %d x\n", pNode->iData, pNode->iHeight, pNode->pLeft->iData);
        }
        
else if(pNode->pRight!=0)
        {
            que.Enqueue(pNode
->pRight);
            printf(
"%d(%d) -> x %d\n", pNode->iData, pNode->iHeight, pNode->pRight->iData);
        }
    }
}

#endif

// Main
//////////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
    CAVLTree avl;
    avl.Insert(
14);
    avl.Insert(
11);
    avl.Insert(
13);
    avl.Insert(
1);
    avl.Insert(
4);
    avl.Insert(
3);
    avl.Insert(
15);
    avl.Insert(
2);
    avl.Insert(
9);
    avl.Insert(
10);
    avl.Insert(
8);
    avl.Insert(
7);

    avl.Delete(
10);
    avl.Delete(
8);
    avl.Delete(
7);
    avl.Delete(
13);
#ifdef _DEBUG
    avl.PrintTree();
#endif

    
return 0;
}
代碼中有些注釋顯示得不太正常,這是因?yàn)檫@個(gè)博客中的代碼部分不適用等寬字符的緣故,拿到你的IDE下看就正常了。
posted on 2009-10-26 17:18 Jiang Guogang 閱讀(6693) 評(píng)論(8)  編輯 收藏 引用 所屬分類: Knowledge

評(píng)論

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2009-10-26 17:46 matthew0816
國(guó)綱,我的基礎(chǔ)知識(shí)只能靠你來(lái)補(bǔ)了  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2009-10-26 17:46 matthew0816
繼續(xù)努力呢,
這個(gè)系列很棒,
完全可以開課了  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹[未登錄](méi) 2009-12-29 21:08 hao
LZ,你的數(shù)據(jù)結(jié)構(gòu)系列的課程真是講得太好了!!!!
用力地頂啊!!!!

如果再講一下B+樹和B-樹那就更好了,呵呵。  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2010-08-20 07:43 自學(xué)數(shù)據(jù)結(jié)構(gòu)者
LZ能講其他的嗎,希望繼續(xù)哦  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2010-08-20 15:26 Jiang Guogang
我是樓主,謝謝捧場(chǎng),其實(shí)我對(duì)數(shù)據(jù)結(jié)構(gòu)了解也不多,寫這幾篇文章時(shí)候正好空余時(shí)間比較多,我也是花了不少時(shí)間整理的。目前寫不出這種文章了。  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2011-06-19 00:54 龍?bào)J樓
樓主寫得太棒了,一圖勝千言啊,代碼也不錯(cuò),傳世經(jīng)典啊  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2011-12-11 00:09 thunder
有木有構(gòu)建最佳二叉排序樹的吖?  回復(fù)  更多評(píng)論
  

# re: 圖解數(shù)據(jù)結(jié)構(gòu)(7)——二叉查找樹及平衡二叉查找樹 2016-04-28 08:28 666
66666  回復(fù)  更多評(píng)論
  

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            狂野欧美一区| aⅴ色国产欧美| 久久都是精品| 久久久久久久高潮| 1024国产精品| 亚洲欧洲一区二区三区久久| 欧美成人激情在线| 亚洲伊人色欲综合网| 亚洲欧美日韩网| 尹人成人综合网| 国产婷婷一区二区| 久久激五月天综合精品| 久久久久免费视频| 99国内精品久久| 性色av一区二区三区红粉影视| 好吊色欧美一区二区三区视频| 亚洲国产成人一区| 国产精品久久久久久影视| 久久精品中文字幕免费mv| 麻豆精品精华液| 亚洲欧美视频在线观看视频| 久久xxxx精品视频| 一本色道婷婷久久欧美| 欧美在线视屏| 亚洲一区二区三区欧美| 久久精品一区四区| 亚洲一品av免费观看| 久久久久久久综合色一本| 99视频超级精品| 久久精品国产一区二区三区| 中日韩午夜理伦电影免费| 欧美中文字幕在线播放| 中文亚洲欧美| 麻豆精品在线观看| 久久精品免费观看| 国产精品成人一区二区网站软件 | 国产日韩免费| 亚洲国产精品www| 韩国精品一区二区三区| 一区二区三区av| 99精品视频免费| 久久综合久久综合久久综合| 欧美一区二区视频在线观看2020 | 久久精品国产一区二区三区| 亚洲天堂视频在线观看| 欧美成va人片在线观看| 久久这里有精品视频| 免费成人在线观看视频| 国产精品一级二级三级| 亚洲精品美女久久7777777| 亚洲高清电影| 久热这里只精品99re8久| 久久国产天堂福利天堂| 国产精品高潮呻吟久久| 99视频在线精品国自产拍免费观看 | 亚洲精品免费在线播放| 亚洲人体1000| 免费成人你懂的| 久久在线免费观看| 在线播放日韩专区| 久久久在线视频| 美女成人午夜| 亚洲国产视频一区二区| 久久人人爽人人爽| 欧美α欧美αv大片| 亚洲国产美女| 欧美电影电视剧在线观看| 亚洲国产一区二区在线| 亚洲免费电影在线观看| 欧美日韩国产黄| 宅男66日本亚洲欧美视频| 亚洲欧美日韩精品| 国产欧美亚洲视频| 久久精品在线免费观看| 欧美激情按摩| 在线视频免费在线观看一区二区| 欧美日韩成人在线| 亚洲一区国产视频| 久久久精品五月天| 亚洲国产精品视频一区| 欧美国产丝袜视频| 在线一区二区三区四区五区| 欧美亚洲免费电影| 在线观看欧美黄色| 欧美日韩国产精品专区| 亚洲午夜精品一区二区| 久久久青草青青国产亚洲免观| 激情综合电影网| 欧美久久久久久久久久| 一区二区三区视频免费在线观看| 久久成人免费视频| 亚洲全部视频| 国产欧美一区二区三区在线老狼 | 亚洲一区图片| 免费亚洲电影| 亚洲视频香蕉人妖| 国内精品嫩模av私拍在线观看| 欧美国产高清| 午夜精品999| 亚洲国产综合视频在线观看| 香蕉久久久久久久av网站| 亚洲第一精品福利| 国产精品日产欧美久久久久| 久久亚洲私人国产精品va媚药 | 欧美激情视频给我| 午夜在线观看欧美| 亚洲精品一二三| 国产情人综合久久777777| 欧美成人官网二区| 久久av一区二区三区| 国产亚洲成人一区| 欧美日韩视频一区二区三区| 午夜精品99久久免费| 亚洲精品在线免费观看视频| 噜噜噜躁狠狠躁狠狠精品视频 | 一区二区在线看| 国产精品美女www爽爽爽| 美女国产精品| 久久国产主播| 亚洲欧美在线一区| 一本色道久久综合亚洲精品婷婷 | 理论片一区二区在线| 亚洲中字黄色| 一本综合精品| 亚洲欧洲三级电影| 欧美激情亚洲视频| 欧美 日韩 国产精品免费观看| 欧美一区激情| 欧美一区二区三区四区夜夜大片 | 极品少妇一区二区三区精品视频| 国产精品xnxxcom| 欧美日韩精品一本二本三本| 麻豆精品在线视频| 六月丁香综合| 久久免费视频网| 久久久久综合网| 久久久噜噜噜久噜久久| 久久九九99视频| 久久精品一区蜜桃臀影院| 久久精品成人| 久久久久久久999精品视频| 久久久99久久精品女同性| 久久激情视频免费观看| 久久国产精品网站| 久久久国产精品亚洲一区 | 欧美一区二区三区四区视频| 欧美激情在线有限公司| 久久狠狠婷婷| 一区二区三区久久| 亚洲免费成人av| 99国产精品| 亚洲一区二区久久| 西瓜成人精品人成网站| 午夜精品久久久99热福利| 午夜精品视频| 久久九九99| 欧美国产精品中文字幕| 欧美日韩国产成人在线91| 欧美亚洲成人网| 国产视频在线观看一区二区三区| 国产亚洲福利| 亚洲日本成人在线观看| 亚洲网站在线观看| 久久激情视频久久| 欧美不卡三区| 9色国产精品| 久久精品国产77777蜜臀| 久久一区中文字幕| 欧美日本在线视频| 国产乱码精品一区二区三区不卡| 国内精品免费午夜毛片| 亚洲激情女人| 午夜久久久久| 欧美国产精品va在线观看| 亚洲人精品午夜| 午夜伦欧美伦电影理论片| 久久天堂av综合合色| 欧美日韩精品中文字幕| 亚洲大胆美女视频| 亚洲一区二区三区在线视频| 久久亚洲欧美| 国产精品嫩草久久久久| 亚洲国内在线| 午夜亚洲性色视频| 亚洲高清视频一区二区| 亚洲免费在线视频一区 二区| 久久精品在线观看| 国产精品二区三区四区| 亚洲电影有码| 久久精品国产清高在天天线| 亚洲日本欧美日韩高观看| 久久狠狠婷婷| 国产精品日韩在线观看| 999亚洲国产精| 美女主播一区| 亚洲欧美日韩精品久久奇米色影视| 免费欧美网站| 黑人一区二区| 欧美主播一区二区三区| 99国内精品久久|