开发者社区> 登天蚂蚁> 正文

数据结构(四):平衡二叉树(AVL树)

简介: 通过之前对二叉搜索树介绍可知,将集合构造为二叉搜索树结构,该结构下对树中节点的查询、删除和插入三种操作,时间复杂度均为 ~。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。
+关注继续查看
img_efc824708393197faf3ded1ee43347b7.jpe

通过之前对二叉搜索树介绍可知,将集合构造为二叉搜索树结构,该结构下对树中节点的查询、删除和插入三种操作,时间复杂度均为 O(log_2N)~O(N)。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

定义

平衡二叉树也叫自平衡二叉搜索树(Self-Balancing Binary Search Tree),所以其本质也是一颗二叉搜索树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子,树中每个节点的平衡因子绝对值不大于 1,此时二叉搜索树称之为平衡二叉树。

自平衡是指,在对平衡二叉树执行插入或删除节点操作后,可能会导致树中某个节点的平衡因子绝对值超过 1,即平衡二叉树变得“不平衡”,为了恢复该节点左右子树的平衡,此时需要对节点执行旋转操作。

情景分析

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

  • 左左情况(LL)

LL 情况是指根节点的平衡因子为 2,根节点的左子节点平衡因子为 01

img_34b62edda9e54582580aaa99cb3994f9.png
LL_1

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

img_eb35f7209487b0feabde0edc04949aeb.png
LL_2

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

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

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

  1. 设置根节点 root 的左子节点为新的根节点 root_{new}
  2. root_{new} 节点的右子树作为 root 节点的左子树,将 root 节点作为 root_{new} 的右子树,即降低“左子树”高度,提升“右子树”高度,使得新的左右子树高度趋于平衡;

对于图 LL_1,节点 B 的平衡因子为 1,设 B 节点的左子树 D 高度为 h,则右子树 E 高度为h-1,因为 A 的平衡因子为 2,所以二叉树 C 的高度为: h-1。则右旋操作后,B 的左子树高度不变为 h,右子树高度为:1+max(height(C),height(E))=h,此时二叉树为平衡二叉树,如下图 balanced_LL_1

img_7086e1c721b5751949492a25cf1e39ba.png
balanced_LL_1

对于图 LL_2,节点 B 的平衡因子为 0,设 B 节点的左右子树高度为 h,则二叉树 C 的高度为: h-1。右旋操作后,B 的左子树高度不变为 h,右子树高度为:1+max(height(C),height(E))=h+1,此时二叉树为平衡二叉树,如下图 balanced_LL_2

img_8ba5bb329a3116da1a8ec058669c61fa.png
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

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

更新二叉树高度
# 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,根节点的右子节点平衡因子为 -10,为了恢复二叉树的平衡,需要进行左旋,来使得新的左右子树高度区域平衡。

img_da8a28b76223a6974b5e2cf984cefb57.png
RR

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

  1. 设置根节点 root 的右子节点为新的根节点 root_{new}
  2. root_{new} 节点的左子树作为 root 节点的右子树,将 root 节点作为 root_{new} 的左子树,即降低“右子树”高度,提升“左子树”高度,使得新的左右子树高度趋于平衡;

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

img_49c2de225d46291053f3bf74879e4c6d.png
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

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

  • 左右情况

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

对于图 LR,节点 B 的平衡因子为 -1,设 B 节点的左子树 D 高度为 h,则右子树 E 高度为h+1,因为 A 的平衡因子为 2,所以二叉树 C 的高度为: h。则右旋操作后,B 的左子树高度不变为 h,右子树高度为:1+max(height(C),height(E))=h+2,因为 B 的平衡因子为 -2,所以按此方式的旋转操作没有效果。

img_009db677e1fa0f07fe2c60285a1674af.png
LR

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

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

img_9543b72f9580142af4f9fdbb4f91ad59.png
step_1

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

img_34be33ef992fbbd869a9c49c44dfbadc.png
step_2
  • 右左情况

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

img_a4353f2a334bf4afcf41ba59d59c3031.png
RL

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

img_f9e10b241f356e6b6fca308b2e0e3767.png
step_1

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

img_6b2c5a29b42d94fd62ef310620d5ea82.png
step_2

性能分析

因为平衡二叉树也是二叉搜索树,回顾二叉搜索树中的操作复杂度,查询、插入和删除复杂度均为 log_2N~N。平衡二叉树中查询复杂度影响因素自然为树的高度;插入节点操作可以拆分为两个步骤:查询节点位置,插入节点后平衡操作;删除节点操作同理可以拆分为两个步骤:查询节点位置,删除节点后平衡操作。

