有声读物,盗墓笔记txt全集下载

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案

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

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

創(chuàng)新互聯(lián)企業(yè)建站,10多年網(wǎng)站建設(shè)經(jīng)驗(yàn)，專注于網(wǎng)站建設(shè)技術(shù)，精于網(wǎng)頁(yè)設(shè)計(jì)，有多年建站和網(wǎng)站代運(yùn)營(yíng)經(jīng)驗(yàn)，設(shè)計(jì)師為客戶打造網(wǎng)絡(luò)企業(yè)風(fēng)格，提供周到的建站售前咨詢和貼心的售后服務(wù)。對(duì)于成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)中不同領(lǐng)域進(jìn)行深入了解和探索，創(chuàng)新互聯(lián)在網(wǎng)站建設(shè)中充分了解客戶行業(yè)的需求，以靈動(dòng)的思維在網(wǎng)頁(yè)中充分展現(xiàn)，通過(guò)對(duì)客戶行業(yè)精準(zhǔn)市場(chǎng)調(diào)研，為客戶提供的解決方案。

遞歸調(diào)用已到達(dá)樹(shù)的根。
父節(jié)點(diǎn)的平衡因子已調(diào)整為零。一旦子樹(shù)平衡因子為零，那么父節(jié)點(diǎn)的平衡因子不會(huì)發(fā)生改變。

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

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方法完成了大部分功能，實(shí)現(xiàn)了我們剛提到的遞歸過(guò)程。這個(gè)再平衡方法首先檢查當(dāng)前節(jié)點(diǎn)是否完全不平衡，以至于需要重新平衡(第 16 行)。如果當(dāng)前節(jié)點(diǎn)需要再平衡，那么只需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡，而不需要進(jìn)一步更新父節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)不需要再平衡，那么父節(jié)點(diǎn)的平衡因子就需要調(diào)整。如果父節(jié)點(diǎn)的平衡因子不為零，算法通過(guò)父節(jié)點(diǎn)遞歸調(diào)用updateBalance方法繼續(xù)遞歸到樹(shù)的根。

當(dāng)對(duì)一棵樹(shù)進(jìn)行再平衡是必要的，我們?cè)撛趺醋瞿?高效的再平衡是使 AVL 樹(shù)能夠很好地執(zhí)行而不犧牲性能的關(guān)鍵。為了讓 AVL 樹(shù)恢復(fù)平衡，我們會(huì)在樹(shù)上執(zhí)行一個(gè)或多個(gè)“旋轉(zhuǎn)”(rotation)。

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

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

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

使右節(jié)點(diǎn)(B)成為子樹(shù)的根。
移動(dòng)舊的根節(jié)點(diǎn)(A)到新根的左節(jié)點(diǎn)。
如果新根(B)原來(lái)有左節(jié)點(diǎn)，那么讓原來(lái)B的左節(jié)點(diǎn)成為新根左節(jié)點(diǎn)(A)的右節(jié)點(diǎn)。

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

雖然這個(gè)過(guò)程概念上看起來(lái)簡(jiǎn)單，但實(shí)現(xiàn)時(shí)的細(xì)節(jié)有點(diǎn)棘手，因?yàn)橐３侄嫠阉鳂?shù)的所有性質(zhì)，必須以絕對(duì)正確的順序把節(jié)點(diǎn)移來(lái)移去。此外，我們需要確保更新了所有的父節(jié)點(diǎn)。讓我們看一個(gè)稍微復(fù)雜的樹(shù)來(lái)說(shuō)明右旋轉(zhuǎn)。圖 4 的左側(cè)展現(xiàn)了一棵“左重”的樹(shù)，根的平衡因子為 2。執(zhí)行一個(gè)正確的右旋轉(zhuǎn)，我們需要做到以下幾點(diǎn)：

使左節(jié)點(diǎn)(C)成為子樹(shù)的根。
移動(dòng)舊根(E)到新根的右節(jié)點(diǎn)。
如果新根(C)原來(lái)有右節(jié)點(diǎn)(D)，那么讓 D 成為新根右節(jié)點(diǎn)(E)的左節(jié)點(diǎn)。

注：由于新根(C)是 E 的左節(jié)點(diǎn)，移動(dòng)后的 E 的左節(jié)點(diǎn)一定為空。這時(shí)可以直接給移動(dòng)后的 E 添加左節(jié)點(diǎn)。

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

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

下一步是調(diào)整兩個(gè)節(jié)點(diǎn)的父指針。如果newRoot原來(lái)有左節(jié)點(diǎn)，左節(jié)點(diǎn)的新父節(jié)點(diǎn)變成舊根。新根的父節(jié)點(diǎn)將成為舊根的父節(jié)點(diǎn)。如果舊根是整個(gè)樹(shù)的根，那么我們必須讓整棵樹(shù)的根指向這個(gè)新的根。如果舊根是左節(jié)點(diǎn)，那么我們改變左節(jié)點(diǎn)的父節(jié)點(diǎn)到一個(gè)新的根;否則，我們改變右節(jié)點(diǎn)的父節(jié)點(diǎn)到一個(gè)新的根(第 10-13 行)。最后我們?cè)O(shè)置的舊根的父節(jié)點(diǎn)成為新的根。這里有很多復(fù)雜的中間過(guò)程，所以建議你一邊看函數(shù)的代碼，一邊看圖 3。rotateRight方法和rotateLeft是對(duì)稱的，所以請(qǐng)自行研究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 行需要解釋一下。這兩行我們更新了舊根和新根的平衡因子。因?yàn)槠渌僮鞫际且苿?dòng)整個(gè)子樹(shù)，被移動(dòng)的子樹(shù)內(nèi)的節(jié)點(diǎn)的平衡因子不受旋轉(zhuǎn)的影響。但我們?nèi)绾卧跊](méi)有重新計(jì)算新的子樹(shù)的高度的情況下更新平衡因子?下面的推導(dǎo)將讓你明白，這些代碼都是正確的。

圖 5：左旋轉(zhuǎn)

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

newBal(B)=hA?hC

oldBal(B)=hA?hD

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

oldBal(B)=hA?(1+max(hC,hE))

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

beginsplitnewBal(B)?oldBal(B)=hA?hC?(hA?(1+max(hC,hE)))

newBal(B)?oldBal(B)=hA?hC?hA+(1+max(hC,hE))

newBal(B)?oldBal(B)=hA?hA+1+max(hC,hE)?hC

newBal(B)?oldBal(B)=1+max(hC,hE)?hC

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

newBal(B)=oldBal(B)+1+max(hC?hC,hE?hC)

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

newBal(B)=oldBal(B)+1+max(0,?oldBal(D))

newBal(B)=oldBal(B)+1?min(0,oldBal(D))

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

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

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

圖 6：一棵更難平衡的不平衡樹(shù)

圖 7：顯示的樹(shù)左旋轉(zhuǎn)后，仍然不平衡。如果我們要做一個(gè)右旋轉(zhuǎn)來(lái)試圖再平衡，又回到了開(kāi)始的狀態(tài)。

要解決這個(gè)問(wèn)題，我們必須使用以下規(guī)則：

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

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

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

實(shí)現(xiàn)這些規(guī)則的代碼可以從我們“再平衡”(rebalance)的方法中找到，如Listing 3 所示。上面的第一條規(guī)則從第二行if語(yǔ)句中實(shí)現(xiàn)。第二條規(guī)則是由第 8 行elif語(yǔ)句實(shí)現(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)

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

分享題目：Python數(shù)據(jù)結(jié)構(gòu)——AVL樹(shù)的實(shí)現(xiàn)
本文鏈接：http://www.fisionsoft.com.cn/article/coedgjj.html

新聞中心

其他資訊