平衡二叉树的构建(递归

2023-12-25 20:38:17

1.概念:

平衡二叉树(Balanced Binary Tree),也称为AVL树,是一种二叉树,它满足每个节点的左子树和右子树的高度差不超过1。换句话说,它是一棵高度平衡的二叉树。平衡二叉树的目的是为了保证二叉树的查询、插入和删除操作的时间复杂度都能够达到最优。
在这里插入图片描述

2.特点:

平衡二叉树有几个重要的特点:

高度平衡:每个节点的左子树和右子树的高度差不超过1,使得整个树的高度非常平衡。

快速查询:由于平衡二叉树的高度平衡,因此查询操作的时间复杂度为O(log n),在n个元素中查找一个元素只需要最多log2^n次比较。

快速插入和删除:平衡二叉树的插入和删除操作都能够在O(log n)时间内完成,因为节点的插入和删除都会导致树的平衡性被破坏,需要进行调整。

3.构建方法:

平衡二叉树的构建方法有很多种,但是最常见的方法是使用递归算法。具体来说,可以按照以下步骤构建平衡二叉树:

首先将输入的数据进行排序,然后按照中间节点的值创建根节点。

将剩余的数据分成两部分,分别递归地创建左子树和右子树,并将它们作为根节点的左子树和右子树。

重复上述步骤,直到所有的节点都被创建出来。

4.代码:

# 平衡二叉树节点类
class BiTreeNode():
    def __init__(self, data):
        self.lchild = None  # 二叉树左子树
        self.rchild = None  # 二叉树右子树
        self.data = data

# 创建平衡二叉树的函数
def create(list_data):
    # 中间节点索引
    mid_index = len(list_data) // 2

    # 创建节点
    node = BiTreeNode(list_data[mid_index])

    # 列表左右分割
    rlist_data = list_data[:mid_index]
    llist_data = list_data[mid_index + 1:]

    # 递归构建左子树和右子树
    if len(rlist_data) > 0:
        node.rchild = create(rlist_data)
    if len(llist_data) > 0:
        node.lchild = create(llist_data)

    return node  # 返回根节点

if __name__ == "__main__":
    list_data = [1, 2, 3, 0, 7, 8]   # 输入数据
    root = create(sorted(list_data))    # 默认升序

小结:

关注我给大家分享更多有趣的知识,以下是个人公众号,提供 ||代码兼职|| ||代码问题求解||
由于本号流量还不足以发表推广,搜我的公众号即可:
在这里插入图片描述

文章来源:https://blog.csdn.net/m0_72249799/article/details/135207583
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。