日本久久久久久久久久,国产成人无码精品久久久免费,久久国产精品久久久

十三、左偏樹（Leftist Tree）

樹這個(gè)數(shù)據(jù)結(jié)構(gòu)內(nèi)容真的很多，上一節(jié)所講的二叉堆，其實(shí)就是一顆二叉樹，這次講的左偏樹（又叫“左翼堆”），也是樹。

二叉堆是個(gè)很不錯(cuò)的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樗浅１阌诶斫猓覂H僅用了一個(gè)數(shù)組，不會(huì)造成額外空間的浪費(fèi)，但它有個(gè)缺點(diǎn)，那就是很難合并兩個(gè)二叉堆，對(duì)于“合并”，“拆分”這種操作，我覺得最方面的還是依靠指針，改變一下指針的值就可以實(shí)現(xiàn)，要是涉及到元素的移動(dòng)，那就復(fù)雜一些了。

左偏樹跟二叉堆比起來，就是一棵真正意義上的樹了，具有左右指針，所以空間開銷上稍微大一點(diǎn)，但卻帶來了便于合并的便利。BTW：寫了很多很多的程序之后，我發(fā)覺“空間換時(shí)間”始終是個(gè)應(yīng)該考慮的編程方法。:)

左偏左偏，給人感覺就是左子樹的比重比較大了，事實(shí)上也差不多，可以這么理解：左邊分量重，那一直往右，就一定能最快地找到可以插入元素的節(jié)點(diǎn)了。所以可以這樣下個(gè)定義：左偏樹就是對(duì)其任意子樹而言，往右到插入點(diǎn)的距離（下面簡(jiǎn)稱為“距離”）始終小于等于往左到插入點(diǎn)的距離，當(dāng)然了，和二叉堆一樣，父節(jié)點(diǎn)的值要小于左右子節(jié)點(diǎn)的值。

如果節(jié)點(diǎn)本身不滿，可插入，那距離就為0，再把空節(jié)點(diǎn)的距離記為-1，這樣我們就得出：父節(jié)點(diǎn)的距離 = 右子節(jié)點(diǎn)距離 + 1，因?yàn)橛易庸?jié)點(diǎn)的距離始終是小于等于左子節(jié)點(diǎn)距離的。我把距離的值用藍(lán)色字體標(biāo)在上圖中了。

左偏樹并一定平衡，甚至它可以很不平衡，因?yàn)樗鋵?shí)也不需要平衡，它只需要像二叉堆那樣的功能，再加上合并方便，現(xiàn)在來看左偏樹的合并算法，如圖：

這種算法其實(shí)很適合用遞歸來做，但我還是用了一個(gè)循環(huán)，其實(shí)也差不多。對(duì)于左偏樹來說，這個(gè)合并操作是最重要最基本的了。為什么？你看哦：Enqueue，我能不能看作是這個(gè)左偏樹的root和一個(gè)單節(jié)點(diǎn)樹的合并？而Dequeue，我能不能看作是把root節(jié)點(diǎn)取出來，然后合并root的左右子樹？事實(shí)上就是這樣的，我提供的代碼就是這樣干的。

Conclusion：左偏樹比同二叉堆的優(yōu)點(diǎn)就是方便合并，缺點(diǎn)是編程復(fù)雜度略高（也高不去哪），占用空間稍大（其實(shí)也大不去哪）。附上代碼，老樣子了，單個(gè)文件，直接調(diào)試的代碼，零依賴零配置，一看就懂，代碼雖然不算完美，但作為演示和學(xué)習(xí)，是足夠了。

#include <stdio.h>

// TreeNode
//////////////////////////////////////////////////////////////////////////
struct TreeNode
{
    TreeNode(int iVal)
    {
        m_iData = iVal;
        m_iDistance = 0;
        m_pLeft = 0;
        m_pRight = 0;
    }

    ~TreeNode()
    {

    }

    void SwapLeftRight()
    {
        TreeNode *pTmp = m_pLeft;
        m_pLeft = m_pRight;
        m_pRight = pTmp;
    }

    void UpdateDistance()
    {
        m_iDistance = GetRightDistance()+1;
    }

    int GetLeftDistance()
    {
        return m_pLeft!=0?m_pLeft->m_iDistance:-1;
    }

    int GetRightDistance()
    {
        return m_pRight!=0?m_pRight->m_iDistance:-1;
    }

    int m_iData;
    int m_iDistance;
    TreeNode* m_pLeft;
    TreeNode* m_pRight;
};

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

// LeftistTree
//////////////////////////////////////////////////////////////////////////
class LeftistTree
{
public:
    LeftistTree();
    ~LeftistTree();

    //return 0 means failed.
    int Dequeue(int& iVal);
    int Enqueue(int iVal);

    //returns the merged root.
    TreeNode* Merge(TreeNode *pT1, TreeNode *pT2);

    TreeNode* GetRoot();
#ifdef _DEBUG
    void Print(TreeNode* pNode);
#endif

protected:
    TreeNode *m_pRoot;
};

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

LeftistTree::~LeftistTree()
{
    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->m_pLeft!=0)
        {
            st.Push(pNode);
            pTemp = pNode;
            pNode = pNode->m_pLeft;
            pTemp->m_pLeft = 0;
            continue;
        }

        if(pNode->m_pRight!=0)
        {
            st.Push(pNode);
            pTemp = pNode;
            pNode = pNode->m_pRight;
            pTemp->m_pRight = 0;
            continue;
        }

        delete pNode;

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

