建站
咨詢
售后
建站咨詢
新聞中心
既然，我們已經(jīng)證明，保持 AVL 樹的平衡將會使性能得到很大的提升，那我們看看如何在程序中向樹插入一個新的鍵值。因為所有的新鍵是作為葉節(jié)點插入樹的，而新葉子的平衡因子為零，所以我們對新插入的節(jié)點不作調(diào)整。不過一旦有新葉子的插入我們必須更新其父節(jié)點的平衡因子。新葉子會如何影響父節(jié)點的平衡因子取決于葉節(jié)點是左子節(jié)點還是右子節(jié)點。如果新節(jié)點是右子節(jié)點，父節(jié)點的平衡因子減 1。如果新節(jié)點是左子節(jié)點，父節(jié)點的平衡因子將加 1。這種關(guān)系可以遞歸地應用于新節(jié)點的前兩個節(jié)點，并有可能影響到之前的每一個甚至是根節(jié)點。由于這是一個遞歸的過程，我們看看更新平衡因子的兩個基本條件：
創(chuàng)新互聯(lián)企業(yè)建站,10多年網(wǎng)站建設經(jīng)驗，專注于網(wǎng)站建設技術(shù)，精于網(wǎng)頁設計，有多年建站和網(wǎng)站代運營經(jīng)驗，設計師為客戶打造網(wǎng)絡企業(yè)風格，提供周到的建站售前咨詢和貼心的售后服務。對于成都網(wǎng)站制作、成都網(wǎng)站建設、外貿(mào)營銷網(wǎng)站建設中不同領(lǐng)域進行深入了解和探索，創(chuàng)新互聯(lián)在網(wǎng)站建設中充分了解客戶行業(yè)的需求，以靈動的思維在網(wǎng)頁中充分展現(xiàn)，通過對客戶行業(yè)精準市場調(diào)研，為客戶提供的解決方案。
- 遞歸調(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 樹恢復平衡，我們會在樹上執(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é)點。讓我們看一個稍微復雜的樹來說明右旋轉(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 行)。最后我們設置的舊根的父節(jié)點成為新的根。這里有很多復雜的中間過程，所以建議你一邊看函數(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)绾卧跊]有重新計算新的子樹的高度的情況下更新平衡因子?下面的推導將讓你明白，這些代碼都是正確的。
圖 5：左旋轉(zhuǎn)
圖5顯示了一個左旋轉(zhuǎn)。B 和 D 是中心節(jié)點，A，C，E 是其子樹。讓 hX 表示以X為根節(jié)點的子樹的高度。通過定義我們知道：
newBal(B)=hA?hC
oldBal(B)=hA?hD
但我們知道，D 的高度也可以通過 1 + max(hC,hE) 給定，也就是說，D 的高度為兩子樹高度中較大者加 1。記住，hC 和 hE 沒有改變。所以，把上式代入第二個方程，可以得到：
oldBal(B)=hA?(1+max(hC,hE))
然后兩方程作差。下面是作差的步驟，newBal(B) 使用了一些代數(shù)方法簡化方程。
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
接下來我們移動 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)。所以我們說：max(?a,?b) = ?min(a,b)，可以通過以下步驟完成對 newBal(B) 的推導：
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)后的平衡因子的方程推導與此類似。現(xiàn)在你可能認為步驟都完全了解了。我們知道如何并且什么時候進行左右旋轉(zhuǎn)，但看看圖 6。由于節(jié)點 A 的平衡因子是 -2，我們應該做一個左旋轉(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)，整個子樹恢復平衡。
圖 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方法運行的時間復雜度為 O(log2n)。但問題是put方法的時間復雜度是多少?我們把put操作進行分解。由于每一個新節(jié)點都是作為葉節(jié)點插入的，每一輪更新所有父節(jié)點的平衡因子最多只需要 log2n 次操作，每層執(zhí)行一次。如果子樹是不平衡的最多需要兩個旋轉(zhuǎn)把子樹恢復平衡。但是，每個旋轉(zhuǎn)的操作的復雜度為 O(1) ，所以即使我們進行put操作最終的復雜度仍然是 O(log2n)。
分享題目：Python數(shù)據(jù)結(jié)構(gòu)——AVL樹的實現(xiàn)
文章轉(zhuǎn)載：http://www.dlmjj.cn/article/coedgjj.html
