国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Python數(shù)據(jù)結(jié)構(gòu)——AVL樹的實現(xiàn)

Pink / 1387人閱讀

摘要:一旦子樹平衡因子為零,那么父節(jié)點的平衡因子不會發(fā)生改變。新根的父節(jié)點將成為舊根的父節(jié)點。因為其他操作都是移動整個子樹,被移動的子樹內(nèi)的節(jié)點的平衡因子不受旋轉(zhuǎn)的影響。讓表示以為根節(jié)點的子樹的高度。

既然,我們已經(jīng)證明,保持 AVL 樹的平衡將會使性能得到很大的提升,那我們看看如何在程序中向樹插入一個新的鍵值。因為所有的新鍵是作為葉節(jié)點插入樹的,而新葉子的平衡因子為零,所以我們對新插入的節(jié)點不作調(diào)整。不過一旦有新葉子的插入我們必須更新其父節(jié)點的平衡因子。新葉子會如何影響父節(jié)點的平衡因子取決于葉節(jié)點是左子節(jié)點還是右子節(jié)點。如果新節(jié)點是右子節(jié)點,父節(jié)點的平衡因子減 1。如果新節(jié)點是左子節(jié)點,父節(jié)點的平衡因子將加 1。這種關(guān)系可以遞歸地應(yīng)用于新節(jié)點的前兩個節(jié)點,并有可能影響到之前的每一個甚至是根節(jié)點。由于這是一個遞歸的過程,我們看看更新平衡因子的兩個基本條件:

遞歸調(diào)用已到達樹的根。

父節(jié)點的平衡因子已調(diào)整為零。一旦子樹平衡因子為零,那么父節(jié)點的平衡因子不會發(fā)生改變。

我們將實現(xiàn) AVL 樹的子類BinarySearchTree。首先,我們將重寫_put方法,并寫一個新的輔助方法updateBalance。這些方法如Listing 1 所示。除了第 7 行和第 13 行對 updateBalance的調(diào)用,你會注意到_put和簡單的二叉搜索樹的定義完全相同。

Listing 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
        else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode)
                self.updateBalance(currentNode.leftChild)
    else:
        if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
        else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode)
                self.updateBalance(currentNode.rightChild)

def updateBalance(self,node):
    if node.balanceFactor > 1 or node.balanceFactor < -1:
        self.rebalance(node)
        return
    if node.parent != None:
        if node.isLeftChild():
                node.parent.balanceFactor += 1
        elif node.isRightChild():
                node.parent.balanceFactor -= 1

        if node.parent.balanceFactor != 0:
                self.updateBalance(node.parent)

updateBalance方法完成了大部分功能,實現(xiàn)了我們剛提到的遞歸過程。這個再平衡方法首先檢查當前節(jié)點是否完全不平衡,以至于需要重新平衡(第 16 行)。如果當前節(jié)點需要再平衡,那么只需要對當前節(jié)點進行再平衡,而不需要進一步更新父節(jié)點。如果當前節(jié)點不需要再平衡,那么父節(jié)點的平衡因子就需要調(diào)整。如果父節(jié)點的平衡因子不為零, 算法通過父節(jié)點遞歸調(diào)用updateBalance方法繼續(xù)遞歸到樹的根。

當對一棵樹進行再平衡是必要的,我們該怎么做呢?高效的再平衡是使 AVL 樹能夠很好地執(zhí)行而不犧牲性能的關(guān)鍵。為了讓 AVL 樹恢復(fù)平衡,我們會在樹上執(zhí)行一個或多個“旋轉(zhuǎn)”
(rotation)。

為了了解什么是旋轉(zhuǎn),讓我們看一個很簡單的例子。思考一下圖 3 的左邊的樹。這棵樹是不平衡的,平衡因子為 -2。為了讓這棵樹平衡我們將根的子樹節(jié)點 A 進行左旋轉(zhuǎn)。

圖 3:使用左旋轉(zhuǎn)變換不平衡樹

執(zhí)行左旋轉(zhuǎn)我們需要做到以下幾點:

使右節(jié)點(B)成為子樹的根。

移動舊的根節(jié)點(A)到新根的左節(jié)點。

