当前位置: 首页 > news >正文

平衡二叉树的构建(递归

目录

  • 1.概念:
  • 2.特点:
  • 3.构建方法:
  • 4.代码:
  • 小结:

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))    # 默认升序

小结:

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

相关文章:

平衡二叉树的构建(递归

目录 1.概念:2.特点:3.构建方法:4.代码:小结: 1.概念: 平衡二叉树(Balanced Binary Tree),也称为AVL树,是一种二叉树,它满足每个节点的左子树和右…...

flutter开发实战-设置bottomNavigationBar中间按钮悬浮效果

flutter开发实战-设置bottomNavigationBar中间按钮悬浮的效果 在使用tabbar时候,可以使用bottomNavigationBar来设置中间凸起的按钮,如下 一、效果图 中间按钮凸起的效果图如下 二、实现代码 我们使用BottomAppBar 一个容器,通常与[Sscaf…...

不同参数规模大语言模型在不同微调方法下所需要的显存总结

原文来自DataLearnerAI官方网站: 不同参数规模大语言模型在不同微调方法下所需要的显存总结 | 数据学习者官方网站(Datalearner)https://www.datalearner.com/blog/1051703254378255 大模型的微调是当前很多人都在做的事情。微调可以让大语言模型适应特定领域的任…...

Crow:Middlewares 庖丁解牛6 middleware_call_helper

Crow:http请求到Rule绑定的handler_的调用链-CSDN博客 介绍了handler_的调用顺序,其中的一个调用过程是Connection::->handle void handle() {...ctx_ = detail::context<Middlewares...>();req_.middleware_context = static_cast<void*>(&ctx_);req_.m…...

MyBatis:Generator

MyBatis Generator附批量操作分页查询存储过程 Generator 介绍网址&#xff1a;Introduction to MyBatis Generator Generator &#xff0c;一个用于 MyBatis 的代码生成工具&#xff0c;可以根据数据库表结构自动生成对应的实体类、DAO 接口和 SQL 映射文件&#xff0c;提高…...

rabbitmq的事务实现、消费者的事务实现

RabbitMQ提供了事务机制&#xff0c;可以确保消息在发送和确认过程中的一致性。使用事务机制可以将一系列的消息操作&#xff08;发送、确认、回滚&#xff09;作为一个原子操作&#xff0c;要么全部执行成功&#xff0c;要么全部回滚。 下面是使用RabbitMQ事务的一般步骤&…...

龙芯杯个人赛串口——做一个 UART串口——RS-232

文章目录 Async transmitterAsync receiver1. RS-232 串行接口的工作原理DB-9 connectorAsynchronous communicationHow fast can we send data? 2.波特率时钟生成器Parameterized FPGA baud generator 3.RS-232 transmitter数据序列化完整代码&#xff1a; 4.RS-232 receiver…...

验证码服务使用指南

验证码服务使用指南 1 部署验证码服务 1.1 基础环境 Java 1.8 Maven3.3.9 1.2 安装Redis 参考“Redis安装指南” 1.3 部署验证码服务 1.3.1 下载源码 使用git从远程下载验证码服务代码(开源)。 1.3.2 使用idea打开项目 使用idea打开上一步下载的sailing目录&#xf…...

js中Math.min(...arr)和Math.max(...arr)的注意点

当arr变量为空数组时&#xff0c;这两个函数和不传参数时的结果是一样的 Math.max() // -Infinity Math.max(...[]) // -InfinityMath.min() // Infinity Math.min(...[]) // Infinity...

【zookeeper特点和集群架构】

文章目录 1. Zookeeper介绍2、ZooKeeper数据结构3、Zookeeper集群架构 1. Zookeeper介绍 ZooKeeper 是一个开源的分布式协调框架&#xff0c;是Apache Hadoop 的一个子项目&#xff0c;主要用来解决分 布式集群中应用系统的一致性问题。Zookeeper 的设计目标是将那些复杂且容易…...

MySQL集群架构搭建以及多数据源管理实战

MySQL集群架构搭建以及多数据源管理实战 ​ 数据库的分库分表操作&#xff0c;是互联网大型应用所需要面对的最核心的问题。因为数据往往是一个应用最核心的价值所在。但是&#xff0c;在最开始的时候&#xff0c;需要强调下&#xff0c;在实际应用中&#xff0c;对于数据库&a…...

C# WPF上位机开发(从demo编写到项目开发)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 C# WPF编程&#xff0c;特别是控件部分&#xff0c;其实学起来特别快。只是后面多了多线程、锁、数据库、网络这部分稍微复杂一点&#xff0c;不过…...

微信小程序引入 vant组件(详细步骤)

vant官方地址 https://vant-contrib.gitee.io/vant-weapp/#/quickstart 步骤一、 通过 npm 安装 # 通过 npm 安装 npm i vant/weapp -S --production# 通过 yarn 安装 yarn add vant/weapp --production# 安装 0.x 版本 npm i vant-weapp -S --production步骤二 修改 app.js…...

Django之按钮(actions)

开篇就是道歉&#xff0c;哈哈哈哈&#xff0c;托更了好久好久&#xff0c;最近太忙了没啥时间更新&#xff0c;各位看官有催更的阔以给我私信哇&#xff0c;希望各位看官给个三连&#xff01;&#xff01;&#xff01;&#x1f60d;&#x1f60d;&#x1f60d;&#x1f60d; …...

从YOLOv1到YOLOv8的YOLO系列最新综述【2023年4月】

作者&#xff1a;Juan R. Terven 、Diana M. Cordova-Esparaza 摘要&#xff1a;YOLO已经成为机器人、无人驾驶汽车和视频监控应用的核心实时物体检测系统。我们对YOLO的演变进行了全面的分析&#xff0c;研究了从最初的YOLO到YOLOv8每次迭代的创新和贡献。我们首先描述了标准…...

浙江大唐乌沙山电厂选择ZStack Cloud打造新一代云基础设施

浙江大唐乌沙山电厂选择云轴科技ZStack Cloud云平台为其提供高性能、高可用的云主机、云存储和云网络&#xff0c;构建了简单、稳定、安全、高效的云基础设施&#xff1b;通过ZStackCloud为其提供可视化服务编排、多租户自服务等模块&#xff0c;帮助电厂提高IT资源利用率&…...

电脑开机快捷启动,启动菜单没有u盘怎么办

电脑开机快捷启动键找不到u盘怎么办 对于快捷启动键找不到u盘的问题&#xff0c;小编很了解其中的门道&#xff0c;因为开机找不到u盘是我们使用电脑时候的常见问题。那么我们到底要如何解决开机找不到u盘的问题呢?其实方法还是蛮简单的&#xff0c;下面小编就来教大家电脑开…...

线程的同步与互斥

抢票的例子 竞争过程 进程A被切走 进程B被切走 结论&#xff1a; 互斥 int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr); mutex: 指向要初始化的互斥锁的指针。attr: 用于设置互斥锁属性的指针&#xff0c;通常可以传入 NULL 以使用默认属性…...

低代码实施复杂应用的实践方法

内容来自演讲&#xff1a;韦有炬 | 柳州知行远企业管理咨询有限公司 | 总经理 摘要 本文探讨了在全民开发时代如何使用低代码实施复杂应用并降低上线风险。文章分析了复杂系统实施失败的风险&#xff0c;包括项目规划不周、人员变动、企业基础管理不足等&#xff0c;并对比了低…...

算法学习系列(十一):KMP算法

目录 引言一、算法概念二、题目描述三、思路讲解三、代码实现四、测试 引言 这个KMP算法就是怎么说呢&#xff0c;就是不管算法竞赛还是找工作笔试面试&#xff0c;都是非常爱问爱考的&#xff0c;其实也是因为这个算法比较难懂&#xff0c;其实就是很难&#xff0c;所以非常个…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...