平衡调节过程中可能存在旋转操作,递归执行的次数则依赖于树的高度(可以优化为当前节点平衡因子不发生变化,则取消向上递归)。所以平衡二叉树中查询、插入和删除节点操作的复杂度依赖于树高。

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

img_484d678e65ee667542c4a35c3875e36a.png
AVL

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

F(0) = 1
F(1) = 2
F(2) = 4
F(H) = F(H-1)+F(H-2)+1(H \ge 3)

根据推导公式可知,平衡二叉树的高度最大为 O(log_{\frac{1+\sqrt5}2}N)。当二叉树向完全二叉树靠拢,尽量填满每层上的节点时,树的高度最小,为 O(log_2N)。所以相对于二叉搜索树,平衡二叉树避免了向线性结构演化的倾向,查询、插入和删除节点的时间复杂度为 O(log_2N)~O(log_{\frac{1+\sqrt5}2}N)。因为每个节点上需要保存平衡因子,所以空间复杂度要略高于二叉搜索树。

代码附录

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 = 

github 链接:平衡二叉树

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《重学数据结构》之什么是二叉树?(上)
基本概念 树,一种非线性表数据结构: 节点 “树”里面的每个元素 父子关系 连线相邻节点之间的关系 兄弟节点 节点的父节点是同一个节点 根节点 没有父节点的节点 叶(子)节点 没有子节点的节点 节点的高度 节点到叶节点的最长路径(边数) 树的高度 根节点的高度 节点的深度 根节点到该节点所经历的边的个数 节点的层数 节点的深度+1
30 0
《重学数据结构》之什么是二叉树?(下)
基本概念 树,一种非线性表数据结构: 节点 “树”里面的每个元素 父子关系 连线相邻节点之间的关系 兄弟节点 节点的父节点是同一个节点 根节点 没有父节点的节点 叶(子)节点 没有子节点的节点 节点的高度 节点到叶节点的最长路径(边数) 树的高度 根节点的高度 节点的深度 根节点到该节点所经历的边的个数 节点的层数 节点的深度+1
30 0
Erlang Mnesia 数据丢失(并未真正丢失,只是索引丢失)
从 Ejabberd开源项目中了解到了 Mnesia的用法,之后好多长一段时间都用 Mnesia 设计分布式缓存。 前段时间系统上线没有出现问题,过了一段时间发现用户登录出现异常(总结发现都是用户切换网络时候出现)发现用户或设备数据丢失
260 0
数据结构(四):平衡二叉树(AVL树)
通过之前对二叉搜索树介绍可知,将集合构造为二叉搜索树结构,该结构下对树中节点的查询、删除和插入三种操作,时间复杂度均为 ~。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。
903 0
数据结构(一):二叉树
定义 二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为: 三个不相交的节点集合构成,一个作为根节点,一个节点集构成的二叉树作为根节点的左子树,另一个节点集构成的二叉树作为根节点的右子树 当节点数为零时,表示二叉树为空 所以节点个数为零的空树也是二叉树,二叉树根节点的左、右子树也是二叉树,其结构同样符合以上定义,当左子树为空树时,表示根节点没有左子节点。
830 0
数据智能,触手可及!袋鼠云数栈推出 数据科学平台 DTinsight.Science
一句话了解DTinsight.Science DTinsight.Science是「可视化建模与交互式代码编写于一体的机器学习作业探索平台」,实现数据接入、可视化实验建模、Notebook编程、模型训练、模型部署、任务运维等开发场景,帮助企业构建算法服务能力,提供高效、安全、稳定的算法运行环境。
2449 0
数据结构(二):二叉搜索树(Binary Search Tree)
二分法猜数字的游戏应该每个人都知道,通过对猜测数字“大了”、“小了”的情况判断,来猜出最终的数字。序列范围为 的集合,复杂度为 ,即最多需要 次可以猜到最终数字。
959 0
【图解数据结构】树和二叉树全面总结
阅读本次文章你将会掌握树和二叉树的基本概念、五大性质、判断完全二叉树、满二叉树,二叉树的四大遍历、要求写出遍历顺序和相应的递归代码。搞懂二叉树和树的相互转换流程。
20 0
数据结构(三):二叉树遍历
遍历方式 二叉树的常见遍历方式如下几种: 前序遍历: 访问根节点,前序遍历方式访问左子树,前序遍历方式访问右子树; 中序遍历: 中序遍历方式访问左子树,访问根节点,中序遍历方式访问右子树; 后序遍历: 后序遍历方式访问左子树,后序遍历方式访问右子树,访问根节点; 层次遍历: 按照层次递增的顺序,依次访问树的每层节点。
860 0
+关注
登天蚂蚁
相信量变引发质变,相信厚积薄发
30
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载