讲师中心 微信公众号

工具推荐

视频效率加速
updream

一键生成高质量推广成片

Laper
Laper

剧本策划到成片协作

立刻MV
立刻MV

低成本歌曲 MV、视频生成

Seko
Seko

AI短剧一键生成成片

C++如何实现二叉搜索树的平衡因子动态实时计算与旋转调整算法

浅辰大大_3298

浅辰大大_3298

发布时间:2026-06-30 11:18:24

|

881人浏览过

|

来源于php中文网

原创

平衡因子实时计算需在节点中缓存height字段,插入/删除后自底向上回溯更新:每层用子节点height重算自身height=max(left→height, right→height)+1,并立即计算balance=left→height−right→height;空子树高度为-1。

c++如何实现二叉搜索树的平衡因子动态实时计算与旋转调整算法

平衡因子怎么实时算,别每次遍历整棵树

平衡因子本质是左右子树高度差,实时更新的关键在于「自底向上回溯时顺手算」。如果每次调用 getBalanceFactor 都递归求左右高度,时间复杂度直接退化到 O(n),完全失去 AVL 树的意义。

正确做法是在每个节点里缓存 height 字段,插入/删除后沿路径向上修正——从被修改的叶子一路回到根,每层用子节点的 height 重算自己的 height = max(left->height, right->height) + 1,同时立即算出 balance = left->height - right->height。

  • 必须把 height 存在节点结构体里,不能靠函数临时算
  • 所有修改子树的操作(插入、删除)完成后,必须做一次自底向上的高度/平衡因子更新,不能只改局部
  • 注意空指针:叶子节点的子节点为 nullptr,对应高度按 -1 处理(这样单节点高度才是 0)

四种旋转怎么选,看的是失衡节点和插入路径的组合

不是「左子树高就右旋,右子树高就左旋」这么简单。AVL 的四种旋转由「失衡节点的平衡因子」和「导致失衡的那个子节点的平衡因子」共同决定,本质是看插入发生在「内侧」还是「外侧」。

假设当前失衡节点为 node,它左子树过高(node->balance == 2):

立即学习“C++免费学习笔记(深入)”;

C++14
C++14

C++14 对 C++11 的修正与增强版本,适合旧系统维护和较老工具链兼容。

下载
  • 如果 node->left->balance == 1:插入发生在左子树的左侧 → 执行 rotateRight(node)(LL 型)
  • 如果 node->left->balance == -1:插入发生在左子树的右侧 → 先 rotateLeft(node->left),再 rotateRight(node)(LR 型)

同理,右子树过高(node->balance == -2)时:node->right->balance == -1 是 RR,== 1 是 RL。关键点是必须检查子节点的 balance 值,而不是猜方向。

旋转后哪些节点的 height 和 balance 必须重算

旋转只是指针交换,不自动更新高度和平衡因子。只重算参与旋转的 2~3 个节点就够了,其余不受影响。

  • 单旋(LL/RR):只涉及 node 和它的左/右孩子,重算这两个节点的 height 和 balance
  • 双旋(LR/RL):涉及 node、node->left(或 right)、以及更下一层的孙子节点,共三个节点需重算
  • 千万别在旋转函数里递归更新整棵子树高度——这是常见性能陷阱

示例:LL 旋转后,原 node->left 成了新根,它的新高度取决于自己左右子树;原 node 现在是右孩子,它的新高度只取决于自己新的左右子树(其中一边刚被换掉)。

删除操作比插入更容易破坏平衡,回溯时得检查每一层

插入最多引发一次失衡(因为只增加一层),但删除可能让某条路径变短,导致从删除点到根的路径上多个节点都出现 balance 超出 [-1,1] 范围。所以删除后的修复必须「一路回溯到根」,对每个祖先节点都检查 balance 并必要时旋转。

  • 不能删完只修一次——哪怕某层旋转后暂时平衡了,上层仍可能失衡
  • 旋转后子树高度可能变化,必须更新该层节点的 height,否则上层计算会错
  • 特别注意:某次旋转可能让原本平衡的上层节点变得不平衡(比如 RL 旋转后,原祖父节点高度减 1),所以回溯不能中途停止