如果新根(B)原來有左節(jié)點,那么讓原來B的左節(jié)點成為新根左節(jié)點(A)的右節(jié)點。

注:由于新根(B)是 A 的右節(jié)點,在這種情況下,移動后的 A 的右節(jié)點一定是空的。我們不用多想就可以給移動后的 A 直接添加右節(jié)點。

雖然這個過程概念上看起來簡單,但實現(xiàn)時的細節(jié)有點棘手,因為要保持二叉搜索樹的所有性質(zhì),必須以絕對正確的順序把節(jié)點移來移去。此外,我們需要確保更新了所有的父節(jié)點。
讓我們看一個稍微復(fù)雜的樹來說明右旋轉(zhuǎn)。圖 4 的左側(cè)展現(xiàn)了一棵“左重”的樹,根的平衡因子為 2。執(zhí)行一個正確的右旋轉(zhuǎn),我們需要做到以下幾點:

使左節(jié)點(C)成為子樹的根。

移動舊根(E)到新根的右節(jié)點。

如果新根(C)原來有右節(jié)點(D),那么讓 D 成為新根右節(jié)點(E)的左節(jié)點。

注:由于新根(C)是 E 的左節(jié)點,移動后的 E 的左節(jié)點一定為空。這時可以直接給移動后的 E 添加左節(jié)點。

圖 4:使用右旋轉(zhuǎn)變換不平衡樹

現(xiàn)在你已經(jīng)明白了旋轉(zhuǎn)的過程,了解了旋轉(zhuǎn)的方法,讓我們看看代碼。Listing 2 同時顯示了右旋轉(zhuǎn)和左旋轉(zhuǎn)的代碼。在第 2 行,我們創(chuàng)建一個臨時變量來跟蹤新的子樹的根。正如我們之前所說的新的根是舊根的右節(jié)點。現(xiàn)在,右節(jié)點已經(jīng)存儲在這個臨時變量中。我們將舊根的右節(jié)點替換為新根的左節(jié)點。

下一步是調(diào)整兩個節(jié)點的父指針。如果newRoot原來有左節(jié)點,左節(jié)點的新父節(jié)點變成舊根。新根的父節(jié)點將成為舊根的父節(jié)點。如果舊根是整個樹的根,那么我們必須讓整棵樹的根指向這個新的根。如果舊根是左節(jié)點,那么我們改變左節(jié)點的父節(jié)點到一個新的根;否則,我們改變右節(jié)點的父節(jié)點到一個新的根(第 10-13 行)。最后我們設(shè)置的舊根的父節(jié)點成為新的根。這里有很多復(fù)雜的中間過程,所以建議你一邊看函數(shù)的代碼,一邊看圖 3。rotateRight方法和rotateLeft是對稱的,所以請自行研究rotateRight的代碼。

Listing 2

def rotateLeft(self,rotRoot):
    newRoot = rotRoot.rightChild
    rotRoot.rightChild = newRoot.leftChild
    if newRoot.leftChild != None:
        newRoot.leftChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
        self.root = newRoot
    else:
        if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
        else:
            rotRoot.parent.rightChild = newRoot
    newRoot.leftChild = rotRoot
    rotRoot.parent = newRoot
    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

最后,第 16-17 行需要解釋一下。這兩行我們更新了舊根和新根的平衡因子。因為其他操作都是移動整個子樹,被移動的子樹內(nèi)的節(jié)點的平衡因子不受旋轉(zhuǎn)的影響。但我們?nèi)绾卧跊]有重新計算新的子樹的高度的情況下更新平衡因子?下面的推導(dǎo)將讓你明白,這些代碼都是正確的。

圖 5:左旋轉(zhuǎn)

圖5顯示了一個左旋轉(zhuǎn)。B 和 D 是中心節(jié)點,A,C,E 是其子樹。讓 hX 表示以X為根節(jié)點的子樹的高度。通過定義我們知道:

$$newBal(B) = h_A - h_C
oldBal(B) = h_A - h_D$$

但我們知道,D 的高度也可以通過 1 + max(hC,hE) 給定,也就是說,D 的高度為兩子樹高度中較大者加 1。記住,hC 和 hE 沒有改變。所以,把上式代入第二個方程,可以得到:

$$oldBal(B) = h_A - (1 + max(h_C,h_E))$$

然后兩方程作差。下面是作差的步驟,newBal(B) 使用了一些代數(shù)方法簡化方程。

$$begin{split}newBal(B) - oldBal(B) = h_A - h_C - (h_A - (1 + max(h_C,h_E)))
newBal(B) - oldBal(B) = h_A - h_C - h_A + (1 + max(h_C,h_E))
newBal(B) - oldBal(B) = h_A - h_A + 1 + max(h_C,h_E) - h_C
newBal(B) - oldBal(B) = 1 + max(h_C,h_E) - h_C$$

接下來我們移動 oldBal(B) 到方程的右端并利用 max(a,b)?c = max(a?c,b?c)。

$$newBal(B) = oldBal(B) + 1 + max(h_C - h_C ,h_E - h_C)$$

但 hE ? hC 等同于 ?oldBal(D)。所以我們說:max(?a,?b) = ?min(a,b),可以通過以下步驟完成對 newBal(B) 的推導(dǎo):

$$newBal(B) = oldBal(B) + 1 + max(0 , -oldBal(D))
newBal(B) = oldBal(B) + 1 - min(0 , oldBal(D))$$

現(xiàn)在方程所有的項都是已知數(shù)。如果我們記得 B 是rotRoot,D 是newRoot,可以看出這正好符合第 16 行的語句:

rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(0,newRoot.balanceFactor)

更新節(jié)點 D,以及右旋轉(zhuǎn)后的平衡因子的方程推導(dǎo)與此類似。
現(xiàn)在你可能認為步驟都完全了解了。我們知道如何并且什么時候進行左右旋轉(zhuǎn),但看看圖 6。由于節(jié)點 A 的平衡因子是 -2,我們應(yīng)該做一個左旋轉(zhuǎn)。但是,當我們在左旋轉(zhuǎn)時會發(fā)生什么?

圖 6:一棵更難平衡的不平衡樹

圖 7:顯示的樹左旋轉(zhuǎn)后,仍然不平衡。如果我們要做一個右旋轉(zhuǎn)來試圖再平衡,又回到了開始的狀態(tài)。

要解決這個問題,我們必須使用以下規(guī)則:

如果子樹需要左旋轉(zhuǎn)使之平衡,首先檢查右節(jié)點的平衡因子。如果右節(jié)點左重則右節(jié)點右旋轉(zhuǎn),然后原節(jié)點左旋轉(zhuǎn)。

如果子樹需要右旋轉(zhuǎn)使之平衡,首先檢查左節(jié)點的平衡因子。如果左節(jié)點右重則左節(jié)點左旋轉(zhuǎn),然后原節(jié)點右旋轉(zhuǎn)。

圖 8 顯示了這些規(guī)則如何解決了我們在圖 6 和圖 7 中遇到的問題。首先,以 C 為中心右旋轉(zhuǎn),樹變成一個較好的形狀;然后,以 A 為中心左旋轉(zhuǎn),整個子樹恢復(fù)平衡。

圖 8:右旋轉(zhuǎn)后左旋轉(zhuǎn)

實現(xiàn)這些規(guī)則的代碼可以從我們“再平衡”(rebalance)的方法中找到,如Listing 3 所示。上面的第一條規(guī)則從第二行if語句中實現(xiàn)。第二條規(guī)則是由第 8 行elif語句實現(xiàn)。

Listing 3

def rebalance(self,node):
  if node.balanceFactor < 0:
         if node.rightChild.balanceFactor > 0:
            self.rotateRight(node.rightChild)
            self.rotateLeft(node)
         else:
            self.rotateLeft(node)
  elif node.balanceFactor > 0:
         if node.leftChild.balanceFactor < 0:
            self.rotateLeft(node.leftChild)
            self.rotateRight(node)
         else:
            self.rotateRight(node)

