天天看點
傳回

【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作

1、定義

二叉樹的建構過程中，若元素的插入先後順序不同，則會影響二叉樹最終的結構，是以引入在key插入時一直保持平衡的二叉查找樹： AVL樹。AVL是發明者的名字縮寫： G.M. AdelsonVelskii and E.M. Landis。利用AVL樹實作ADT Map， 基本上與BST的實作相同，不同之處僅在于二叉樹的生成與維護過程

  • AVL樹的實作中， 需要對每個節點跟蹤“平衡因子balance factor”參數

  • 平衡因子是根據節點的左右子樹的高度來定義的， 确切地說， 是左右子樹高度差： balanceFactor =

    height(leftSubTree) -height(rightSubTree)

  • 如果平衡因子大于0，稱為“左重left-heavy”，小于零稱為“右重right-heavy”，平衡因子等于0，則稱作平衡。

如果一個二叉查找樹中每個節點的平衡因子都在-1， 0， 1之間， 則把這個二叉搜尋樹稱為平衡樹

【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作

2、功能分析

在平衡樹操作過程中， 有節點的平衡因子超出此範圍， 則需要一個重新平衡的過程，要保持BST的性質！

【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作

既然AVL平衡樹确實能夠改進BST樹的性能， 避免退化情形，我們來看看向AVL樹插入一個新key， 如

何才能保持AVL樹的平衡性質，首先， 作為BST， 新key必定以葉節點形式插入到AVL樹中

  • ❖葉節點的平衡因子是0， 其本身無需重新平衡
  • ❖但會影響其父節點的平衡因子： 作為左子節點插入，則父節點平衡因子會增加1； 作為右子節點插入，則父節點平衡因子會減少1。
【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作

這種影響可能随着其父節點到根節點的路徑一直傳遞上去， 直到：

  • 傳遞到根節點為止；
  • 或者某個父節點平衡因子被調整到0，不再影響上層節點的平衡因子為止。
    【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作
    重新定義_put方法即可 
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)

UpdateBalance方法

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)

rebalance重新平衡

主要手段 ：将不平衡的子樹進行旋轉rotation

視**“左重”或者“右重”進行不同方向的旋轉同時更新相關父節點引用，更新旋轉後被影響節點的平衡因子**

下圖是一個**“右重”子樹**A的左旋轉（并保持BST性質），将右子節點B提升為子樹的根，将舊根節點A作為新根節點B的左子節點，如果新根節點B原來有左子節點，則将此節點設定為A的右子節點（A的右子節點一定有空）

【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作

更複雜一些的情況：如圖的“左重”子樹右旋轉

旋轉後，新根節點将舊根節點作為右子節點，但是新根節點原來已有右子節點，需要将原有的右子節點重新定位！

原有的右子節點D改到舊根節點E的左子節點

同樣， E的左子節點在旋轉後一定有空

【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作
def rebalance(self,node):
    if node.balanceFactor < 0:
        if node.rightChild.balanceFactor > 0:
            # Do an LR Rotation
            self.rotateRight(node.rightChild)
            self.rotateLeft(node)
        else:
            # single left
            self.rotateLeft(node)
    elif node.balanceFactor > 0:
        if node.leftChild.balanceFactor < 0:
            # Do an RL Rotation
            self.rotateLeft(node.leftChild)
            self.rotateRight(node)
        else:
            # single right
            self.rotateRight(node)

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)


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

3、代碼實作 

class AVLTree(BinarySearchTree):
    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)

    def rebalance(self,node):
        if node.balanceFactor < 0:
            if node.rightChild.balanceFactor > 0:
                # Do an LR Rotation
                self.rotateRight(node.rightChild)
                self.rotateLeft(node)
            else:
                # single left
                self.rotateLeft(node)
        elif node.balanceFactor > 0:
            if node.leftChild.balanceFactor < 0:
                # Do an RL Rotation
                self.rotateLeft(node.leftChild)
                self.rotateRight(node)
            else:
                # single right
                self.rotateRight(node)

    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)


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

4、算法分析

AVL樹最差情形下的性能：即平衡因子為1或者-1，下圖列出平衡因子為1的“左重”AVL樹，樹的高度從1開始，問題規模（總節點數N）和比對次數（樹的高度h）之間的關系為：最多搜尋次數h和規模N的關系， 可以說AVL樹的搜尋時間複雜度為O(log n)

【資料結構與算法python】平衡二叉查找樹（AVL樹）的實作
資料結構與算法 二叉樹 平衡二叉樹 Python AVL
上一篇: 資料結構與算法-基礎（十）平衡二叉搜尋樹
下一篇: SparkMlib 之決策樹及其案例

繼續閱讀