平衡二叉树(AVL树)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_36670529/article/details/103118546

通过之前对二叉搜索树介绍可知,将集合构造为二叉搜索树结构,该结构下对树中节点的查询、删除和插入三种操作,时间复杂度均为

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

定义

平衡二叉树也叫自平衡二叉搜索树(Self-Balancing Binary Search Tree),所以其本质也是一颗二叉搜索树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子,树中每个节点的平衡因子绝对值不大于1,此时二叉搜索树称之为平衡二叉树。自平衡是指,在对平衡二叉树执行插入或删除节点操作后,可能会导致树中某个节点的平衡因子绝对值超过1,即平衡二叉树变得“不平衡”,为了恢复该节点左右子树的平衡,此时需要对节点执行旋转操作。

情景分析

在执行插入或删除节点操作后,平衡因子绝对值变为大于1的情况,即左右子树的高度差为2或-2的情况,可以归纳为如下四种:

  • 左左情况(LL)

LL情况是指根节点的平衡因子为2,根节点的左子节点平衡因子为0或1。

LL_1

如图 LL_1 所示,当节点C的子节点被删除,或者节点D插入子节点F时,根节点A的平衡因子变为2,A的左子节点B的平衡因子为1。

LL_2

或者如图 LL_2 所示,当节点C的子节点被删除,根节点A的平衡因子变为2,A的左子节点B的平衡因子为0。。

当根节点的左子树高度比右子树的高度大2,因为平衡二叉树是一种有序结构,节点值之间具有大小关系,所以如果根节点保持不变,左右子树始终分隔两岸,则无论如何调整节点位置,二叉树始终不可能恢复平衡。所以需要更换根节点,使得新的根节点的左右子树的高度趋于平衡。

该情况下需要对平衡二叉树执行右旋操作:

  1. 设置根节点root的左子节点为新的根节点

节点的右子树作为root节点的左子树,将root节点作为

的右子树,即降低“左子树”高度,提升“右子树”高度,使得新的左右子树高度趋于平衡;

对于图 LL_1,节点B的平衡因子为1,设B节点的左子树D高度为h,则右子树E高度为h-1,因为A的平衡因子为2,所以二叉树C的高度为: h-1。则右旋操作后,B的左子树高度不变为h,右子树高度为:

,此时二叉树为平衡二叉树,如下图 balanced_LL_1

balanced_LL_1

对于图 LL_2,节点B的平衡因子为h,设B节点的左右子树高度为h,则二叉树C的高度为:h-1。右旋操作后,B的左子树高度不变为h,右子树高度为

:,此时二叉树为平衡二叉树,如下图 balanced_LL_2

balanced_LL_2

右旋代码

# rotate from left to right with the left-child node as the axis
def rotateL2R(node):
    leftChild = node.lchild
    leftChild.rchild,node.lchild = node,leftChild.rchild   # rotate
    updateHeight(node)
    updateHeight(leftChild)
    return leftChild

其中

函数作用为更新调整后节点的平衡因子,因为右旋操作平衡因子变化的节点只有两个:原根节点和新根节点,即根节点和根节点的左子节点,所以只需要对这两个节点执行

函数。函数代码参考如下:

更新二叉树高度

# update the height of the node
def updateHeight(root):
    if root.lchild and root.rchild:
        root.height = max(root.lchild.height, root.rchild.height) + 1
    elif root.lchild:
        root.height = root.lchild.height + 1
    elif root.rchild:
        root.height = root.rchild.height + 1
    else:
        root.height = 0

树的高度也就是左右子树的高度最大值加一,若无子树,则设置树高为零。

  • 右右情况(RR)

该情况与上面的左左情况具有对称性,对平衡二叉树执行插入或删除节点操作后,根节点的平衡因子变为-2,根节点的右子节点平衡因子为-1或0,为了恢复二叉树的平衡,需要进行左旋,来使得新的左右子树高度区域平衡。

RR

如上图RR所示,该情况下需要对平衡二叉树执行左旋操作:

  1. 设置根节点

的右子节点为新的根节点 ;

节点的左子树作为root节点的右子树,将root节点作为

的左子树,即降低“右子树”高度,提升“左子树”高度,使得新的左右子树高度趋于平衡;

左旋操作后,平衡二叉树如图 balanced_RR 所示。

balanced_RR

左旋代码

# rotate from right to left with the right-child node as the axis
def rotateR2L(node):
    rightChild = node.rchild
    rightChild.lchild, node.rchild = node, rightChild.lchild  # rotate
    updateHeight(node)
    updateHeight(rightChild)
    return rightChild

左旋操作同右旋一样,只更改了原根节点和新根节点的平衡因子,所以只需要对这两个节点执行

函数。

  • 左右情况

