6.平衡二叉查找树

平衡二叉查找树：

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之间，则把这个二叉搜索树称为平衡树

AVL树的性能

我们先看看限定平衡因子带来的结果。我们认为，保证树的平衡因子为–1、0 或 1，可以使关键操作获得更好的大O性能

image.png

观察上图h=1～4时，总节点数N的变化
h= 1, N= 1
h= 2, N= 2= 1+ 1
h= 3, N= 4= 1+ 1+ 2
h= 4, N= 7= 1+ 2+ 4

image.png

观察这个通式，很接近斐波那契数列
定义斐波那契数列
利用重写

image.png
斐波那契数列的性质：趋向于黄金分割
image.png
将
通式代入到中，得到的通式
image.png image.png

最多搜索次数h和规模N的关系，可以说AVL树的搜索时间复杂度为O(log n)

AVL树的实现

❖既然AVL平衡树确实能够改进BST树的性能，避免退化情形
❖我们来看看向AVL树插入一个新key，如何才能保持AVL树的平衡性质
❖首先，作为BST，新key必定以叶节点形式插入到AVL树中

叶节点的平衡因子是0，其本身无需重新平衡
但会影响其父节点的平衡因子：

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

这种影响可能随着其父节点到根节点的路径一直传递上去，直到传递到根节点为止；
或者某个父节点平衡因子被调整到0，不再影响上层节点的平衡因子为止。
• （无论从-1或者1调整到0，都不会改变子树高度）

image.png

重新定义_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.updataBlance(currentNode.leftChild)
    else:
        if currentNode.hasRightChild():
            self._put(key, val, currentNode.rightChild)
        else:
            currentNode.rightChild = TreeNode(key, val, parent = currentNode)
            self.updataBlance(currentNode.rightChild)

UpdateBalance方法

def updateBalance(self, node):
    if node.balanceFactor > 1 or node.balanceFactor < -1:
        self.rebalance(node)
    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视“左倾”或者“右倾”进行不同方向的旋转
同时更新相关父节点引用，更新旋转后被影响节点的平衡因子

image.png

如图，是一个“右倾”子树A的左旋转（并保持BST性质）将右子节点B提升为子树的根，将旧根节点A作为新根节点B的左子节点，如果新根节点B原来有左子节点，则将此节点设
置为A的右子节点（A的右子节点一定有空）
更复杂一些的情况：如图的“左倾”子树右旋转，旋转后，新根节点将旧根节点作为右子节点，但是新根节点原来已有右子节点，需要将原有的右子节点重新定位！原有的右子节点D改到旧根节点E的左子节点，同样，E的左子节点在旋转后一定有空

image.png

    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.blanceFactor + 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
        newRoot.rightChild = rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(
            newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(
            rotRoot.balanceFactor, 0)

如何调整平衡因子
看看左旋转对平衡因子的影响，保持了次序ABCDE，ACE的平衡因子不变，hA/hC/hE不变，主要看BD新旧关系

image.png
来看看B的变化，






更复杂的情形
下图的“右倾”子树，单纯的左旋转无法实现平衡
左旋转后变成“左倾”了，“左倾”再右旋转，还回到“右倾”
image.png
image.png
所以，在左旋转之前检查右子节点的因子，如果右子节点“左重”的话，先对它进行右旋转
再实施原来的左旋转，同样，在右旋转之前检查左子节点的因子，如果左子节点“右重”的话，先对它进行左旋转再实施原来的右旋转
image.png
rebalance代码

    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)

拓展 尝试计算树的高度
TreeNode类中添加高度方法

    def height(self):
        height_l = 0
        height_r = 0
        if self.isLeaf():
            return 0
        if self.leftChild:
            height_l = self.leftChild.height()
        if self.rightChild:
            height_r = self.rightChild.height()
        return max(height_l,height_r) + 1

经过复杂的put方法，AVL树始终维持平衡，get方法也始终保持O(log n)高性能
将AVL树的put方法分为两个部分：
需要插入的新节点是叶节点，更新其所有父节点和祖先节点的代价最多为O(log n)
如果插入的新节点引发了不平衡，重新平衡最多需要2次旋转，但旋转的代价与问题规模无关，是常数O(1)所以整个put方法的时间复杂度还是O(log n)