通過保持樹的平衡,我們可以確保get方法運行的時間復(fù)雜度為 O(log2n)。但問題是put方法的時間復(fù)雜度是多少?我們把put操作進行分解。由于每一個新節(jié)點都是作為葉節(jié)點插入的,每一輪更新所有父節(jié)點的平衡因子最多只需要 log2n 次操作,每層執(zhí)行一次。如果子樹是不平衡的最多需要兩個旋轉(zhuǎn)把子樹恢復(fù)平衡。但是,每個旋轉(zhuǎn)的操作的復(fù)雜度為 O(1) ,所以即使我們進行put操作最終的復(fù)雜度仍然是 O(log2n)。

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/45516.html

相關(guān)文章

  • Python數(shù)據(jù)結(jié)構(gòu)——AVL樹的基本概念

    摘要:我們知道,當樹變得不平衡時和操作會使二叉搜索樹的性能降低到。樹實現(xiàn)抽象數(shù)據(jù)類型就像一個普通的二叉搜索樹,唯一不同的是這棵樹的工作方式。我們通過比較每個節(jié)點的左右子樹的高度完成比較。 平衡二叉搜索樹 在上一節(jié)中我們討論了建立一個二叉搜索樹。我們知道,當樹變得不平衡時get和put操作會使二叉搜索樹的性能降低到O(n)。在這一節(jié)中我們將看到一種特殊的二叉搜索樹,它可以自動進行調(diào)整,以確保樹...

    jiekechoo 評論0 收藏0
  • 學習JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — AVL

    摘要:可以看到,一次左單旋將右側(cè)子樹的高度減小了,而左側(cè)子樹的高度增加了。如圖,對進行右單旋,需要左子樹的右子樹的高度小于等于左子樹的高度,否則不能達到平衡的效果,只是把不平衡性從左邊轉(zhuǎn)移到了右邊。 AVL樹 普通二叉搜索樹可能出現(xiàn)一條分支有多層,而其他分支卻只有幾層的情況,如圖1所示,這會導(dǎo)致添加、移除和搜索樹具有性能問題。因此提出了自平衡二叉樹的概念,AVL樹(阿德爾森-維爾斯和蘭迪斯樹...

    impig33 評論0 收藏0
  • AVL樹的Java實現(xiàn)

    摘要:容忍不平衡紅黑樹的思路的核心是增大了可容忍的高度差,從而實現(xiàn)既保證查詢效率,也保證了插入和刪除后調(diào)整平衡的效率。紅黑樹的查詢效率是略低于樹的,但是紅黑樹通過犧牲了少許查詢效率,使插入刪除后的調(diào)整效率達到了常數(shù)級別。 定義 Wikipedia - AVL樹 在計算機科學中,AVL樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中,任一節(jié)點對應(yīng)的兩棵子樹的最大高度差為1,因此它也被稱為高度平衡...

    leejan97 評論0 收藏0
  • JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(十)自平衡樹

    摘要:為了解決這類問題,我們進行自平衡樹的學習。自平衡樹常見有兩種樹和紅黑樹。自平衡樹準備知識節(jié)點的高度和平衡因子節(jié)點高度從節(jié)點到任意子節(jié)點的彼岸的最大值。 前面介紹了二叉樹和二叉樹搜索樹的創(chuàng)建和使用,接下來我們繼續(xù)學習關(guān)于樹的更多知識。BST存在一個問題,就是當我們多次添加節(jié)點數(shù),有可能造成一種情況,樹的一條邊可能會非常深,有非常多的層,而另一條分支卻只有幾層。當我們需要進行添加、移除和搜...

    msup 評論0 收藏0
  • 一文掌握關(guān)于Java數(shù)據(jù)結(jié)構(gòu)所有知識點(歡迎一起完善)

    摘要:是棧,它繼承于。滿二叉樹除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。沒有鍵值相等的節(jié)點。這是數(shù)據(jù)庫選用樹的最主要原因。 在我們學習Java的時候,很多人會面臨我不知道繼續(xù)學什么或者面試會問什么的尷尬情況(我本人之前就很迷茫)。所以,我決定通過這個開源平臺來幫助一些有需要的人,通過下面的內(nèi)容,你會掌握系統(tǒng)的Java學習以及面試的相關(guān)知識。本來是想通過Gitbook的...

    keithxiaoy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<