当前位置: 首页 > 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;所以非常个…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...