该情况下根节点的平衡因子与左左情况相同,都为2,不同之处在于左子节点的平衡因子为-1,若按照之前直接进行右旋操作,则旋转操作后二叉树扔处于不平衡状态。

对于图 LR,节点B的平衡因子为-1,设B节点的左子树D高度为h,则右子树E高度为h+1,因为A的平衡因子为2,所以二叉树C的高度为: h。则右旋操作后,B的左子树高度不变为h,右子树高度为:

,因为B的平衡因子为-2,所以按此方式的旋转操作没有效果。

所以该情况下,首先需要对根节点的左子节点进行调整,即将左子节点的平衡因子由-1调整为1, 使得当前情况转换为LL情况,然后再对二叉树执行右旋操作。

step 1:对左子树执行左旋操作

step_1

step 2:对二叉树执行右旋操作

step_2

  • 右左情况

该情况与上面左右情况对称,根节点的平衡因子为-2,右子节点平衡因子为1,需要首先对右子树进行右旋操作,调整二叉树为RR情况,再对二叉树执行左旋操作。

RL

step 1:对右子树执行右旋操作

step_1

step 2:对二叉树执行左旋操作

step_2

性能分析

因为平衡二叉树也是二叉搜索树,回顾二叉搜索树中的操作复杂度,查询、插入和删除复杂度均为

。平衡二叉树中查询复杂度影响因素自然为树的高度;插入节点操作可以拆分为两个步骤:查询节点位置,插入节点后平衡操作;删除节点操作同理可以拆分为两个步骤:查询节点位置,删除节点后平衡操作。 平衡调节过程中可能存在旋转操作,递归执行的次数则依赖于树的高度(可以优化为当前节点平衡因子不发生变化,则取消向上递归)。所以平衡二叉树中查询、插入和删除节点操作的复杂度依赖于树高。

平衡二叉树因为左右子树的平衡因子限制,所以不可能存在类似于斜树的情况,因为任一节点的左右子树高度差最大为一,且二叉树具有对称性,所以不妨设每个子树的左子树高度大于右子树高度。

AVL

根据平衡二叉树定义可知,若二叉树左子树高度为

,则右子树高度最少也要是h-1,方能满足平衡二叉树的平衡特性。以F(H)表示高度为H的平衡二叉树的最少节点个数,若二叉树不是空树则有:

根据推导公式可知,平衡二叉树的高度最大为

。当二叉树向完全二叉树靠拢,尽量填满每层上的节点时,树的高度最小,为

。所以相对于二叉搜索树,平衡二叉树避免了向线性结构演化的倾向,查询、插入和删除节点的时间复杂度为

。因为每个节点上需要保存平衡因子,所以空间复杂度要略高于二叉搜索树。

代码附录

python版本:3.7,树中的遍历、节点插入和删除操作使用的是递归形式

  • 树节点定义
# tree node definition
class Node(object):
    def __init__(self, value, height=0, lchild=None, rchild=None):
        self.lchild = lchild
        self.rchild = rchild
        self.value = value
        self.height = height   

相对于二叉搜索树的节点定义,增加了height属性。

  • 树定义
# tree definition
class Tree(object):
    def __init__(self, root=None):
        self.root = root

    # node in-order traversal(LDR)
    def traversal(self):
        traversal(self.root)

    # insert node
    def insert(self, value):
        self.root = insert(self.root, value)

    # delete node
    def delete(self, value):
        self.root = delete(self.root, value)
  • 模块中对树结构中的函数进行实现
# node in-order traversal(LDR)
def traversal(node):
    if not node:
        return
    traversal(node.lchild)
    print(node.value, 'height=', node.height, end=', ')
    traversal(node.rchild)

# insert node
'''
the recursive insert operation has a flaw,
that the binary tree will recursively updates the height of the parent node 
even if the inserted element already exists.
'''
def insert(root, value):
    if not root:
        return Node(value)
    if value < root.value:
        root.lchild = insert(root.lchild, value)
    elif value > root.value:
        root.rchild = insert(root.rchild, value)
    return checkBalance(root)

# check whether the tree is balanced
def checkBalance(root):
    if not root:
        return None
    if abs(heightDiffL2R(root)) < 2:  # the tree is balance
        updateHeight(root)
    elif heightDiffL2R(root) == 2:  # situation L
        if heightDiffL2R(root.lchild) == -1:  # situation LR
            root.lchild = rotateR2L(root.lchild)
            root = rotateL2R(root)
        else:  # situation LL
            root = rotateL2R(root)
    elif heightDiffL2R(root) == -2:  # situation R
        if heightDiffL2R(root.rchild) == 1:  # situation RL
            root.rchild = rotateL2R(root.rchild)
            root = rotateR2L(root)
        else:  # situation RR
            root = rotateR2L(root)
    return root

# get the height difference between left-child and right-child
def heightDiffL2R(node):
    if node.lchild and node.rchild:
        return node.lchild.height - node.rchild.height
    if node.lchild:
        return node.lchild.height + 1
    if node.rchild:
        return -(node.rchild.height + 1)
    return 0

# update the height of the node
def updateHeight(root):
    if root.lchild and root.rchild:
        root.height = max(root.lchild.height, root.rchild.height) + 1
    elif root.lchild:
        root.height = root.lchild.height + 1
    elif root.rchild:
        root.height = root.rchild.height + 1
    else:
        root.height = 0

# rotate from left to right with the left-child node as the axis
def rotateL2R(node):
    leftChild = node.lchild
    leftChild.rchild, node.lchild = node, leftChild.rchild
    updateHeight(node)
    updateHeight(leftChild)
    return leftChild

# rotate from right to left with the right-child node as the axis
def rotateR2L(node):
    rightChild = node.rchild
    rightChild.lchild, node.rchild = node, rightChild.lchild
    updateHeight(node)
    updateHeight(rightChild)
    return rightChild

def delete(root, value):
    if not root:
        return None
    if root.value > value:
        root.lchild = delete(root.lchild, value)
    elif root.value < value:
        root.rchild = delete(root.rchild, value)
    else:
        if root.lchild and root.rchild:  # degree of the node is 2
            target = transferDeleteNode(root)
            root = delete(root, target)
            root.value = target
        else:  # degree of the node is [0|1]
            root = root.lchild if root.lchild else root.rchild
    return checkBalance(root)

# find the maximum node or the minimum node in the tree
def transferDeleteNode(node):
    if node.rchild.height > node.lchild.height:
        target = node.rchild
        while target.lchild:
            target = target.lchild
    else:
        target = node.lchild
        while target.rchild:
            target = target.rchild
    return target.value
  • 测试代码与输出
if __name__ == '__main__':
    arr = [5, 3, 4, 0, 2, 1, 8, 6, 9, 7,7]
    T = Tree()
    for i in arr:
        T.insert(i)
    print('BST in-order traversal------------------')
    T.traversal()
    print('\ndelete test------------------')
    for i in arr[::-1]:
        print('after delete', i, end=',BST in-order is = ')
        T.delete(i)
        T.traversal()
        print()
  • 输出结果为:
BST in-order traversal------------------
0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 7 height= 0, 8 height= 1, 9 height= 0, 
delete test------------------
after delete 7,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 8 height= 1, 9 height= 0, 
after delete 7,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 8 height= 1, 9 height= 0, 
after delete 9,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 8 height= 0, 
after delete 6,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 2, 8 height= 0, 
after delete 8,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 2, 3 height= 0, 4 height= 1, 5 height= 0, 
after delete 1,BST in-order is = 0 height= 0, 2 height= 2, 3 height= 0, 4 height= 1, 5 height= 0, 
after delete 2,BST in-order is = 0 height= 0, 3 height= 2, 4 height= 1, 5 height= 0, 
after delete 0,BST in-order is = 3 height= 0, 4 height= 1, 5 height= 0, 
after delete 4,BST in-order is = 3 height= 1, 5 height= 0, 
after delete 3,BST in-order is = 5 height= 0, 
after delete 5,BST in-order is = 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 路径压缩

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    于小勇
  • 矩阵求导、几种重要的矩阵及常用的矩阵求导公式

    原文链接:https://blog.csdn.net/daaikuaichuan/article/details/80620518

    于小勇
  • logging addHandler(console)

    于小勇
  • 数据结构(四):平衡二叉树(AVL树)

    。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

    zhipingChen
  • 如何在CDH集群外配置非Kerberos环境的Gateway节点

    Fayson
  • Centos 7从python2.7.5

    py3study
  • TreeView中节点勾选设置

    本文转载:http://www.cnblogs.com/luxiaoxun/p/3288003.html

    跟着阿笨一起玩NET
  • 什么是二叉搜索树

    二叉搜索树是一种综合效率比较好的一种数据结构,搜索、插入、删除的复杂度等于树高, 平均空间复杂度为O(n),时间复杂度为O(log n),最坏时间复杂度为O(n...

    我是攻城师
  • 简单的python脚本监控服务器温度

    因为服务器放房间里面,我嫌吵,就通过ipmi把风扇调小了,但是我又怕以后服务运转的过多,cpu温度会过高出问题,所以就写了一个简单的温度控制脚本

    kevinfaith
  • 如何在 ASP.NET MVC 中集成 AngularJS(1)

    介绍 当涉及到计算机软件的开发时,我想运用所有的最新技术。例如,前端使用最新的 JavaScript 技术,服务器端使用最新的基于 REST 的 Web API...

    葡萄城控件

扫码关注云+社区

领取腾讯云代金券