C++实现AVL树平衡旋转 _ 左右旋转逻辑代码实现【源码】
A VL树旋转必须返回新根节点，因二叉链表无父指针，调用方需用返回值重连子树；height函数对空节点须返回−1以保证平衡因子计算正确；四种失衡类型严格对应单旋或双旋，且判断条件中需包含等号。 实现A VL树的平衡旋转，可不是简单地“左右各写一个函数”就万事大吉了。真正的难点在于，旋转后必须同步更新
A VL树旋转必须返回新根节点，因二叉链表无父指针，调用方需用返回值重连子树；height函数对空节点须返回−1以保证平衡因子计算正确；四种失衡类型严格对应单旋或双旋，且判断条件中需包含等号。
实现A VL树的平衡旋转，可不是简单地“左右各写一个函数”就万事大吉了。真正的难点在于，旋转后必须同步更新节点高度、妥善处理父指针（如果采用三叉链结构），而且一次旋转往往不够——插入节点后，可能需要从插入点开始，沿着路径向上逐层检查平衡性，最多执行一次旋转才能恢复全局平衡。
为什么rotateLeft和rotateRight必须返回新根节点
这其实是由A VL树常见的实现方式决定的。大多数情况下，节点采用二叉链表结构，这意味着节点本身没有指向父节点的指针。那么问题来了：旋转操作会彻底改变局部子树的根节点，如果旋转函数不把新的根节点“告诉”上层调用者，上层代码该如何正确地重新建立链接呢？
举个例子就清楚了。假设因为右子树的插入导致了失衡，你调用了rotateLeft进行左旋。旋转完成后，原来那个失衡的节点已经不再是这棵子树的根了。如果旋转函数是void类型，调用方手里拿着的还是那个旧指针，原父节点的right字段就无法指向真正的新根，结果就是链表在此处“断裂”，整棵子树都丢失了。
这就是一个典型的陷阱。很多初学者会写出void rotateLeft(Node* node)这样的函数，内部虽然正确地调整了node->right和node->right->left的指向，但调用方却无法感知到这个变化，程序逻辑自然就错了。
正确的做法应该遵循以下三点：
- 函数签名设计为
Node* rotateRight(Node* y)，传入失衡节点y，返回旋转后的新根节点（也就是原来的y->left）。 - 调用时必须用返回值进行重连，例如：
x->right = rotateLeft(x->right)。 - 在旋转函数内部，所有指针关系重新建立后，必须立即调用
updateHeight来更新所有涉及节点的高度，为后续的平衡检查做好准备。
getBalanceFactor的计算顺序与边界处理
平衡因子的定义很明确：左子树高度减去右子树高度。但魔鬼藏在细节里。很多实现会直接写成height(node->left) - height(node->right)，这看似没问题，实则暗藏一个关键前提：height函数对于空节点（nullptr）必须返回-1，而不是0。
为什么必须是-1？我们来看一个反例。如果height(nullptr)返回0，那么对于一个叶子节点（左右子树皆空），计算出的平衡因子将是 0 - 0 = 0，这看起来是对的。但等等，叶子节点自身的高度通常是0。按照这个逻辑，一个高度为0的节点，其左右子树“高度”也是0，这在概念上是矛盾的，也会导致某些边界情况下的计算错误。正确的逻辑是，空树的高度定义为-1，这样叶子节点的平衡因子才是 (-1) - (-1) = 0。
来看一段有问题的代码：
int height(Node* n) { return n ? n->height : 0; } // ❌ 这会导致叶子节点的 balance 被误算为 1
而正确的写法应该是：
int height(Node* n) { return n ? n->height : -1; } // ✅ 确保空节点高度为-1，计算逻辑自洽
因此，实现getBalanceFactor时必须严格遵循这个高度定义，并且绝对不能省略空指针判断。即使你确信某个节点非空，为了代码的健壮性和避免未定义行为，这个检查也必不可少。
四种失衡场景如何对应到旋转组合
A VL树的平衡调整不是乱猜的，它严格对应着四种失衡类型。判断的依据是当前节点的平衡因子，以及其较重一侧子节点的平衡因子。这里千万不能凭感觉，必须对号入座：
- LL型（左左）：当
balance > 1且getBalanceFactor(node->left) >= 0时触发。这意味着新节点插入在左子树的左侧，只需一次右单旋即可。 - RR型（右右）：当
balance < -1且getBalanceFactor(node->right) <= 0时触发。这意味着新节点插入在右子树的右侧，只需一次左单旋即可。 - LR型（左右）：当
balance > 1且getBalanceFactor(node->left) < 0时触发。这意味着新节点插入在左子树的右侧，需要先对左孩子进行一次左旋（转化为LL型），再对当前节点进行一次右旋。 - RL型（右左）：当
balance < -1且getBalanceFactor(node->right) > 0时触发。这意味着新节点插入在右子树的左侧，需要先对右孩子进行一次右旋（转化为RR型），再对当前节点进行一次左旋。
这里有一个极其关键的细节：判断条件中的等号（=）必须包含。为什么？考虑一种情况，插入操作可能使一个原本平衡（因子为0）的子树变成轻微失衡（因子为+1或-1），这种情形仍然属于LL或RR型，需要用单旋解决。如果漏掉了等号，这部分失衡情况就会被错误地忽略，导致树最终失去平衡。
插入后updateHeight和平衡检查的调用时机
这是另一个容易出错的地方。高度更新和平衡检查的顺序至关重要，必须遵循一个原则：高度更新必须在旋转操作完成之后、向上回溯检查之前进行。
一个典型的错误流程是：在递归插入函数返回后，立即更新当前节点的高度，然后紧接着检查平衡因子。问题在于，此时其子树可能已经失衡，但你用来计算平衡因子的“高度”却是更新前、未失衡状态下的旧值，这必然导致误判。
正确的递归插入流程应该是这样的：
- 向左右子树递归插入新节点。
- 递归返回后，立即更新当前节点的高度：
height = 1 + max(height(left), height(right))。 - 基于刚更新的高度计算当前节点的平衡因子。
- 根据平衡因子及其子节点的平衡因子，判断属于四种失衡类型的哪一种，并执行相应的旋转（或不旋转）。
- 如果执行了旋转，旋转函数内部已经更新了所有相关节点（至少涉及三个节点）的高度。这里顺序很重要：必须先更新位置最低的“孙子”节点高度，然后更新“儿子”节点，最后更新新的根节点。顺序错了，中间计算的高度值就不准确。
最后再强调一遍最容易被忽略的一点：旋转操作本身就是一个改变结构的过程，必须在函数内部一鼓作气地完成所有节点高度的修正，不能留给外部流程，否则状态就会不一致。
IntelliJ IDEA 是 JetBrains 推出的专业集成开发环境，重点服务于 Java、Kotlin 与 JVM 项目开发。软件集成代码补全、静态检查、重构、调试、测试、版本控制及构建工具，并可借助插件扩展语言和框架支持。
JetBrains PyCharm 是面向 Python 开发者的集成开发环境，提供智能补全、代码检查、重构、调试、测试、版本控制及虚拟环境管理功能。Mac 版兼容 Intel 与 Apple 芯片，核心功能可免费使用。
JetBrains WebStorm 是面向 JavaScript、TypeScript 和现代 Web 技术的专业集成开发环境，可智能理解项目结构，提供代码补全、重构、错误检查、运行调试、测试及 Git 工具。
Adobe After Effects 是面向动态图形、影视特效与视频合成的专业创作软件。它提供关键帧动画、遮罩抠像、运动跟踪、三维空间、文字动画和表达式等工具，并可与 Premiere Pro、Photoshop、Illustrator
Adobe Audition 是面向播客、影视后期、音乐制作及内容创作者的专业音频工作站，提供波形精修、多轨录制与混音、频谱编辑、降噪修复、响度匹配和效果处理工具，并可与 Adobe Premiere 协同完成视频声音制作。
Adobe Bridge 是面向摄影师、设计师及内容团队的免费数字资产管理工具，可集中预览照片、视频和 Adobe 项目文件，并利用评级、标签、关键词、元数据、筛选与收藏集完成分类检索。它还支持批量重命名、格式导出、相机导入及 Camera
Adobe Illustrator 是 Adobe 推出的专业矢量图形设计软件，适合在 Mac 上制作标志、图标、插画、包装、信息图及印刷版面。它以路径和锚点构建可无损缩放的图形，并提供钢笔、形状、文字、图像描摹、渐变、画板及生成式功能。
Adobe InDesign 是面向印刷品与数字出版物的专业版面设计软件，可在 Mac 上制作书籍、杂志、宣传册、海报、报告及交互式文档。它提供精细的文字样式、网格、母版、长文档管理和印前输出能力。
Adobe Lightroom Classic 是面向桌面摄影工作流的照片管理与后期处理软件，可将原始照片保存在本地硬盘，通过目录、关键词、评分和收藏夹高效整理图库，并提供 RAW 冲印、蒙版、镜头校正、批量同步及多格式导出等功能。
Adobe Media Encoder 是 Adobe 推出的专业音视频编码与转码工具，可通过队列、预设和监视文件夹批量完成格式转换、代理文件创建及多平台成片输出，并与 Premiere Pro、After Effects 等软件紧密协作。
Adobe Photoshop 是面向摄影师、设计师和内容创作者的专业图像处理软件，提供图层、蒙版、选区、修复、调色、文字排版、智能对象及生成式编辑等能力。Mac 版支持 Intel 与 Apple Silicon 处理器。
Adobe Premiere Pro 是面向专业视频制作的非线性剪辑软件，提供多轨时间线、调色、音频处理、字幕、代理工作流和多格式输出能力，并可与 After Effects、Audition、Photoshop 及 Frame.io 协同
JetBrains IntelliJ IDEA 是以 Java、Kotlin 和 JVM 项目为核心的专业集成开发环境，提供智能补全、代码检查、安全重构、调试、测试、版本控制及构建工具集成。统一发行版的核心功能可免费用于商业和非商业项目，
PhpStorm 是 JetBrains 面向 PHP 与现代 Web 开发打造的专业集成开发环境，提供代码补全、静态检查、重构、调试、测试、数据库、版本控制及前端语言支持。Windows 用户可直接下载安装程序，
PyCharm 是 JetBrains 推出的 Python 集成开发环境，提供智能代码补全、错误检查、重构、调试、测试、Git、终端及 Jupyter Notebook 支持。统一版安装后可体验 30 天 Pro 功能，
WebStorm 是 JetBrains 面向 JavaScript、TypeScript 和现代 Web 技术打造的集成开发环境。它提供项目级代码分析、智能补全、安全重构、导航搜索，并集成调试、测试、终端、Git 与常用前端工具，
Adobe Photoshop 是面向摄影师、设计师和内容创作者的专业图像处理工具，可在 Windows 上完成照片修饰、选区抠图、图层合成、文字排版、绘画及生成式编辑。软件采用订阅授权，由 Creative Cloud 管理安装、更新与许
Adobe InDesign 是面向印刷与数字出版的专业页面排版工具，可制作书籍、杂志、宣传册、海报、交互式 PDF 和电子书。它提供精细的文字样式、多页面管理、印前检查及多格式输出能力，并能与 Photoshop、Illustrator
Adobe Illustrator 是用于绘制矢量图形、插画、图标、徽标和版式的专业设计工具。它以路径和锚点为核心，作品放大后仍能保持清晰，并提供画板、文字、渐变、图像描摹及精确变换等功能，适合品牌视觉、印刷物料、数字界面和商业插画创作。
Adobe Bridge 是 Adobe 推出的创意资产管理工具，可集中预览、分类和查找照片、视频、PDF及多种设计文件，并支持元数据、关键词、评级、批量重命名和格式导出。它可与 Photoshop、Illustrator 等应用衔接，
Adobe Lightroom Classic 是面向 Windows 桌面摄影工作流的照片管理与无损编辑工具，可通过目录集中整理大型图库，并完成 RAW 显影、局部蒙版、批量调整、打印和多格式导出。它强调本地文件管理与精细控制，
Adobe Acrobat Pro 是面向专业 PDF 工作的综合解决方案，可在 Windows 中创建、编辑、转换、比较、整理和保护文档，并支持表单、电子签名、扫描件文字识别及敏感信息永久遮盖。订阅还包含网页、移动服务和云端协作能力，
Adobe After Effects 是面向动态图形、动画与影视视觉特效制作的专业工具，可完成关键帧动画、图层合成、遮罩跟踪、抠像、文字动画和二维三维元素整合。Windows 版通过 Adobe Creative Cloud 安装及更新，
Adobe Media Encoder 是 Adobe 面向视频与音频制作流程提供的专业编码和转码工具，可批量处理媒体文件、创建代理、套用输出预设并监控文件夹自动执行任务。它与 Premiere、After Effects、Audition