平衡二叉查找树AVL

1.AVL简介

这篇文章我们要介绍的是能够在key插入时一直保持平衡的二叉查找树(AVL树,AVL是发明者的名字缩写)

利用AVL实现ADT MAP,基本上与BST的实现相同。不同之处在于二叉树的生成与维护过程。

2.AVL中的概念

AVL树的实现中,需要对每个节点跟踪“平衡因子balance factor”参数。

平衡因子是根据节点的左右子树的高度来定义的。确切的来说,是左右子树的高度差。balanceFactor = height(leftSubTree) - height(rightSubTree)。

如果平衡因子大于0,称为“左重 left-heavy”,小于0,称为“右重right-heavy”,平衡因子等于0,则称作平衡。

如果一个二叉查找树中每个节点的平衡因子都在-1,0,1之间,则把这个二叉搜索树称为平衡树。

3.AVL树性能分析

分析AVL树最差情形下的性能,即平衡因子为1或者-1时

总结点数N 和比对次数(树的高度h)之间的关系。
h = 1,N = 1
h = 2,N = 2
h = 3,N = 4 = 1 + 1 +2
h = 4,N = 7 = 1 + 2 + 4
Nh = 1 + Nh-1 + Nh-2

h = 1.44logNh

可以说AVL树的搜索时间复杂度为O(logn)

4.AVL树的python实现

AVL平衡树确实能够改进BST树的性能,避免退化情形
我们来看看向AVL树插入一个新key,如何才能保持AVL树的平衡性质。

首先,作为BST,新key必定以叶节点形式插入到AVL树中。而叶节点的平衡因子始终是0,其本身无需重新平衡。但会影响父节点的平衡因子。

  • 作为左子节点插入,则父节点平衡因子会增加1
  • 作为右子节点插入,则父节点平衡因子会减少1

这种影响可能会随着其父节点到根节点的路径一直传递上去。直到:

  • 传递到根节点为止
  • 或者某个父节点平衡因子被调整到0,则不再影响上层节点的平衡因子。(无论是从-1到0还是1到0,子树的高度都没有发生改变)

重新定义_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)
            self.updateBalance(currenNode.leftChild)
    else:
        if currentNode.hasRightChild():
            self._put(key,val,currentNode.rightChild)
        else:
            currentNode.rightChild = TreeNode(key,val)
            self.updateBalance(currentNode.rightChild)
            
def updateBalance(self,node):
    if node.balanceFactor > 1 or node.balanceFactor < -1:
        self.reblance(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(self,node.parent)

# 主要手段:将不平衡的子树进行旋转rotation
def rebalance(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)

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)
    

5.小结

经过复杂的put方法,avl树始终维持平衡,get方法保持O(logn)高性能。

那么put方法的代价呢?

将put方法分成两个部分:

需要插入的新节点时叶节点,更新其所有父节点和祖先节点的代价最多为O(logn)。

如果插入的新节点引发了不平衡,重新平衡最多需要2次旋转,但旋转的代价与问题的规模无关,是常数O(1)。所以整个put方法的时间复杂度还是O(logn)。

上一篇:二叉树(五)平衡二叉树(AVL树)


下一篇:动画 | 什么是平衡二分搜索树(AVL)?