真正麻烦的不是旋转逻辑本身,而是忘记在回溯路径上持续更新 height——一个没更新,后面全错。

热门AI工具

更多
SoundView
SoundView Hot

SoundView是一款面向跨境电商的视频翻译、配音和本地化 AI 创作平台。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

讯飞智作

讯飞智作是一款AI视频创作工具,AI文本配音工具,数字人课程、营销视频制作。

超级麦吉

一款通过数字员工协作完成调研、数据分析与文档制作的AI办公平台。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

讯飞智文

一款面向学习和办公场景的AI文档创作工具,可辅助生成PPT与Word文档,提高资料整理和内容制作效率。

讯飞绘文

讯飞绘文是一款由科大讯飞推出的一站式 AIGC 内容运营平台。

相关专题

更多
c++和c语言的区别有哪些
c++和c语言的区别有哪些

c++和c语言的区别:1、面向对象编程(OOP)支持不同;2、新增特性不同;3、标准库不同;4、编译方式不同;5、命名空间不同等等。想了解更多c++的相关内容,可以阅读本专题下面的文章。

2328

2024.03.14

c++和python学习顺序推荐
c++和python学习顺序推荐

一般建议先学习C++,再学习Python,因为这样可以逐步从较为底层的编程语言向更高级的语言过渡。想了解更多python的相关内容,可以阅读本专题下面的文章。

1059

2024.03.14

python和c++学习性价比分析
python和c++学习性价比分析

Python易于学习,广泛应用于Web开发、数据科学和人工智能等领域,但性能较低。C语言性能高,适用于对性能要求较高的场景,如游戏开发和系统编程,但学习曲线陡峭,错误处理复杂。想了解更多python的相关内容,可以阅读本专题下面的文章。

467

2024.03.14

c语言和c++一样吗
c语言和c++一样吗

c语言和c++是两种不同的编程语言,虽然有相似之处,但存在显著差异。c语言专注于过程式编程和系统级开发,以简洁、高效著称。c++作为c语言的超集,引入了面向对象编程,增强了代码组织和管理能力,但学习曲线也更陡峭。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

347

2024.03.14

c语言和c++先学哪个好
c语言和c++先学哪个好

初学者选择学习c语言还是c++语言,需要根据个人学习目标、背景以及编程兴趣和预期应用方向来决定。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

446

2024.03.14

c语言和c++的区别和联系
c语言和c++的区别和联系

c语言和c++是计算机科学领域应用广泛的编程语言。虽然它们有着相似的基础,但它们在语言类型、语法功能和内存管理方面存在着显著差异。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

600

2024.03.14

c++软件中文更改教程
c++软件中文更改教程

对于 ide,可通过打开设置,找到语言设置,选择中文,并保存更改。对于非 ide 应用程序,可查找设置或选项,选择语言设置,更改为中文,并保存更改。想了解更多c++的相关内容,可以阅读本专题下面的文章。

1449

2024.03.21

python和java和c++学习性价比分析
python和java和c++学习性价比分析

Python以其易学性、丰富的库和活跃的社区而著称,适合数据科学、人工智能和Web开发。Java以其跨平台性、企业级应用开发和Android应用开发而闻名。C++以其底层控制能力、高效性能和游戏开发而著称。选择哪种语言取决于个人兴趣、职业方向和特定需求。想了解更多python和java和c++的相关内容,可以阅读本专题下面的文章。

1257

2024.03.22

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

20

2026.11.17

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Core Guidelines
C++ Core Guidelines

共0课时 | 0人学习

C++ Reference
C++ Reference

共0课时 | 0人学习

C++ 官方标准说明
C++ 官方标准说明

共0课时 | 0人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn