天天看点
返回

【数据结构与算法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 之决策树及其案例

继续阅读