int LeftistTree::Dequeue(int& iVal)
{
    if(m_pRoot==0)
        return 0;

    iVal = m_pRoot->m_iData;
    TreeNode *pTmp = m_pRoot;
    m_pRoot = Merge(m_pRoot->m_pLeft, m_pRoot->m_pRight);
    delete pTmp;
    return 1;
}

int LeftistTree::Enqueue(int iVal)
{
    TreeNode *pNew = new TreeNode(iVal);
    m_pRoot = Merge(m_pRoot, pNew);
    return 1;
}

TreeNode* LeftistTree::Merge(TreeNode *pT1, TreeNode *pT2)
{
    if(pT1==0 && pT2==0)
        return 0;
    else if(pT1==0) //pT2!=0
        return pT2;
    else if(pT2==0) //pT1!=0
        return pT1;

    if(pT1->m_iData > pT2->m_iData)
        return Merge(pT2, pT1);

    Stack st(40);

    TreeNode* pInsPos = pT1;
    TreeNode* pToIns = pT2;
    TreeNode* pTmp;

    st.Push(pInsPos);

    //Find a node available for insert.
    while(1)
    {
        if(pInsPos->m_pRight!=NULL)
        {
            if(pToIns->m_iData < pInsPos->m_pRight->m_iData)
            {
                pTmp = pInsPos->m_pRight;
                pInsPos->m_pRight = pToIns;
                pToIns = pTmp;
                st.Push(pInsPos);
                pInsPos = pInsPos->m_pRight;
            }
            else
            {
                st.Push(pInsPos);
                pInsPos = pInsPos->m_pRight;
            }
        }
        else
        {
            st.Push(pInsPos);
            //Insert

            pInsPos->m_pRight = pToIns;
            break;
        }
    }

    TreeNode* pNode;
    //Try to update the relative distance and make the tree be still the leftist tree.
    while (0!=st.Pop(pNode))
    {
        if(pNode->GetLeftDistance() < pNode->GetRightDistance())
            pNode->SwapLeftRight();
        pNode->UpdateDistance();
    }

    return pT1;
}

TreeNode* LeftistTree::GetRoot()
{
    return m_pRoot;
}

#ifdef _DEBUG
void LeftistTree::Print(TreeNode* pNode)
{
    if(pNode!=NULL)
    {
        if(pNode->m_pLeft!=NULL && pNode->m_pRight!=NULL)
        {
            printf("%d[%d]->(%d, %d)\n", pNode->m_iData, pNode->m_iDistance, pNode->m_pLeft->m_iData, pNode->m_pRight->m_iData);
            Print(pNode->m_pLeft);
            Print(pNode->m_pRight);
        }
        else if(pNode->m_pLeft!=NULL)
        {
            printf("%d[%d]->(%d, x)\n", pNode->m_iData, pNode->m_iDistance, pNode->m_pLeft->m_iData);
            Print(pNode->m_pLeft);
        }
        else if(pNode->m_pRight!=NULL)
        {
            printf("%d[%d]->(x, %d)\n", pNode->m_iData, pNode->m_iDistance, pNode->m_pRight->m_iData);
            Print(pNode->m_pRight);
        }
    }
}
#endif

int main(int argc, char* argv[])
{
    LeftistTree tree;
    tree.Enqueue(9);
    tree.Enqueue(4);
    tree.Enqueue(2);
    tree.Enqueue(1);
    tree.Enqueue(3);
    tree.Enqueue(8);

#ifdef _DEBUG
    tree.Print(tree.GetRoot());
#endif

    int iVal;
    tree.Dequeue(iVal);
    printf("\nDequeue value is %d\n", iVal);
    tree.Dequeue(iVal);
    printf("Dequeue value is %d\n", iVal);

#ifdef _DEBUG
    tree.Print(tree.GetRoot());
#endif

    return 0;
}

也許你還想問：怎么你寫的代碼都不加個(gè)頭啊，用來聲明版權(quán)什么的。本人似乎沒這個(gè)習(xí)慣，那些東西繁瑣得很，而且根據(jù)我多年開發(fā)經(jīng)驗(yàn)，給每個(gè)cpp文件加個(gè)頭其實(shí)是沒有必要的，就好像注釋，不需要的時(shí)候也生硬加上，那就是畫蛇添足了。

（未完待續(xù)）

posted on 2009-10-30 15:55 Jiang Guogang 閱讀(1621) 評(píng)論(1) 編輯收藏引用所屬分類: Knowledge

評(píng)論

# re: 圖解數(shù)據(jù)結(jié)構(gòu)（9）——左偏樹 2010-04-25 11:43 ccsu_010

必須頂~ 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 用VS2010發(fā)布ASP.net網(wǎng)站 C#實(shí)現(xiàn)類似C++功能的困惑讓wprintf正常打印漢字根據(jù)下標(biāo)數(shù)組重調(diào)位置發(fā)現(xiàn)MSDN離線文檔的第一個(gè)錯(cuò)別字保存QQ空間的網(wǎng)頁至本地一個(gè)"滾動(dòng)數(shù)組"類模板怪異的有符號(hào)/無符號(hào)轉(zhuǎn)換問題 VSS使用手記一些可能你不知道的printf的參數(shù)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Jiang's C++ Space

公告

留言簿(16)

隨筆分類

隨筆檔案

最新隨筆

最新評(píng)論

評(píng)論