第10章 AVL树-红黑树
10.1 平衡树基础概念
在5.7.1小节中，讨论了二叉搜索树的缺陷，当我们把有序的数据依次插入普通的二叉搜索树（BST）时，树不会长成“左右均匀”的形状，而是沿着一条方向一直长下去：递增序列会产生完全右偏的树（每个节点只有右子节点）；递减序列会产生完全左偏的树（每个节点只有左子节点）。形象地说，BST 会“退化”为一个链表。
二叉搜索树在面对有序的数据时，额外脆弱，因此延伸讨论了如何做到让树的高度保持在一个较低且可控的范围，使左右子树的高度差保持小，从而让操作效率保持稳定。而今天所要学习的平衡树就是相关的解决方案。
10.1.1 平衡树的定义与必要性
平衡树是一类自我约束高度的二叉搜索树。其目的是通过一些特殊的技巧来维护树的高度平衡，从而保证树的搜索、插入、删除等操作的时间复杂度都较低。在刚才讨论二叉搜索树是有可能退化成链状结构，那么搜索、插入、删除等操作的时间复杂度就会达到最坏情况，即O(n)，因此不能满足要求，这是我们需要平衡树的原因。
平衡树通过不断调整树的结构，使得树的高度尽量平衡，从而保证搜索、插入、删除等操作的时间复杂度都较低，通常为O(logn)。因此，如果我们需要高效地处理大量的数据（在如今信息爆炸的时代，高效处理信息的需求逐渐提升），那么平衡树就显得非常重要了。
当插入或删除导致树失衡时，平衡树会通过局部旋转（左旋、右旋或组合旋转）来恢复平衡。不同平衡树对“平衡”的定义略有不同：如 AVL 树严格限制高度差，红黑树通过颜色规则间接控制高度，但核心思想一致——用额外规则换取高度可控，从而换取性能稳定性。
假如我们连续的插入1、2、3、4、5、6的数字，那么二叉搜索树最终形成的结构如图10-1所示。
图10-1 二叉搜索树的平衡
而实际中，不只是添加会导致树的不平衡，删除元素也可能会导致树的不平衡。在普通二叉搜索树中，插入和删除操作始终遵循有序性规则，但树本身并不对高度或形态作任何约束。因此，任意一系列有序修改操作，都可能使树的结构逐渐偏斜，甚至退化为近似链表。这里的“不平衡”并非规则意义上的失衡，而是指结构上高度增长、左右子树分布不均所带来的性能退化。
正是由于普通二叉搜索树只保证有序性而不约束结构形态，树的高度完全依赖于操作序列本身。一旦插入或删除的数据分布存在偏序，树就可能逐渐向一侧生长，最终退化为近似链表，使查找、插入和删除等操作的时间复杂度从期望的O(log n)退化到最坏的O(n)。这种性能的不稳定性，并不是算法实现上的缺陷，而是 BST 设计本身就这样。那么如何让一棵树更加平衡呢？
为了在保持有序性的同时控制树的高度并稳定操作性能，引入了平衡树这一类数据结构。平衡树在每次结构性修改后，通过额外的平衡约束与局部调整机制，将树限制在“近似完全”的形态范围内，从而保证基本操作在最坏情况下仍能维持在O(log n)的时间复杂度。这正是平衡树相对于普通二叉搜索树最根本的设计动机。
额外的平衡约束与局部调整机制？要如何去做？通常有以下两种方式：
（1）方式一：限制插入、删除的节点（比如在树特性的状态下，不允许插入或者删除某些节点，不现实）。
（2）方式二：在随机插入或者删除元素后，通过某种方式观察树是否平衡，如果不平衡通过特定的方式（比如旋转），让树保持平衡。
方式一并不现实，正如我们前面所说，任意一系列有序修改操作，都可能使树的结构逐渐偏斜，甚至退化为近似链表。有序修改删除操作是非常多且不可避免的，如果为了维持结构形态而在树处于某种状态时拒绝执行这些本就合法的操作，那树的实用性和灵活性会大大降低，在实际使用中处处受限，是没人喜欢使用的，而且违背“支持动态有序数据”的设计初衷。
相比之下，方式二采取的是更符合数据结构设计原则的思路：允许任意合法的插入和删除操作始终按照二叉搜索树的有序规则执行，而在操作完成后，通过维护额外的平衡信息来检测结构是否偏离预期形态。一旦发现局部失衡，便通过预先定义好的调整手段（如旋转等局部重构操作）对树的结构进行修复，使其重新回到受控的高度范围内。这种做法既不限制操作的合法性，又能在整体上约束树的形态，从而在保证有序性的同时，稳定树的高度和操作性能。
现在我们来看AVL树在一次插入操作后，由平衡到失衡，再通过旋转恢复平衡的全过程，如图10-2所示。
图10-2 AVL树的插入操作
图10-2所述内容可以从“发生了什么”和“为什么这样做”两个层次来理解。最左侧是一棵合法的 AVL 树。此时以 100 为根，左右子树高度相近，所有节点的平衡因子都在允许范围内，说明树的高度被有效控制。接下来向树中插入新节点 12，插入过程严格遵循二叉搜索树的有序性规则，新节点沿着 100 → 50 → 25 的路径，被放入最左侧的位置。
插入完成后，树的有序性没有任何问题，但高度信息发生了变化。新节点的加入使得 25、50 以及 100 的左子树高度依次增加，而右子树高度保持不变，最终导致节点 100 的左右子树高度差超过 1。此时 100 成为第一个不满足 AVL 平衡条件的节点，也就是图中标注的 critical node。由于失衡路径是“左子树的左子树”，这一情形被称为 LL 型失衡。
针对 LL 型失衡，AVL 树采用一次右旋操作来修复结构。右旋并不是重新插入节点，而是一种局部的结构重排：让失衡节点 100 的左孩子 50 上移成为新的根节点，而 100 下沉为其右孩子，同时将 50 原本的右子树调整为 100 的左子树。整个过程中，各节点的相对大小关系没有被破坏，因此二叉搜索树的有序性得以完整保留。
旋转完成后，树的结构重新变得紧凑，所有节点的左右子树高度差再次回到允许范围内，整棵树恢复为一棵合法的 AVL 树。这个过程体现了 AVL 树的核心思想：插入操作可以是任意合法的有序操作，而平衡性通过插入后的局部旋转来修复，从而保证整体性能的稳定性。
通过一次AVL树的一次插入操作，我们见证了预先定义好的调整手段是如何对树的结构进行修复的。
10.1.2 平衡树的分类与应用
计算机发展到如今，常见的平衡二叉搜索树已经根据应用场景，被人发明出来，不需要我们去冥思苦想，直接学习就行。常见的平衡二叉搜索树有以下5种：
（1）AVL树：这是一种最早的平衡二叉搜索树，在1962年由G.M. Adelson-Velsky和E.M. Landis发明。PS：AVL树的命名即发明者的首字母拼接。
（2）红黑树：这是一种比较流行的平衡二叉搜索树，由R. Bayer在1972年发明。
（3）Splay树：这是一种动态平衡二叉搜索树，通过旋转操作对树进行平衡。
（4）Treap：这是一种随机化的平衡二叉搜索树，是二叉搜索树和堆的结合。
（5）B-树：这是一种适用于磁盘或其他外存存储设备的多路平衡查找树。
这些平衡二叉搜索树都用于保证搜索树的平衡，从而在插入、删除、查找操作时保证了较低的时间复杂度。如果把这些平衡二叉搜索树放在一起看，其实它们的差异主要体现在“追求什么样的平衡、愿意为此付出多大的维护成本”上。AVL 树是最“较真”的那一类，它对高度控制得非常严格，几乎时刻保持最矮，因此查询性能很稳定，但插入和删除时旋转也最频繁。红黑树则更像现实主义者，它不追求绝对平衡，只要“别太歪”就行，用更宽松的规则换来了更少的调整成本，这也是它在工程中（比如各种语言的 map/set 实现）被广泛采用的原因。
Splay 树的思路就完全不一样了，它并不保证每一刻都平衡，而是相信“常用的节点以后还会常用”，每次访问都会把节点旋转到根附近，用摊还复杂度来换取长期平均性能。Treap 则把“平衡”这件事交给概率，通过给节点随机优先级，让树在期望意义上保持平衡，结构简单、实现优雅，但带点随机色彩。至于 B-树，它已经跳出了“纯内存二叉树”的范畴，通过多路分支大幅降低树高，减少磁盘 IO，几乎是为数据库和文件系统量身定做的方案。可以说，这些树并不是互相取代，而是各自在不同使用场景下，给“有序 + 高效”提供了不同的解决路径。
总结下来，红黑树和AVL树因占据了查询、插入，查找等主要高频操作行为，是应用最广泛的平衡二叉搜索树。红黑树被广泛应用于实现诸如操作系统内核、数据库、编译器等软件中的数据结构，其原因在于它在插入、删除、查找操作时都具有较低的时间复杂度。而AVL树被用于实现各种需要高效查询的数据结构，如计算机图形学、数学计算和计算机科学研究中的一些特定算法。
这两者的区别在于红黑树更稳定，而AVL树牺牲一定稳定性，做到在查询性能极致化。AVL树和红黑树在时间复杂度量级上是一样的，都是 O(log n)，红黑树被广泛采用，并不是因为“时间复杂度更低”，而是在“最坏情况下旋转次数更少，维护成本更低”，稳定性更强。在现实中，稳定性往往比性能极致更具备应用场景。
10.2 AVL树详解
在前面所说，AVL树（Adelson-Velsky and Landis Tree）是由G.M. Adelson-Velsky和E.M. Landis在1962年发明的，它是一种自（Self）平衡二叉搜索树。自平衡是什么意思？指自动平衡，当出现失衡情况时，树会根据既定的平衡规则，自动对局部结构进行调整，使其重新满足平衡条件。自动行为源于算法的主动且持续的维护。
在AVL树身上是指：树在每一次插入或删除节点之后，都会自动检查自身的结构是否仍然满足平衡条件；一旦发现某些节点的左右子树高度差超过允许范围，就会立即通过局部调整（旋转）把树修复回来。所以我们可以说AVL树是二叉搜索树的一个变体，在保证二叉搜索树性质的同时，通过旋转操作保证树的平衡。
10.2.1 AVL树的基本特性
通过对平衡树的概念学习，以及了解AVL树的运作原理。我们清楚的知道AVL树主要特性源于两点操作：
（1）每次树结构的改变都会检查自身是否处于平衡状态。
（2）当树结构处于失衡状态，通过旋转操作，使树结构恢复平衡状态。
但AVL树要通过什么方式来检查树结构是否处于平衡状态呢？通过平衡因子，通俗易懂的说：是"权重"。
在 AVL 树中，每个节点都会维护一个与“高度”相关的度量，通常称为平衡因子（有时也被口语化地称为权值）。这个平衡因子表示该节点左子树高度与右子树高度之差，一般定义为 左子树高度 − 右子树高度。由于 AVL 树对平衡性有严格约束，任意节点的平衡因子只能取 -1、0 或 1，也就是说，任一节点的左右子树高度差最多为 1。正是这种对高度差的强制限制，使 AVL 树在结构上始终保持“接近完全”的形态，因此也常被称为高度平衡树。
这种高度上的严格控制，直接带来了性能上的好处。与普通二叉搜索树不同，AVL 树不会因为插入顺序不当而逐渐退化为链表，其整体高度始终维持在 O(log n) 范围内，从而保证查找操作具有稳定且高效的时间复杂度。当插入或删除节点导致某些节点的平衡因子超出允许范围时，AVL 树会立即通过一系列旋转操作对局部结构进行调整，在不破坏二叉搜索树有序性的前提下恢复平衡状态。正是这种“修改后即时修复”的机制，使 AVL 树在动态更新场景中依然能够保持良好的查询性能。
AVL树的插入和删除操作与普通的二叉搜索树类似，但是在插入或者删除之后，AVL树需要通过旋转操作来继续保持树的平衡。
图10-3 AVL树的平衡因子
AVL树的平衡因子如图10-3所示。这棵 AVL 树中，每个节点旁边标注的数字表示的是平衡因子（balance factor），由节点左右子树的高度计算得出，通常定义为：左子树高度 − 右子树高度。例如根节点 100，其左子树高度为 3，右子树高度为 2，因此平衡因子为 3 − 2 = 1；节点 50 的左子树高度为 1、右子树高度为 2，于是得到 1 − 2 = -1；而像 75、150 这类左右子树高度相同的节点，其平衡因子自然为 0。叶子节点由于没有子树，高度差为 0，平衡因子也为 0。
在插入或删除节点时，AVL 树会从发生变化的位置开始，自下而上更新各节点的高度和平衡因子。一旦发现某个节点的平衡因子变为 2 或 -2，就说明该节点已经失衡，AVL 树会根据失衡方向（LL、LR、RR、RL）选择对应的旋转方式，对局部结构进行调整。旋转完成后，相关节点的高度和权值会被重新计算，使平衡因子重新回到允许范围内。
失衡方向（LL、LR、RR、RL）是用来描述失衡节点是“往哪一侧歪的”，以及“歪的那一侧内部又是怎么歪的”。
（1）LL（Left-Left）型失衡：左子树高，且左子树的左子树也更高。
（2）LR（Left-Right）型失衡：左子树高，但左子树内部是右子树更高。
（3）RR（Right-Right）型失衡：右子树高，且右子树的右子树也更高。
（4）RL（Right-Left）型失衡：右子树高，但右子树内部是左子树更高。
记住4种失衡方向的方式：第一个字母看“哪边高”，第二个字母看“高度来自那边的哪一侧”。所以旋转方式有可能转一次也可能转两次。像LL和RR这种两次旋转都在一个方向的，可以合并成一次旋转；而LR和RL这种两次旋转相反的，就需要转两次。
由于AVL树具有自平衡性，哪怕最坏的情况下，时间复杂度也仅为O(log n)，不至于退化成链表。
10.2.2 AVL树的旋转操作
10.2.1小节中，知晓了AVL树通过平衡因子来判断是否处于平衡状态，以及4种类型的失衡状态。当处于这4种失衡状态，知道要通过旋转操作使AVL树保持平衡状态。可旋转操作是怎么做的？AVL树的旋转操作如图10-4所示。
图10-4 AVL树的旋转操作
这幅图，我们很快就会用到。AVL树的实现离不开旋转，而在旋转之前，还需要解决什么时候旋转？从哪个节点旋转？转左边还是转右边等问题。所以接下来，会着重关注这些问题，最终在10.2.5小节，来深入AVL树的旋转问题。
10.2.3 AVL树的节点封装
手写实现AVL树本身的过程是相当的复杂的，那么我们要如何规划学习AVL树的路径呢？将一个庞大的目标，拆分成数个小目标，使学习曲线更加平缓是一种非常好用的方式，我们的AVL树学习也采用该方法，将手写AVL树拆分为5大步骤：
（1）学习AVL树节点的封装。
（2）学习AVL树的旋转代码情况。
（3）写出不同情况下进行的不同旋转操作。
（4）写出插入操作后，树的再平衡操作。
（5）写出删除操作后，树的再平衡操作。
一步步实现上面的功能，最后将功能组合在一起，实现AVL树的编写，让我们开始吧！
封装AVL树的节点在完全未知的情况是非常难以完善的。假如我们从未学习过AVL树，我们可能会先将二叉搜索树的节点直接拿过来使用，然后在后续编写代码与完善思路中发现矛盾之处，再回过头对AVL树的节点进行完善补充，然后继续往后编写实现AVL树，循环往复。每一次重构代码都是对自身的一次考验，个人的思维逻辑也会在该过程得到极强的锻炼。PS：AVL 节点的设计（高度 / 平衡因子 / 子指针 / 回溯更新）高度依赖整体算法的协同关系，不是“看到就能想到”的字段组合。如果不知道后面要做旋转、回溯、失衡判断，节点设计必然会反复推翻。
不过这种做法是非常痛苦的，而且非常消耗时间。我们完全不必这么做，但在学习现成的AVL树时，我们也可以采用迂回的，更具性价比的做法，让思维模式也能有足够的锻炼。如：在编写AVL树节点时，看着完善的属性设定，多想一想这些属性会用在哪些地方，会如何使用，最后能用自己的话表达出来。每次思考都可以在稍等之后的学习中得到验证，主动的用起头脑理解和被动摄入知识的效率相比，是云泥之别。
接下来，让我们来封装AVL树的节点。
AVL树也是一棵二叉搜索树，只不过多了两点主要特性（10.2.1小节开头说明），所以AVL树的节点可以继承自二叉搜索树的节点，在原有基础上去开发。二叉搜索树节点代码如下：
▼typescript复制代码class Node<T> { value: T constructor(value: T) { this.value = value } } export class TreeNode<T> extends Node<T> { left: TreeNode<T> | null = null right: TreeNode<T> | null = null // 当前节点的父节点 parent: TreeNode<T> | null = null // 判断当前节点是父节点的左子节点 get isLeft(): boolean { return !!(this.parent && this.parent.left === this) } // 判断当前节点是父节点的右子节点 get isRight(): boolean { return !!(this.parent && this.parent.right === this) } }
AVL树的节点继承自二叉搜索树节点， 在这里可以提前说明isLeft()和isRight()方法很重要，但为什么很重要？可以先想一想。
然后重写left，right和parent属性，设置为AVL树本身的节点类型，后续方便取出一些AVL树所特定的属性。
▼typescript复制代码class AVLTreeNode<T> extends TreeNode<T> { // 保证获取到的left/right节点的类型是AVLTreeNode left: AVLTreeNode<T> | null = null right: AVLTreeNode<T> | null = null parent: AVLTreeNode<T> | null = null }
10.2.4 AVL树的平衡状态
完成AVLTreeNode节点的基础封装后，我们接下来要开始封装AVL树节点的核心部分，在编写的同时，可以思考该核心部分的用途是什么，能在哪一位置使用。学习已有数据结构时，无需多次往返重构，节省时间是我们的优势。
▼typescript复制代码class AVLTreeNode<T> extends TreeNode<T> { // 保证获取到的left/right节点的类型是AVLTreeNode left: AVLTreeNode<T> | null = null right: AVLTreeNode<T> | null = null parent: AVLTreeNode<T> | null = null // height: number = 1 /** 获取每个节点的高度 */ private getHeight(): number { const leftHeight = this.left ? this.left.getHeight(): 0 const rightHeight = this.right ? this.right.getHeight(): 0 return Math.max(leftHeight, rightHeight) + 1 } /** 权重: 平衡因子(左边height - 右边height) */ private getBalanceFactor(): number { const leftHeight = this.left ? this.left.getHeight(): 0 const rightHeight = this.right ? this.right.getHeight(): 0 return leftHeight - rightHeight } /** 直接判断当前节点是否平衡 */ get isBalanced(): boolean { const factor = this.getBalanceFactor() return factor >= -1 && factor <= 1 // -1 0 1 } }
我们一共封装了3个方法，分别用于：获取节点高度，给节点设置权重值以及判断当前节点是否平衡。
获取节点的高度有一种方式，新增height属性，用于存储节点所处的高度，默认值为1（即AVL树只有根节点时，根节点同时也是叶子节点，所处的高度为1）。通过不断的计算节点所处的高度，修改height属性来为每一个节点赋值。
但通过新增height属性来获取节点高度的维护比较困难，因为每添加一个子节点，就需要重新计算一次高度，如果高度增加就更新height属性，高度不变就保持。
所以我们采用另一种方式来获取节点高度。已知节点高度是节点自身的左右子节点高度取高的那一个加1。如图10-5所示，节点75的高度取决于左右叶子节点65和85的高度（叶子节点高度为0，所以节点75高度为1），而节点50的高度取决于左右节点25和75中，高的一方（节点75）再加1，所以节点50的高度为2。
图10-5 AVL树的节点高度
所以获取高度，我们通过私有工具方法getHeight()来实现（获取获取节点高度主要用于计算节点的权重值，用户不需要使用，因此该方法为私有方法）。使用递归获取左右节点高度，然后读取高度更高的一侧节点加1，即获取目标节点的高度。PS：高度是相对的数值，叶子节点的高度可以为0为1，也可以为其余任何值，节点之间的高度是相对的，不影响计算。
▼typescript复制代码/** 获取每个节点的高度 */ private getHeight(): number { // 获取当前节点的左子节点，直到读取到叶子节点为止，并给叶子节点赋值高度0 const leftHeight = this.left ? this.left.getHeight(): 0 const rightHeight = this.right ? this.right.getHeight(): 0 return Math.max(leftHeight, rightHeight) + 1 // 叶子节点高度为1 }
通过递归方式实现的 getHeight() 方法，即一个节点的高度等于其左右子节点高度的最大值再加1。这种做法不需要在节点中额外维护高度状态，节点的高度完全由当前树的结构自然推导而来，因此逻辑非常直观，也更不容易因遗漏更新而引入错误。从理解和学习的角度看，它能够帮助开发者真正把“高度是结构的派生结果”这一概念内化，而不是把高度误认为节点的固有属性。
相比之下，通过在节点中维护 height 属性虽然在性能上更优，但需要在插入、删除和旋转等操作中小心翼翼地同步更新高度，一旦某个步骤遗漏就可能破坏平衡判断。递归 getHeight() 的优势并不体现在运行效率上，而体现在实现的纯粹性和安全性上：高度始终与当前结构保持一致，不依赖历史状态（不引入额外状态，节点只关系左右节点是谁，高度完全由结构决定，不存在忘记更新height属性，更新顺序错误或者旋转后高度不同步等问题）。在学习 AVL 树原理和验证旋转逻辑正确性的阶段，这种方式更有利于建立清晰、可靠的认知基础（不变式更少，Bug 更难产生），随后再引入 height 属性作为性能优化，会更加水到渠成。PS：height属性的做法更侧重性能，是标准AVL树的实现，但理解难度相对更高。
获取节点高度这件事情，需要用来计算节点的平衡因子才有意义。通过 getHeight() 方法可以获取目标节点的左右子节点高度。目标节点的平衡因子计算公式是：左子节点-右子节点，得出的差值为平衡因子。在此代码的编写中，获取leftHeight和rightHeight是可以抽象封装的，等下会进行优化。
▼typescript复制代码/** 权重: 平衡因子(左边height - 右边height) */ getBalanceFactor(): number { const leftHeight = this.left ? this.left.getHeight(): 0 const rightHeight = this.right ? this.right.getHeight(): 0 return leftHeight - rightHeight }
生成一棵比较极端的二叉搜索树（一棵明显向右倾斜的二叉搜索树），根节点为 10，其右子节点为 15，而节点 15 又只有一个右子节点 20。在当前高度定义下（空节点高度为 0，节点高度为其左右子树高度的最大值加 1），节点 20 为叶子节点，其高度为 1；节点 15 的右子树高度为 1、左子树为空，因此其高度为 2；根节点 10 的右子树高度为 2、左子树为空，高度为 3。
按照平衡因子的定义（左子树高度减去右子树高度），根节点 10 的平衡因子为 0 − 2 = -2，已经超出 AVL 树允许的取值范围 [-1, 1]，因此该节点处于失衡状态。
▼typescript复制代码const avlNode1 = new AVLTreeNode(10) avlNode1.right = new AVLTreeNode(15) avlNode1.right.right = new AVLTreeNode(20) // 测试平衡因子(权值) console.log(avlNode1.getBalanceFactor()) // -2
所以我们可以通过getBalanceFactor()方法来判断当前二叉树是否处于平衡状态。但在这里，我们还需要基于getBalanceFactor()方法再封装一层，因为getBalanceFactor()方法返回的是具体的权值，还需要比对是否在AVL 树允许的取值范围 [-1, 1]内，而我们需要的是该节点是否处于失衡状态的结果（以布尔值作为返回结果）。通过get语法来反映内部变量的状态，无需使用显式方法调用。
▼typescript复制代码/** 直接判断当前节点是否平衡 */ get isBalanced(): boolean { const factor = this.getBalanceFactor() // factor在[-1，1]之间才是平衡的，返回true，否则返回false。 return factor >= -1 && factor <= 1 // -1 0 1 } // 直接获取到一个节点目前是否平衡 console.log(avlNode1.isBalanced) console.log(avlNode1.right.isBalanced)
我们可以通过isBalanced来获取一个节点是否处于平衡状态。如果目标节点处于失衡状态，到时候AVL树要旋转时，要以谁为中心？isBalanced本身并不决定“从哪里旋转”，决定从哪旋转的是轴心（枢轴点）。如图10-5所示的AVL树中，不平衡的节点是根节点，平衡因子为2，依靠直觉的判断，旋转要以节点3作为轴心来旋转，从而形式根节点3，左节点2以及右节点5的AVL树，达成平衡状态。
图10-5 AVL树的旋转枢轴点
可在计算机中，一切都是必须明确的，不能依靠直觉，我怎么知道要以失衡节点的左子节点还是右子节点为轴心？这是已经有前人总结规律了，找失衡节点的轴心，是去找失衡节点的左右子节点中，高度更高的那一个子节点。
在 AVL 树中，旋转并不是凭经验或直觉进行的，而是由失衡产生的因果关系严格决定的。当插入或删除一个节点时，树的高度变化只会沿着一条从操作位置向上回溯的路径传播。因此，当某个节点第一次出现平衡因子绝对值大于 1 时，说明它的左右子树中，必然有一侧的高度发生了异常增长或缩减，从而打破了原有的平衡状态。
所谓“轴心（枢轴点）”，正是这次高度变化的直接来源。如果失衡节点的左子树高度更高，说明高度变化来自左子树；反之，若右子树高度更高，则变化来自右子树。旋转操作的目的，是压缩这条过长的高度路径，而不是去调整与失衡无关的那一侧。因此，轴心只能选取失衡节点左右子节点中高度更高的那个节点，这是由失衡形成的物理原因所决定的，而非人为设定的规则。
这一原则将人类对树结构“向哪边歪了”的直觉判断，转化为计算机可以明确执行的算法逻辑。通过比较失衡节点左右子节点的高度，程序就能确定旋转的轴心，从而围绕导致失衡的那条路径进行局部结构重排。正是这种以“高度变化来源”为核心的旋转策略，保证了 AVL 树能够用有限且确定的旋转操作，稳定地恢复平衡状态。
所以，我们要封装higherChild()方法，用于获取目标节点中，左右子节点高度更高的那一个子节点。先同时获取目标节点的左右子节点高度，然后返回高度更高的那一个子节点。同时添加边界判断，当左右子节点高度相等时，可以直接返回null，一般情况下，是不会来到该边界判断的，因为只有失衡情况，我们才会调用该方法。但AVL树有一个默认规范，假如目标节点是左节点，那我们就返回目标节点的左节点，反之返回右节点。这是一种延续之前变化的做法。
▼typescript复制代码/** 获取更高子节点 */ public get higherChild(): AVLTreeNode<T> | null { const leftHeight = this.left ? this.left.getHeight(): 0 const rightHeight = this.right ? this.right.getHeight(): 0 if (leftHeight > rightHeight) return this.left if (leftHeight < rightHeight) return this.right // 判断父节点是否为左节点，是则返回父节点的左节点，反之返回右节点 return this.isLeft ? this.left: this.right }
AVL树确认了轴心就可以旋转了，但要往哪边旋转？在 AVL 树中，当失衡节点和轴心（Pivot）已经确定后，旋转方向其实已经隐含在树的结构之中。失衡节点之所以失衡，是因为某一侧子树高度异常增长，而轴心正是这次高度增长的来源节点。旋转的目的，并不是简单地“换个位置”，而是通过结构重排，将这条过长的高度路径向中间压缩，从而恢复左右子树高度的平衡。
具体来说，旋转方向永远与失衡的方向相反。如果失衡节点的左子树更高，说明树在结构上向左倾斜，此时必须通过一次“向右的旋转”来抵消这种左倾；反之，如果右子树更高，则通过一次“向左的旋转”来修正右倾。这种“向高的一侧反方向旋转”的原则，确保旋转操作能够直接作用在造成失衡的那条最长路径上，而不是对无关结构做无效调整。
在更复杂的情形下（如 LR 或 RL 型失衡），虽然需要两次旋转，但方向判断的本质并没有变化：第一次旋转用于修正轴心内部的倾斜方向，第二次旋转用于修正失衡节点整体的倾斜方向。因此，无论是单旋转还是双旋转，旋转方向始终由高度增长路径决定，而不是人为指定。正是这种由结构关系自动推导出的旋转方向，使 AVL 树的平衡修复过程既确定又可预测。
10.2.5 AVL树的旋转
如果你是从10.2.2小节直接跳到这一小节，那么需要思考是否想清楚那一小节最后的3个问题：
（1）什么时候旋转？PS：你是否掌握权衡因子以及平衡状态。
（2）从哪个节点旋转？PS：你是否掌握判断枢轴点。
（3）转左边还是转右边？PS：你是否理解旋转的本质是为了调整失衡的最长路径。
如果你都已经了解，那么可以开始对AVL树的旋转学习。在开始之前，我们重温一些重要的概念：首先，旋转并不是重新插入节点或打乱树的有序性，而是一种局部的结构调整：它只发生在失衡节点及其相邻子节点之间，作用范围极小。无论进行哪种旋转，树的中序遍历顺序始终保持不变，因此旋转前后都仍然是一棵合法的二叉搜索树。
其次，AVL 树的旋转是确定性的，而不是试探性的。一旦通过平衡因子确定了失衡节点、轴心以及失衡类型（LL、LR、RR、RL），旋转方式和方向就已经唯一确定，不存在多种可选方案。旋转的目标也非常明确：压缩导致失衡的那条最长高度路径，使左右子树的高度重新回到允许范围内。只要牢记“旋转围绕失衡节点展开、轴心来自高度增长方向、旋转方向与失衡方向相反”这几个基本原则，后续理解任何具体旋转步骤都会变得顺理成章。
10.2.5.1 左左情况分析
AVL树的左左情况如图10-6所示，左左情况即LL（Left-Left）型失衡，在该情况下，我们需要采用右旋转来让AVL树恢复平衡。
图10-6 AVL树-左左情况
在此图片中的A、B、C、D是可能存在的节点，但为什么要画出可能存在的节点，只考虑失衡节点所处路径的已有节点不行吗？这是一个非常关键、而且非常“算法思维”的问题，画出 A、B、C、D 并不是为了当前这棵树，而是为了证明：旋转在“所有可能的子树形态下”都成立且安全。
在讲解 AVL 树旋转时，如果只画出当前已经存在的节点，很容易让人误以为：旋转只在“这种具体形态”下才正确。但在真实的 AVL 树中，失衡节点附近并不只包含图中标出的那几个关键节点，它们的左右两侧随时可能还挂着其他子树。这些子树在旋转时既不能被丢失（例如旋转前的节点3的右子节点B），也不能破坏二叉搜索树的有序性，因此在示意图中必须用 A、B、C、D 把这些“可能存在的子树”明确标出来。
更重要的是，A、B、C、D 的存在，是为了说明旋转并不是“换几个节点位置”这么简单，而是一种保持中序顺序不变的结构重排。无论这些子树是否为空，旋转前后的中序遍历顺序都必须保持一致：D < 2 < C < 3 < B < 5 < A。
画出这些子树，正是在强调这一点——旋转过程中，节点的相对大小关系没有被破坏，只是重新分配了父子关系。如果不把 A、B、C、D 画出来，我们很容易忽略这一不变式，从而对“旋转为什么是安全的”产生疑惑。
从算法设计的角度看，AVL 树的旋转是一种通用规则。画出可能存在的节点，说明这些子树是否存在、形态如何，旋转规则都同样适用。这正是算法严谨性的体现：它不依赖当前数据的偶然形态，而对所有合法情况都成立。
如图10-6是如何判断左左情况的？关键不在于节点的数量或外形是否“向左偏”，而在于高度变化的传播路径。图中最上方的失衡节点是根节点 5，可以看到它的左子树高度明显大于右子树，说明失衡首先发生在左侧，这是第一个 “Left”。
继续沿着高度增长的方向向下观察，5 的左子节点 3 同样是其左子树高度更高，真正导致高度继续增加的是 3 的左子节点 2 这一侧，而非右侧子树。也就是说，高度变化路径呈现为 “左 → 左” 的连续方向。因此，该结构满足左子树的左子树导致失衡的特征，属于典型的 LL（Left-Left）型失衡。
在判断4种类型失衡时，最有意思的地方来了，只需要看这两个地方就能决定旋转并恢复二叉搜索树的平衡了？如果这是一个更复杂的二叉搜索树，有更多的节点，不会影响我们的判断吗？因为一次插入或删除，只会让“一条路径”的高度发生变化，失衡类型正是由这条路径在失衡节点处的前两步方向唯一决定的（这里的局部信号决定了全局）。
在 AVL 树中，无论整棵树多么复杂，插入或删除操作对高度的影响都具有一个重要特性：高度变化只会沿着从操作位置到根节点的一条路径向上传播。其他不在这条路径上的子树，其结构和高度在这次操作中完全不会发生改变。因此，当某个节点第一次出现失衡时，真正“参与造成失衡”的信息，只存在于这条高度变化路径上。
对于这个失衡节点而言，判断失衡类型只需要关注两层关系：高度是从哪一侧子树传上来的（左还是右），以及在该子树内部，高度又是来自它的哪一侧（左还是右）。这两次方向选择，已经完整描述了高度增长路径在该节点附近的形态，也就唯一确定了失衡类型是 LL、LR、RR 还是 RL。再往下的节点虽然可能存在，但它们只是在这条路径上继续延伸，并不会改变“先左还是先右”的方向组合。
因此，即便二叉搜索树结构再复杂，节点数量再多，在判断失衡类型时也无需关心更深层的细节。AVL 树的旋转本质上是对最小失衡子树进行修复，只要把这条路径在失衡节点附近“压短”，更高层的结构自然会随之恢复平衡。这也是 AVL 树能够通过局部旋转解决全局高度问题的根本原因。
在了解4种失衡类型的原理后，能得出结论：只需要找到失衡节点，后续所有操作都可以顺理成章的进行下去，所以失衡节点是绝对的关键，要旋转就第一时间找失衡节点（就像理清毛线球，第一时间找线头）。自己推理出结论和直接获取结论的意义是不一样的，会记得更牢固。
10.2.5.2 右旋转的情况分析
现在，我们来分析AVL树-左左情况的具体右旋转操作（以图10-6举例）。在 AVL 树的左左（LL）型失衡中，需要对失衡节点执行一次右旋转。以图 10-6 为例，原本的失衡节点为 5，其左子节点 3 作为枢轴点参与旋转。右旋转的核心过程是：将节点 3 上移，成为新的子树根节点；同时，原根节点 5 下移，成为 3 的右子节点。为了保持二叉搜索树的有序性，3 原本的右子树 B 被重新挂接为 5 的左子树。
右旋转最大的变化，是对右子树B的迁移，这一点在逻辑推理与代码中均是重要体现。
旋转完成后，新的结构以节点 3 为根，左侧保持原有的左子树结构，右侧则由节点 5 及其子树组成。整个过程中，中序遍历顺序保持不变，但失衡节点处过长的左侧高度被有效压缩，从而恢复了 AVL 树的平衡状态。
10.2.5.3 右旋转的伪代码逻辑
所以AVL树的右旋转，主要实现步骤为以下3大步，每大步再具体细分：
- 处理pivot的位置。
（1）选择当前节点（失衡节点）的左子节点作为旋转轴心（pivot）。
（2）pivot的父节点指向this（root）的父节点。PS：this节点是当前节点（失衡节点）。
- 处理pivot右子节点的位置。PS：AVL树旋转的重要变化。
（3）this（root）当前节点的左子节点，指向pivot的右子节点。PS：右子树B（pivot的右子节点）有可能为空，为空则无需处理。
（4）如果pivot的右子节点有值，那么右子节点的父节点指向this节点。PS：这一步要在（5）之前完成，否则 pivot.right 会被覆盖。
- 处理this节点的位置。
（5）pivot的右子节点指向this节点。
（6）this节点的父节点指向pivot。
（7）判断是否有父节点，父节点的left/rigth指向pivot。PS：失衡节点如果是根节点的话，根节点是没有父节点。这一点需要注意分情况讨论。
AVL 树的右旋转虽然步骤较多，但逻辑是固定且可复用的。总结下来，就是先处理枢轴点，然后处理枢轴点可能存在的右子树，最后处理失衡节点。严谨的说则是：先确定并上移枢轴点（pivot），再妥善安置枢轴点可能存在的右子树，最后将失衡节点下沉并完成父子关系的重新挂接。只要熟悉这一流程，在实际实现中就可以像模板一样直接套用，而不需要每次重新推导结构。
之所以必须采用这种处理顺序，是因为旋转过程中存在严格的依赖关系。枢轴点是新的子树根，必须最先确立其父子关系，否则后续节点将无从挂接；而枢轴点的右子树在旋转后会变成失衡节点的左子树，如果不提前处理，就可能在指针重排时丢失或覆盖这棵子树；最后再处理失衡节点的位置，才能确保整个旋转过程中所有节点始终“有处可去”，不会出现悬空引用或结构断裂。换句话说，这种顺序并非人为约定，而是为了在每一步都保持二叉搜索树的结构和有序性不被破坏，是一种最安全、最自然的旋转执行路径。
10.2.5.4 右旋转代码实现
将右旋转代码分4个部分，分别实现。
▼typescript复制代码rightRotation() { // 1. 处理pivot节点 // 2. 处理pivot节点的右子节点right // 3. 处理this // 4. 挂载pivot }
部分1：处理pivot节点，即枢轴点。在右旋转的情况中，枢轴点位于失衡节点的左子节点。且由于我们是通过失衡节点来调用rightRotation()方法的，所以可以利用this获取失衡节点，通过this.left获取失衡节点的左子节点（枢轴点）。PS：一切都是基于右旋转的情况，即失衡节点的左侧不平衡，因此枢轴点一定位于失衡节点左侧并且有具体的值。
获取枢轴点（pivot节点），将枢轴点的父节点指向失衡节点的父节点。
▼typescript复制代码rightRotation() { // 1. 处理pivot节点 const pivot = this.left! pivot.parent = this.parent }
部分2：处理pivot的right，即枢轴点的右子树。失衡节点的原左子节点是枢轴点，但由于枢轴点已改变父节点（父节点不再是失衡节点），所以失衡节点的左子节点可以存放新的节点并且不出问题。
右子树并不一定存在（一种可能性），所以需要判断是否存在，存在则将枢轴点的右子树接续到失衡节点的左子节点。并且节点之间是互相指向，即A指向B，B也应该指向A。当右子树确实存在时，右子树的父节点应该直接指向this失衡节点，而非原先的枢轴点。
▼typescript复制代码rightRotation() { // 2. 处理pivot节点的右子节点right this.left = pivot.right if (pivot.right) { pivot.right.parent = this } }
部分3：处理this失衡节点（在上述案例中的失衡节点是根节点root，但失衡节点也可能是其他节点）。将失衡节点挂载到枢轴点的右子节点（原先右子树的位置）。这里一共两步操作（双向对应操作），枢轴点的右子节点为失衡节点，失衡节点的父节点为枢轴点。
▼typescript复制代码rightRotation() { // 3.处理this pivot.right = this this.parent = pivot }
部分4：最后需要挂载pivot节点（枢轴点），pivot节点一共3种情况（具体取决于失衡节点原本的位置情况）：
（1）pivot节点最终是作为根节点。PS：即我们这次的案例事件，枢轴点取代了原先的根节点位置（失衡节点）。
（2）pivot节点最终是作为原失衡节点父节点的左子节点。PS：失衡节点也不一定是根节点，所以pivot节点最终取代的也不一定是根节点。
（3）pivot节点最终是作为原失衡节点父节点的右子节点。
此时刻，pivot节点的父节点已经完成替换（指向失衡节点的父节点），我们还需要做一件事情，将失衡节点的父节点的左/右子节点指向pivot节点，从而实现双向指向。但我们要如何获取失衡节点是位于父节点的左子节点还是右子节点？
（1）通过pivot节点。
（2）通过失衡节点。
答案是通过失衡节点，因为此时父节点还未指向pivot节点，如果我们查找pivot父节点的左右子节点，只能找到失衡节点。而我们的isLeft和isRight是根据当前节点与父节点的左右子节点进行比较来确认位置的。所以pivot要作为父节点的左子节点还是右子节点，需要通过失衡节点来获取正确位置，在代码中通过this就能访问失衡节点，this.isLeft和this.isRight来访问失衡节点作为父节点的左子节点还是右子节点。
由于this在部分3已经被处理了，因此在部分3之前（获取属性节点之类的，通常在最前列先写）通过常量先将失衡节点的isLeft和isRight这两个判断结果保存下来。
▼typescript复制代码rightRotation() { const isLeft = this.isLeft const isRight = this.isRight // 4.挂载pivot if (!pivot.parent) { // pivot直接作为tree的根 return pivot } else if (isLeft) { // pivot作为父节点的左子节点 pivot.parent.left = pivot } else if (isRight) { // pivot作为父节点的右子节点 pivot.parent.right = pivot } }
最终完整代码如下。
▼typescript复制代码/** 旋转操作: 右旋转 */ rightRotation() { const isLeft = this.isLeft const isRight = this.isRight // 1.处理pivot节点 const pivot = this.left! pivot.parent = this.parent // 2.处理pivot的right this.left = pivot.right if (pivot.right) { pivot.right.parent = this } // 3.处理this pivot.right = this this.parent = pivot // 4.挂载pivot if (!pivot.parent) { // pivot直接作为tree的根 return pivot } else if (isLeft) { // pivot作为父节点的左子节点 pivot.parent.left = pivot } else if (isRight) { // pivot作为父节点的右子节点 pivot.parent.right = pivot } return pivot }
如果想对右旋转进行测试，是比较麻烦的。因为AVL树的每个节点暂时都还没有设置parent属性，所以没办法拿到失衡节点的父节点（其实是每个节点的父节点都暂时拿不到）。如果想测试，就需要手动的设置parent属性。但实际并不会如此麻烦，因为AVL树是由一棵空树一次次的插入操作逐渐完善的，我们只需要在插入操作中的第一步（根据传入value创建Node(TreeNode)节点）之后，给新加的节点加上parent属性就行了。
通过正规的方式，AVL树的每个节点都可以拥有parent属性，所以是可以完成右旋转操作的。
▼typescript复制代码// 内容回顾 /** 插入数据的操作 */ insert(value: T) { // 1.根据传入value创建Node(TreeNode)节点 const newNode = this.createNode(value) // 设置parent属性 // 2.判断当前是否已经有了根节点 if (!this.root) { // 当前树为空 this.root = newNode } else { // 树中已经有其他值 this.insertNode(this.root, newNode) } // 3.检测树是否平衡 this.checkBalance(newNode) }
10.2.5.5 左旋转逻辑分析
与左左情况相对应的是右右情况，他们都是存粹的右旋转与左旋转，而非两者兼备。在理清左左情况之后，右右情况是否也是逻辑类似，只不过由于旋转方向不同，所导致的处理顺序和节点不太一致。
根据平衡因子，可得出关键信息如下2点：
（1）失衡节点：3。
（2）枢轴点：5。
AVL树的左旋转用于修复右右（RR）型失衡。当失衡节点的右子树高度过高，且高度来自右子节点的右侧时，选择该右子节点作为枢轴点（pivot），将其上移成为新的子树根；同时，枢轴点原本的左子树被重新挂接为失衡节点的右子树；最后，失衡节点下沉为枢轴点的左子节点并完成父子关系的重连。AVL树的左旋转调整如图10-7所示。
图10-7 AVL树-右右情况
所以AVL树左旋转的实现步骤与右旋转是一致的。不同之处在于左旋转处理枢轴点的右子树，右旋转处理枢轴点的左子树。
▼typescript复制代码leftRotation() { const isLeft = this.isLeft const isRight = this.isRight // 1.处理pivot const pivot = this.right! pivot.parent = this.parent // 2.处理pivot的left this.right = pivot.left if (pivot.left) { pivot.left.parent = this } // 3.处理root(this) pivot.left = this this.parent = pivot // 4.挂载整颗子树pivot if (!pivot.parent) { return pivot } else if (isLeft) { pivot.parent.left = pivot } else if (isRight) { pivot.parent.right = pivot } return pivot }
AVL树的AVLTreeNode节点完整代码如下。
▼typescript复制代码class AVLTreeNode<T> extends TreeNode<T> { // 保证获取到的left/right节点的类型是AVLTreeNode left: AVLTreeNode<T> | null = null right: AVLTreeNode<T> | null = null parent: AVLTreeNode<T> | null = null /** 获取每个节点的高度 */ private getHeight(): number { // 获取当前节点的左子节点，直到读取到叶子节点为止，并给叶子节点赋值高度0 const leftHeight = this.left ? this.left.getHeight() : 0 const rightHeight = this.right ? this.right.getHeight() : 0 return Math.max(leftHeight, rightHeight) + 1 // 叶子节点高度为1 } /** 权重: 平衡因子(左边height - 右边height) */ getBalanceFactor(): number { // 在该计算中，叶子节点高度为0（不为1），但不影响计算 const leftHeight = this.left ? this.left.getHeight() : 0 const rightHeight = this.right ? this.right.getHeight() : 0 return leftHeight - rightHeight } /** 直接判断当前节点是否平衡 */ get isBalanced(): boolean { const factor = this.getBalanceFactor() return factor >= -1 && factor <= 1 // -1 0 1 // return Math.abs(factor) <= 1 } /** 获取更高子节点 */ public get higherChild(): AVLTreeNode<T> | null { const leftHeight = this.left ? this.left.getHeight() : 0 const rightHeight = this.right ? this.right.getHeight() : 0 if (leftHeight > rightHeight) return this.left if (leftHeight < rightHeight) return this.right return this.isLeft ? this.left : this.right } /** 旋转操作: 右旋转 */ rightRotation() { const isLeft = this.isLeft const isRight = this.isRight // 1.处理pivot节点 const pivot = this.left! pivot.parent = this.parent // 2.处理pivot的right this.left = pivot.right if (pivot.right) { pivot.right.parent = this } // 3.处理this pivot.right = this this.parent = pivot // 4.挂载pivot if (!pivot.parent) { // pivot直接作为tree的根 return pivot } else if (isLeft) { // pivot作为父节点的左子节点 pivot.parent.left = pivot } else if (isRight) { // pivot作为父节点的右子节点 pivot.parent.right = pivot } return pivot } leftRotation() { const isLeft = this.isLeft const isRight = this.isRight // 1.处理pivot const pivot = this.right! pivot.parent = this.parent // 2.处理pivot的left this.right = pivot.left if (pivot.left) { pivot.left.parent = this } // 3.处理root(this) pivot.left = this this.parent = pivot // 4.挂载整颗子树pivot if (!pivot.parent) { return pivot } else if (isLeft) { pivot.parent.left = pivot } else if (isRight) { pivot.parent.right = pivot } return pivot } }
10.2.6 4种失衡处理
到目前为止，我们已经实现了两种基础旋转：右旋 rightRotation()（用于 LL 直线型失衡）与左旋 leftRotation()（用于 RR 直线型失衡）。接下来要完成的“步骤三”，并不是再发明新的旋转动作，而是把它们组合起来，形成四种失衡方向对应的四种旋转策略：LL、LR、RR、RL。其中 LL 与 RR 只需要一次旋转；LR 与 RL 属于折线型失衡，需要两次旋转（先把折线“拉直”，再做一次整体旋转），因此本质上仍然是对 rightRotation() 和 leftRotation() 的恰当调用与组合。
需要特别澄清的是：旋转虽然看起来像是在“调整整棵 AVL 树”，但在实现上它只作用于某个最小失衡子树。因此我们把 rightRotation() 和 leftRotation() 设计为“节点方法”是合理的——它们负责完成以某个失衡节点为根的局部重构，并返回该局部子树旋转后的新根节点。然而，决定何时旋转、对哪个节点旋转、以及旋转后的新根如何挂回整棵树，这些都是“树级别”的职责，不能靠节点自己完成。换句话说：节点负责“怎么转”，AVL 树负责“什么时候转、转哪里、转完怎么接回去”。
因此，下一步需要封装一个 AVLTree（或 AVLTree）类，持有整棵树的 root，并在其中实现插入方法 insert()。只有实现插入（以及后续的删除），我们才能在每次结构性修改后沿路径回溯，更新高度/平衡因子，找到第一个失衡节点，并依据其失衡方向（LL/LR/RR/RL）调用 rightRotation() 与 leftRotation() 完成修复。也就是说：先有树结构与插入流程，才有“根据四种失衡情况选择旋转”的触发时机与落点，旋转逻辑才能真正跑起来，成为一棵完整可用的 AVL 树。
AVL树直接继承自之前实现的二叉搜索树。
▼typescript复制代码import { BSTree } from "./00_二叉搜索树BSTree"; class AVLTree<T> extends BSTree<T> { } const avlTree = new AVLTree<number>()
由于AVL树直接继承自二叉搜索树，所以哪怕AVL树暂时只有一个空框架，也可以正常使用。但为了契合AVL树的特性（自平衡），还是需要做一些调整。例如在10.2.5.5小节中，有说明节点暂时没有parent属性，需要通过插入方法来补充。
这里有一个抉择，是要先完成插入方法来实现一棵AVL树还是先完成4种失衡情况的处理？
- 其实都可以，如果我们是自行推演，基本上就需要先完成插入方法。先让插入流程跑通并能回溯定位失衡点，再实现四种失衡选择与组合旋转；否则会在缺少上下文的情况下“写不完整、写了也用不上”。如果先写4种失衡处理，只能写成一堆“给定 root/pivot 的手工旋转演示”，最后仍然要回头补：如何在插入时找到这些节点、如何维护parent、旋转后如何把新的子树根接回去（尤其是处理旋转节点原来在父节点的 left 还是 right、以及旋转发生在根节点时更新 tree.root）。这会导致写的失衡处理代码缺少真实调用场景，容易反复改动。
- 比较合理的推进顺序可以是：先搭好 AVLTree 框架（root、节点带 parent、基础 BST 插入），让插入至少能把节点按 BST 规则挂上并补齐 parent；然后在插入的回溯阶段加入 rebalanceFrom(node) 这样的树级方法：沿父链向上更新高度/平衡因子，遇到第一个失衡节点就根据（LL/LR/RR/RL）调用已经写好的 rightRotation()/leftRotation()（节点方法），并把旋转后的新子树根接回到父节点或更新根。这样写“四种失衡处理”时，每一行代码都有明确的触发时机与输入输出，整体会顺很多，也更不容易返工。
但我们不是开拓者，AVL树的前路都已经被踏平了，我们只需要沿着已经完善的AVL树进行学习，并不会反复改动。因此在这里先完成4种失衡情况的处理。这种想法在学习层面是合理的，尤其当我们的目标是“把AVL树的旋转规则彻底搞明白”，而不是立刻做出一棵可用的 AVLTree。先把 LL/LR/RR/RL 的判定与对应旋转组合写清楚（哪怕暂时是伪代码或只接受 root/pivot 的函数），能减少在实现细节（parent、回溯、挂接）上的干扰，让注意力集中在“为什么这样转、该怎么转”这条主线。
4种失衡情况如图10-4所示。我们需要了解左右情况和右左情况要如何旋转。PS：其实这两者差不多，了解其中一个就行，以左右情况为例。
左右情况-LR（Left-Right）型失衡如图10-8所示，需要先左旋转再右旋转。
图10-8 左右情况-LR（Left-Right）型失衡
从图10-8可以看出，失衡节点只有根节点5，则枢轴点是节点3。可为什么在第一次左旋转时，是以节点3作为失衡节点，以节点4作为枢轴点？这正是左右情况所需要理解的概念。
在AVL树中，一次旋转（无论左旋还是右旋）本质上只能解决一种问题：把同一方向上连续增长的高度压短。这也是为什么 LL 和 RR 这类“直线型失衡”可以通过一次旋转恢复平衡——它们的高度增长路径在结构上是一条单向的直线。
重复一遍，一次旋转只能压短一条直线路径。而在 LR（或 RL）型失衡中，高度增长路径是折线型的，例如 LR 情况下路径是“左 → 右”。这意味着失衡并不是简单地向某一侧倾斜，而是先向左、再向右发生了转折。如果此时强行对失衡节点做一次单旋转，只能消除其中一个方向的倾斜，另一侧的高度问题仍然存在，甚至可能引入新的失衡节点。
因此，AVL 树采用“先转直、再压缩”的策略。第一次旋转（对失衡节点的子节点进行旋转）并不是为了立即恢复平衡，而是消除折线结构中的转折点，将高度增长路径转换为直线型结构；第二次旋转才是针对失衡节点本身，执行一次标准的单旋转，将过长的高度路径整体压短。这样分两步处理，才能在不破坏二叉搜索树有序性的前提下，确保所有相关节点的高度同时回到允许范围内。
所以如图10-8所示的第一次左旋转中，节点 3 并不是失衡节点，而是作为“折线转折点”被选为第一次旋转的操作节点。本质是为了将AVL树的高度增长路径转换为直线型结构，方便后续的处理。将AVL树结构的左右情况捋直，可以以折线转折点为界限，捋上方或者下方，将AVL树转变为左左情况或者右右情况。通常捋折线下方会更容易理解，因此我们采用该方法，当左右情况转变为左左情况，就很好处理了。
PS：我想你也注意到了，将AVL树抽象成形状，可以发觉旋转是对树结构的一次弯折，这有利于理解旋转的概念。以枢轴点作为转折点，向左边或者右边掰动。
图10-9 AVL树结构-折线捋直
在理解左右情况之后，右左情况也是一样的，只需要以高度增长路径中的折线转折点作为第一次旋转的操作节点作为第一次旋转的"失衡节点"（折线的转折点）进行右旋转，转变为右右情况之后处理。PS：建议一定要理解如图10-9的抽象形状，再区分4种失衡情况就非常好理解。
10.2.7 失衡处理-代码实现
现在，先假设已经找到不平衡的节点，要让该节点变得平衡。
▼typescript复制代码import { BSTree } from "./00_二叉搜索树BSTree"; class AVLTree<T> extends BSTree<T> { // 如何去找到不平衡的节点??? 先不管 // 假设已经找到不平衡的节点，那么我们如何让这个节点变得平衡 } const avlTree = new AVLTree<number>()
假设已经找到不平衡的节点了，那我们接下来要让整棵AVL树再次平衡。将使AVL树再次平衡的操作封装为rebalance()方法。
▼typescript复制代码// 假设已经找到了, 那么我们如何让这个节点变的平衡 /** * 根据不平衡的节点的情况(LL/RR/LR/RL)让子树平衡 * @param grand 找到的不平衡的节点 */ rebalance(grand: AVLTreeNode<T>) { }
让整棵AVL树再次平衡所需要的节点一共三个：失衡节点，枢轴点（Pivot），以及第三个节点“枢轴点的子节点”，也就是失衡节点的孙节点，常被称为旋转子节点 / 中间节点 / pivot 的孩子。它并不一定失衡，但它决定了旋转是“直线型”还是“折线型”，从而决定需要一次旋转还是两次旋转。
如果按照如图10-9的抽象概念理解，第三个节点决定了树结构在面临转折点时，是要继续直行还是弯折，从而将两种旋转情况（左左、右右）扩充到了四种（左右，右左）旋转情况。PS：在理解了如图10-9所示的抽象概念后，AVL树的旋转与失衡处理已经对我没有任何难度了，如果你到此刻感受到难度的提升，我建议你可以稍微回头再温习一遍。
好的，调用rebalance()方法需要传入失衡节点。枢轴点为失衡节点的更高子节点，通过在AVLTreeNode节点类封装好的higherChild属性获取。枢轴点的子节点（第三个节点）也是同样的做法，调用枢轴点的higherChild属性获取。
▼typescript复制代码// 让整棵AVL树再次平衡所需要的节点一共三个：失衡节点，枢轴点（Pivot），以及第三个节点“枢轴点的子节点” // 失衡节点：grand rebalance(grand: AVLTreeNode<T>) { // 枢轴点：pivot const pivot = grand.higherChild // 枢轴点的子节点：current const current = pivot?.higherChild }
接着判断4种失衡情况：
（1）枢轴点位于失衡节点的哪一侧？左或者右。
（2）枢轴点的更高子节点位于枢轴点的哪一侧？左或者右。
通过以上两个问题，可以得知失衡情况的4种结合走向，从而针对性处理（使用不同的旋转方式将AVL树实现再平衡）。
▼typescript复制代码rebalance(grand: AVLTreeNode<T>) { const pivot = grand.higherChild const current = pivot?.higherChild if (pivot?.isLeft) { // 左 if (current?.isLeft) { // 左左情况 } else { // 左右情况 } } else { // 右 if (current?.isLeft) { // 右左情况 } else { // 右右情况 } } }
将4种失衡情况分别处理就可以了。4种失衡情况的处理情况如下：
（1）左左情况：以失衡节点为目标节点，右旋转一次。
（2）左右情况：以枢轴点为目标节点，左旋转一次；以失衡节点为目标节点，右旋转一次。
（3）右左情况：以枢轴点为目标节点，右旋转一次；以失衡节点为目标节点，左旋转一次。
（4）右右情况：以失衡节点为目标节点，左旋转一次。
PS：以上4种处理情况的分析，皆是通过图10-9直接理解而来，非死记硬背。
因此，只需要分别以失衡节点与枢轴点为目标节点去调用leftRotation()左旋转方法和rightRotation()右旋转方法，代码如下。
▼typescript复制代码rebalance(grand: AVLTreeNode<T>) { const pivot = grand.higherChild const current = pivot?.higherChild if (pivot?.isLeft) { // 左 if (current?.isLeft) { // 左左情况 grand.rightRotation() // 以失衡节点为目标节点，右旋转一次 } else { // 左右情况 pivot?.leftRotation() // 以枢轴点为目标节点，左旋转一次 grand.rightRotation() // 以失衡节点为目标节点，右旋转一次 } } else { // 右 if (current?.isLeft) { // 右左情况 pivot?.rightRotation() // 以枢轴点为目标节点，右旋转一次 grand.leftRotation() // 以失衡节点为目标节点，左旋转一次 } else { // 右右情况 grand.leftRotation() // 以失衡节点为目标节点，左旋转一次 } } }
在编写左右旋转方法的第4步挂载pivot中（10.2.5.4小节与10.2.5.5小节），当旋转结束后，枢轴点替代了原先失衡节点的位置，需要将枢轴点接到原失衡节点的父节点身上。假如原失衡节点无父节点，则直接返回枢轴点。
此时我们需要在rebalance()方法中，进一步处理假如原失衡节点无父节点的情况（失衡节点为根节点）。调用左/右旋转方法后，会返回枢轴点本身，声明一个resultNode节点变量来接收调用左/右旋转方法后的枢轴点。判断resultNode节点变量是否有父节点（通过parent属性），若resultNode节点无父节点，则说明了原失衡节点无父节点的情况，直接将resultNode节点作为AVL树的根节点。
▼typescript复制代码rebalance(grand: AVLTreeNode<T>) { const pivot = grand.higherChild const current = pivot?.higherChild let resultNode: AVLTreeNode<T> | null = null if (pivot?.isLeft) { if (current?.isLeft) { resultNode = grand.rightRotation() } else { pivot?.leftRotation() resultNode = grand.rightRotation() } } else { if (current?.isLeft) { pivot?.rightRotation() resultNode = grand.leftRotation() } else { resultNode = grand.leftRotation() } // 判断返回的pivot是否有父节点 if (!resultNode.parent) { this.root = resultNode } } }
PS：如果this.root的root报错（无法访问），就将BSTree类种的root属性设置为protected（受保护）而非private（隐私）。
10.2.8 AVL树的插入与再平衡
当AVL树因插入的新节点而导致不平衡（LL失衡），通过旋转操作再平衡如图10-10所示。
图10-10 LL失衡（左左情况）-再平衡过程
我们现在需要回头完成AVL树的插入方法（继承自二叉搜索树的插入方法无法满足需求）。继承的插入方法所创建节点的方式为：
▼typescript复制代码insert(value: T) { // 1.根据传入value创建Node(TreeNode)节点 const newNode = new TreeNode(value) // 省略后续无关操作 }
AVL树的节点是AVLTreeNode，如果按插入方法的原有创建节点方式，所产生的节点不符合AVL树的需求。
对于该情况，为了兼容性（二叉搜索树与AVL树可以共用同一方法），我们就需要将创建节点交给外界决定，不直接在插入方法内写死创建节点。思路想好后，完善代码。
创建受保护（protected）的createNode()方法，该方法唯一作用是返回创建的节点。这么做之后，可以在继承自BSTree类的AVLTreeNode类中，重写createNode()方法，返回类型为AVLTreeNode的节点。
▼typescript复制代码protected createNode(value: T): TreeNode<T> { return new TreeNode(value) } insert(value: T) { // 1.根据传入value创建Node(TreeNode)节点 const newNode = this.createNode(value) // 省略后续无关操作 }
在AVLTree类中，重写调用的createNode()方法如下所示。通过重写将树结构的创建节点类型交给继承自该树的子类，BSTree类的复用性会更强，但也意味着需要我们多分一份心思去关注节点的情况。PS：在AVLTree类中重写的createNode()方法所返回的是AVLTreeNode，而我们通过TypeScript设置的返回类型是TreeNode，而这是没有问题的。因为 AVLTreeNode 是 TreeNode 的子类型，子类方法可以返回“更具体的类型”，这在类型系统中称为“协变返回类型（covariant return type）”，也可以说是多态。在面向对象中，方法重写时允许返回类型变得更具体，只要这个返回值仍然“是父类所期望的那一类对象”。AVLTreeNode 继承自 TreeNode，因此任何 AVLTreeNode 在类型意义上也都是一个 TreeNode，不会破坏父类 BSTree 对返回值的使用假设。
▼typescript复制代码class AVLTree<T> extends BSTree<T> { // 重写调用的createNode方法 protected createNode(value: T): TreeNode<T> { return new AVLTreeNode(value) } // 省略其余内容 }
在完成创建符合情况的节点后，AVL树的插入方法主要做以下3件事情：
（1）给节点添加parent属性，将节点插入到AVL树。
（2）检测插入节点后的AVL树是否平衡，若不平衡，需获得失衡节点。
（3）调用rebalance()方法，传入失衡节点，完成AVL树的再平衡。
第一件事：给节点添加parent属性，方便节点可以找到自身的父节点。根节点无父节点，因此不需要处理根节点。
找到insert()插入方法中的insertNode()插入节点方法处，该方法是找到node节点，将新节点插入到node节点的左边或右边。此时node节点即新节点的父节点，让新节点的parent指向node节点（newNode.parent = node）。
▼typescript复制代码private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) { if (newNode.value < node.value) { // 去左边继续查找空白位置 if (node.left === null) { // node节点的左边已经是空白 node.left = newNode // 设置parent属性 newNode.parent = node } else { this.insertNode(node.left, newNode) } } else { // 去右边继续查找空白位置 if (node.right === null) { node.right = newNode // 设置parent属性 newNode.parent = node } else { this.insertNode(node.right, newNode) } } }
第二件事：插入节点方法完善后，已经具备构成AVL树的基础。每一次插入都需要检测AVL树是否平衡，这句话需要仔细理解，如果我们每次都把整棵AVL树的节点的平衡因子检查一遍，那样的效率很低。我们需要通过尽可能简便的方式来检测AVL树是否平衡以及失衡节点（不平衡的情况）。
插入造成的高度变化只会沿着插入点向上回溯传播，因此失衡节点一定在新节点的祖先链上。我们无需扫描整棵树，只要从新节点的父节点开始逐层向上更新高度与平衡因子，第一个出现失衡的节点就是旋转的根；pivot 与其更高侧子节点也都能由这个失衡节点在局部结构中确定。如果整条祖先链的平衡因子都没有问题，则说明插入新节点后的AVL树依旧保持着平衡。
我们插入节点是在insert()方法中通过递归的寻找AVL树的空白位置来插入。在插入节点之后，就可以立刻向上回溯祖先链来检测平衡因子。这里有两种做法：
（1）在AVLTree类中，重写insert()方法，在insert()方法插入节点之后，检查AVL树是否平衡。
（2）在BSTree类中，调整insert()方法，在AVLTree中去检查AVL树是否平衡。
首先是做法一，检查AVL树是否平衡等同去找到不平衡的节点（找不到就说明AVL树处于平衡），需要封装成一个checkBalance()方法。checkBalance()方法要做的为：通过传入插入AVL树的新节点，通过节点的parent属性向整条祖先链往上攀升，每攀升一次节点就通过isBalanced检查一次平衡因子，如果没有问题就继续递归调用parent属性往上攀升，直到攀升到根节点或者找到了失衡节点，将失衡节点传给rebalance()方法调用旋转操作，实现AVL树的再平衡，通过break结束递归调用（因为已经找到失衡节点并实现AVL树的再平衡，达成目的，无需再向上寻找）。
▼typescript复制代码class AVLTree<T> extends BSTree<T> { insert(value: T) { super.insert(value) // 子类需要有实际的类型提示。 // 检查AVL树是否平衡 } // 如何去找到不平衡的节点 checkBalance(node: AVLTreeNode<T>) { let current = node.parent while (current) { if (!current.isBalanced) { this.rebalance(current) break // 实现AVL树的再平衡，结束递归调用 } current = current.parent } } }
但checkBalance()方法需要我们拿到插入的新节点，而insert()方法是没有返回节点信息的，这需要我们回到insert()返回一下插入的节点，并且将返回的节点类型断言为AVLTreeNode ，因为父类方法的返回类型只保证“最小承诺”，子类在需要使用更具体能力时，必须显式收窄类型。更工程化的做法是让 BSTree 节点类型参数化，以避免类型断言。
▼typescript复制代码class AVLTree<T> extends BSTree<T> { insert(value: T) { const newNode = super.insert(value) as AVLTreeNode<T> this.checkBalance(newNode) return newNode // 在BSTree类的insert方法最后也需要return返回。 } // 如何去找到不平衡的节点 checkBalance(node: AVLTreeNode<T>) { let current = node.parent while (current) { if (!current.isBalanced) { this.rebalance(current) break } current = current.parent } } }
但第一种做法有一个缺点，我们的insert()方法直接将插入的节点返回出去了，那开发者在使用插入方法时，就可以拿到插入的新节点本身。虽然该做法可以完成功能，但我们不应该暴露给外界非必要的节点信息。
此时进行第二种做法，我们不重写insert()方法了，直接在BSTree类的insert()方法中获取插入节点信息，然后"检测"是否平衡。该做法无需返回节点信息，因此不会暴露给外界不必要的内容。
▼typescript复制代码// 请注意，这是是在BSTree类中 protected checkBalance(node: TreeNode<T>, isAdd = true) {} /** 插入数据的操作 */ insert(value: T) { // 1.根据传入value创建Node(TreeNode)节点 const newNode = this.createNode(value) // 2.判断当前是否已经有了根节点 if (!this.root) { // 当前树为空 this.root = newNode } else { // 树中已经有其他值 this.insertNode(this.root, newNode) } // 3.检测树是否平衡 this.checkBalance(newNode) } // 完成以上操作后，无需重写AVLTree类的insert()方法，而是重写checkBalance()方法
在BSTree类中，我通过checkBalance()方法检测了AVL树是否平衡。可普通的二叉搜索树并不需要这一项功能，因此在BSTree类的checkBalance()方法内部是放空的，无实际内容。该做法是为了在AVLTree类中重写checkBalance()方法，在重写的checkBalance()方法中，可以调用传入的参数（即插入的新节点信息），完成AVL树节点的平衡因子检测。
测试代码如下：
▼typescript复制代码const avlTree = new AVLTree<number>() for (let i = 0; i < 20; i++) { avlTree.insert(Math.floor(Math.random() * 200)) } avlTree.print()
10.2.9 AVL树的删除与再平衡
AVL树的删除案例如图10-11所示，假设将红色节点删除，AVL树会呈现失衡状态（RR失衡），在删除操作下，如何完成AVL树的再平衡？
图10-11 AVL树的删除
删除子节点，有可能打破父节点原有的平衡，而对同层级的兄弟节点无影响，需明确问题所在。当删除目标子节点，需从操作位置向上回溯的路径中检测每个节点是否处于失衡状态。若失衡，则对处于失衡状态的节点做出旋转处理；若未失衡，则无需处理。
对于以上思路，需要先获取被删除的子节点，从传入remove()删除方法的值可知所删除的目标节点，可从remove()方法内部定义一个delNode变量用于获取被删除的子节点信息。
▼typescript复制代码remove(value: T): boolean { // 省略其余无关内容 const current = this.searchNode(value) let delNode: TreeNode<T> = current }
但还有一个问题，在图 10-11 所示的结构中，如果删除节点 25，不能简单地将该节点及其子节点一并删除。因为在二叉搜索树（包括 AVL 树）中，删除某个节点时，必须保证原有子树结构被正确保留并重新挂接，而不能破坏整棵树的有序性。
在该例中，节点 25 只有一个子节点 12。根据二叉搜索树的删除规则，当被删除节点只有一个子节点时，应当用其子节点“顶替”被删除节点的位置。因此，正确的做法是：将节点 12 提升到原来 25 所在的位置，即让 50 的左子节点改为指向 12，同时将 12 的 parent 指针更新为 50。这样处理后，整棵树仍然满足二叉搜索树的有序性。如果节点 12 还存在自己的子节点，也应当一并保留，其结构无需额外调整，只需确保父子指针关系正确即可。
在BSTree类的的remove()方法中，current变量是remove()方法所删除的目标节点，而replaceNode是current的子节点（唯一）。因此要做到子节点的“顶替”需要确保两个条件：
（1）被删除的目标节点current存在子节点。PS：即被删除的目标节点不是叶子节点。
（2）被删除的目标节点current存在父节点。
current的子节点与父节点同时存在，才能将current的子节点"顶替"到current原先的位置上。如图10-11所示，假如节点25是被删除的节点current，则replaceNode是节点12，current.parent是节点50。完成筛选判断后，让节点12指向节点50即可。
PS：在remove()方法判断replaceNode之前，已经做到current.parent!.left = replaceNode，即节点50的左子节点指向节点12。因此后续判断replaceNode判断中只是补齐“反向指针”，使其完善。
▼typescript复制代码// 判断replaceNode if (replaceNode && current.parent) { // replaceNode.parent：节点12 // current.parent：节点50 replaceNode.parent = current.parent }
如果被删除的目标节点有前驱节点和后继节点，那需要怎么做？如图10-12所示的删除节点15，存在前驱节点11与后继节点13与20。
图10-12 二叉搜索树-覆盖前（原始状态）
之前的做法是，将节点18放置（覆盖）到被删除节点15的位置，然后将节点20的左子节点指向节点19，操作如图10-13所示。该方式比直接将节点15设置一个isDelete布尔值属性（用于控制是否访问该节点）来得更好，因为设置是否访问节点的做法，无法真正删除节点，删除操作无法让二叉搜索树体积缩小。覆盖虽然也不是完美的方式，但效果一致，并且可以简化较多代码（无需考虑父节点指向问题），因此是一个可行的折中方案。
图10-13 二叉搜索树-覆盖后（节点18顶替节点15，节点19顶替节点18）
采用以上折中方案，需来到BSTree类的remove()方法，修改以下代码。
▼typescript复制代码remove(value: T): boolean { // 省略无关内容 let replaceNode: TreeNode<T> | null = null if (current.left === null && current.right === null) { } else if (current.right === null) { } else if (current.left === null) { } else { // 当被覆盖的节点存在左右子节点 const successor = this.getSuccessor(current) // 继承的节点覆盖被删除的节点 current.value = successor.value } }
同时，需要修改getSuccessor()方法内的部分内容，当我们拿到后继节点18，要对节点18的子节点19处理，替代节点18原有的位置。做出如下4步操作（用图10-13的示例）：
（1）删除successor!.left = delNode.left。该代码作用是将节点15的左子树接到新的替代节点上，但由于采用覆盖做法，只将节点15的值覆盖为18，节点本身无变化，因此无需将节点15的左子树接到新的节点上。
（2）当找到后继节点 18 后，需要处理它在原位置的“补位”问题。由于后继节点是右子树中最小的节点，它一定没有左子节点，但可能存在右子节点（图 10-13 中就是 19）。因此，我们要做的是：让 18 的父节点原本指向 18 的那条边，改为指向 18.right（也就是 19），从而实现“用 19 顶替 18 的位置”。在代码层面就是把 successor.parent.left = successor.right（当 18 不是 delNode.right 时）这一类操作落实到位。
（3）仅仅让父节点改指向还不够，还必须同步修复“反向指针”。也就是说，如果 18 的右子节点 19 存在，那么 19.parent 原本指向 18，现在应该改为指向 18 的父节点。否则树的结构会出现“父节点已经换了孩子，但孩子还以为自己的父亲是旧节点”的断链问题。对应代码就是：if (successor.right) successor.right.parent = successor.parent。这样才能保证父子双向引用一致，后续回溯（尤其 AVL 的再平衡回溯）才不会出错。
（4）最后，需要区分一种特殊情况：当后继节点 18 恰好就是 delNode.right（即后继节点就是被删节点的直接右孩子）时，它并不是某个节点的左孩子，而是 delNode 的右孩子。这时“补位”的连接点不再是 successor.parent.left，而应该直接更新 delNode.right：让 delNode.right = successor.right，并在 successor.right 存在时同步更新其 parent = delNode。这样仍然实现同一个目标：把 18 从原结构中移除，由 19（或空）接管它的位置，同时保持 BST 的有序性与指针完整性。
▼typescript复制代码// 拿到了后继节点 if (successor !== delNode.right) { successor!.parent!.left = successor!.right if (successor?.right) { successor.right.parent = successor.parent } } else { delNode.right = successor!.right if (successor!.right) { successor!.right.parent = delNode } }
当使用remove()方法删除节点后，将后继节点successor赋值到被删除位置的节点就行。并且如果来到最后一种情况（有两个子节点）。
▼typescript复制代码remove(value: T): boolean { // 省略无关内容 let replaceNode: TreeNode<T> | null = null if (current.left === null && current.right === null) { } else if (current.right === null) { } else if (current.left === null) { } else { const successor = this.getSuccessor(current) current.value = successor.value // 给delNode赋值 delNode = successor // 确保删除节点之后的 再平衡没有问题后，返回。 this.checkBalance(delNode, false) return true } }
那不应该让下述代码执行。因为最后一种情况的replaceNode为null，或者用以下两种方式来补充：
（1）在上述delNode = successor之后补充replaceNode = current。
（2）在上述delNode = successor之后补充this.checkBalance(delNode, false)和返回true。采用此方式。
因为节点18替换到节点15之后，只是单纯替换值，无需再让节点11去指向被替换值的节点15。
▼typescript复制代码if (current === this.root) { this.root = replaceNode } else if (current.isLeft) { current.parent!.left = replaceNode } else { current.parent!.right = replaceNode }
AVL树的删除与再平衡就结束了。由于调整原先代码过多，导致思路整体较为复杂，需要额外去多理清两遍。整体代码过多，这里不放出，可以联系我获取完整的代码文件。并且直接替换节点值，保留原先的AVL树指向关系，可以避免去重构节点之间的互相指向问题，节约很多功夫。但由于覆盖节点的方式与一开始的思路不一致，所以在BSTree类，修改了很多内容，这明显带来压力，因此在开写代码之前，想清楚整体结果与做法非常重要，值得多分配一些时间。
remove()方法最终所实现的是两点：
（1）将节点删除。PS：考虑删除节点时，父节点的指向问题需要设置的太多。因此采用覆盖的方式来平替，效果是一致的。覆盖效果是直接用后续节点的value去替代删除节点的value。
（2）删除节点之后的再平衡。PS：checkBalance(delNode)。
10.2.10 AVL树添加和删除的检查平衡区分
在 AVL 树中，“插入”和“删除”都会沿着修改点向上影响祖先节点的高度，但二者对平衡的影响方式不同，因此检查与修复平衡的策略也不同。插入操作会在某条路径上增加高度：从新节点开始向上回溯，某个祖先节点可能首次出现失衡（平衡因子绝对值大于 1）。一旦找到这条回溯链上的第一个失衡节点并完成旋转，局部子树的高度通常会被恢复到插入前的水平或至少不再继续向上增加，从而使更高层祖先节点不再继续恶化。
▼typescript复制代码// 如何去找到不平衡的节点 checkBalance(node: AVLTreeNode<T>, isAdd = true) { let current = node.parent while (current) { if (!current.isBalanced) { this.rebalance(current) // 该位置为旋转完成后的操作 } current = current.parent } }
正因如此，插入场景下常见做法是：第一次旋转修复完成后就可以停止回溯，也就是以下代码中的 if (isAdd) break，避免不必要的继续检查。
▼typescript复制代码// 如何去找到不平衡的节点 checkBalance(node: AVLTreeNode<T>, isAdd = true) { let current = node.parent while (current) { if (!current.isBalanced) { this.rebalance(current) // 这个位置时旋转完成后的操作 // break决定不会进一步去查找父节点有没有平衡的情况了 // 添加的情况是不需要进一步向上查找的, 直接break // 删除的情况是需要进一步向上查找的, 不能break if (isAdd) break } current = current.parent } }
删除操作则不同。删除往往会使某条路径上的高度减少，而这种高度减少可能逐层向上传导，引发“连锁式”的平衡变化：即便在某个节点处通过一次旋转恢复了平衡，旋转后的子树高度仍可能继续降低，进而导致其父节点在随后步骤中变得失衡。因此，删除场景的再平衡不能像插入那样“修一次就结束”，而必须继续沿祖先链向上检查，必要时在多个节点处重复旋转，直到回溯到根节点或整条路径重新稳定为止。这就是 checkBalance(node, isAdd=false) 时不能 break 的根本原因：删除的修复可能需要多次、分层次地进行，才能保证整棵 AVL 树最终恢复平衡。PS：在10.2.9的末尾使用checkBalance的第二参数传入false即是决定是否要在旋转一次后终止继续向上检查。
10.3 红黑树详解
红黑树是数据结构中很难的一个知识点，难到什么程度呢？基本你跟别人聊数据结构的时候, 他不会和你聊红黑树, 因为它是数据结构中一个难点中的难点。数据结构的学习本来就比较难了, 红黑树是又将难度上升一个档次的知识点。
面试的时候经常出现这个场景：
- 面试官: 你知道红黑树吗？
- 面试者: 知道啊。
- 面试官: 知道原理吗？
- 面试者: 不知道啊。
- 面试官: 那你让‘不’过来面试我们公司吧，你先回去等通知吧。
那么哪些面试会出现红黑树相关的题目呢？在面试时基本不会让手写红黑树（即使是面试Google、Apple这样的公司，也很少会出现）。通常是这样问题的（比如腾讯的一次面试题）：为什么已经有平衡二叉树（比如AVL树）了，还需要红黑树呢？
10.3.1 红黑树的五条性质
在所有的二叉查找树中，有一个问题几乎无法回避——树会"长歪"。当数据按顺序插入时，普通的二叉查找树会退化成一条链，查找效率从 O(log n) 跌落至 O(n)。为了解决这个问题，计算机科学家们发明了各种"自平衡"机制，红黑树便是其中最广为人知的一种。它由鲁道夫·贝尔于 1972 年发明，最初被称为"对称二叉 B 树"，直到 1978 年 Leo J. Guibas 与罗伯特·塞奇威克在论文中引入红与黑的染色方案，才有了今天这个更具辨识度的名字。
红黑树本质上仍是一棵二叉查找树，左小右大的基本规则一脉相承。它的特别之处在于，每个节点都被赋予一种颜色——红色或黑色。颜色本身没有任何实际含义，它只是一种编码手段，用来携带关于树结构的元信息，从而让树在插入和删除时能够"感知"自己是否还保持平衡。
要理解红黑树为何能保持平衡，需要先理解它对颜色分布施加的5条约束：
（1）节点只能红色或者黑色。
（2）根节点必须是黑色的，这为整棵树提供了一个稳定的起点。约束二：节点只能红色或者黑色。
（3）每个叶子节点都是黑色的空节点（NIL节点，空节点）。
（4）每个红色节点的两个子节点都是黑色。（换句话说，红色节点不能相邻出现，从叶子节点到根的所有路径上不允许存在两个连续的红色节点）。
（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。这个数量被称为叶子节点的"黑色高度"。
约束3要求每个叶节点（空节点）是黑色的，这是因为在红黑树中，黑色节点的数量表示从根节点到叶子节点的黑色节点数量。这个数量叫做“黑高（black-height）”。为了让这个规则在所有路径上都成立，就必须保证每条路径的终点（NIL）都是黑色。否则，有的路径以黑色结束，有的路径以红色结束，黑色节点数量就无法统一，从而破坏红黑树的平衡约束。
所以最后的NIL节点，是为了让“黑色高度”这个概念在结构上成立（约束5），而"黑色高度"这个概念是为了限制树的高度，使红黑树保持近似平衡。当然，黑色高度只需要概念的存在就可以帮助到我们（因为黑色高度是一种计数规则，规则不依赖真实存在的节点），因此在代码中可以用 null 代替 NIL节点的表达，但在理论分析中必须把它当作黑色节点看待。
约束4和约束5是两条最关键的约束。
这两条规则叠加在一起，产生了一个精妙的效果：假设树中最短的路径全由黑色节点构成，那么最长的路径也不过是黑色与红色交替出现——而由于红色不能连续，最长路径最多是最短路径的两倍。整棵树的高度因此被控制在 O(log n) 的量级之内，平衡性得到了保证。
表面上看，这五条规则繁琐而抽象，像是凭空堆砌的限制。但它们共同指向同一个目标：让树上任何路径的长度不能相差太悬殊。这些规则会让人一头雾水，完成搞不懂规则叠加起来，怎么让一棵树平衡的。但是它们还是被一些聪明的人发明出来了。
图10-14 红黑树示例
红黑树示例如图10-14所示。在红黑树中，所谓“叶子节点”并不是我们通常理解的“没有左右子节点的实际数据节点”，而是指所有的空指针位置。也就是说，每个 null 都被视为一个特殊的节点，称为 NIL 节点。这些 NIL 节点是逻辑上存在的，并且统一规定为黑色。因此，一棵红黑树在结构上，其实是“实节点 + 若干黑色 NIL 节点”共同组成的。
红色节点的作用是让我们尽量少去调整这棵树。
10.3.2 红黑树的相对平衡性
通过10.3.1小节的五条性质，确保了红黑树的关键特性：从根到叶子的最长可能路径, 不会超过最短可能路径的两倍长。结果就是这个树基本是平衡的，虽然也没有做到绝对的平衡，但是可以保证在最坏的情况下, 性能依然是高效的。
最长路径不超过最短路径的两倍，意味着红黑树绝对不可能退化至链表或者近似链表的形态，也是保持树平衡的核心特性，但这个特性是怎么做到的？因为性质5决定了最短路径和最长路径必须有相同的黑色节点：
- 路径最短的情况：全部是黑色节点 n。
- 路径最长的情况：黑色接电的数量也是n，中间全部是红色节点 n – 1。该情况由以下3特性组成：性质2：根节点是黑节点。性质3：叶子节点都是黑节点。性质4：两个红色节点不能相连。
因此最短路径的边为n-1（节点与节点之间的连线视为边），最长路径为（n+n-1）-1 = 2n-2=2（n-1）。所以最长路径一定不超过最短路径的两倍。
10.3.3 手写红黑树
手写一个 TypeScript 红黑树的详细步骤可以像AVL树一样拆分为如下6大步骤：
（1）定义红黑树的节点：定义一个带有键、值、颜色、左子节点、右子节点和父节点的类。
（2）实现左旋操作：将一个节点向左旋转，保持红黑树的性质。
（3）实现右旋操作：将一个节点向右旋转，保持红黑树的性质。
（4）实现插入操作：在红黑树中插入一个新的节点，并保持红黑树的性质。
（5）实现删除操作：从红黑树中删除一个节点，并保持红黑树的性质。
（6）实现修复红黑树性质：在插入或删除操作后，通过旋转和变色来修复红黑树的性质。
其他方法较为简单，可以自行实现。红黑树的完整代码如下（附带注释）。
10.3.3.1 定义红黑树的节点
使用 TypeScript 的泛型编写红黑树的节点。
▼typescript复制代码enum Color { RED, BLACK, } class RedBlackNode<T> { value: T; color: Color; parent: RedBlackNode<T> | null; left: RedBlackNode<T> | null; right: RedBlackNode<T> | null; constructor( value: T, color: Color = Color.RED, parent: RedBlackNode<T> | null = null, left: RedBlackNode<T> | null = null, right: RedBlackNode<T> | null = null ) { this.value = value; this.color = color; this.parent = parent; this.left = left; this.right = right; } }
10.3.3.2 红黑树的结构封装
红黑树的整体结构：
▼typescript复制代码class RedBlackTree<T> { root: RedBlackNode<T> | null = null; // 查找某个节点再红黑树中的最小值 minimum(node: RedBlackNode<T> | null = this.root): RedBlackNode<T> | null { let current = node; while (current && current.left) { current = current.left; } return current; } // 查找红黑树中的某个节点 private search(value: T): RedBlackNode<T> | null { let node = this.root; let parent: RedBlackNode<T> | null = null; while (node) { if (node.value === value) { node.parent = parent; return node; } parent = node; if (value < node.value) { node = node.left; } else { node = node.right; } } return null; } } export {};
10.3.3.3 红黑树的旋转操作
实现左旋转和右旋转操作：
▼typescript复制代码/** * 左旋操作 * * @param node 要进行左旋的结点 */ private leftRotate(node: RedBlackNode<T>) { // 获取 node 的右子节点 let rightChild = node.right!; // 将右子节点的左子节点赋值给 node 的右子节点 node.right = rightChild.left; // 如果右子节点的左子节点不为空，则将右子节点的左子节点的父节点指向 node if (rightChild.left) { rightChild.left.parent = node; } // 将右子节点的父节点指向 node 的父节点 rightChild.parent = node.parent; // 如果 node 的父节点为空，则将右子节点设为根结点 if (!node.parent) { this.root = rightChild; } // 如果 node 是它父节点的左子节点，则将右子节点设为 node 父节点的左子节点 else if (node === node.parent.left) { node.parent.left = rightChild; } // 否则，将右子节点设为 node 父节点的右子节点 else { node.parent.right = rightChild; } // 将 node 的父节点指向 rightChild，并将 rightChild 的左子节点指向 node rightChild.left = node; node.parent = rightChild; } /** * 右旋转 * @param node 旋转节点 */ private rightRotate(node: RedBlackNode<T>) { // 获取旋转节点的左子节点 let leftChild = node.left!; // 将旋转节点的左子节点的右子节点，接到旋转节点的左边 node.left = leftChild.right; // 如果左子节点的右子节点不为空，设置它的父节点为旋转节点 if (leftChild.right) { leftChild.right.parent = node; } // 将左子节点的父节点设为旋转节点的父节点 leftChild.parent = node.parent; // 如果旋转节点的父节点不存在，说明左子节点变成根节点 if (!node.parent) { this.root = leftChild; } else if (node === node.parent.right) { // 如果旋转节点是它父节点的右子节点，将父节点的右子节点设为左子节点 node.parent.right = leftChild; } else { // 如果旋转节点是它父节点的左子节点，将父节点的左子节点设为左子节点 node.parent.left = leftChild; } // 将旋转节点设为左子节点的右子节点 leftChild.right = node; // 将旋转节点的父节点设为左子节点 node.parent = leftChild; }
10.3.3.4 红黑树的插入操作
实现插入操作，并且插入后实现红黑树的平衡和保持性质：
▼typescript复制代码insert(value: T) { // 创建一个新节点 let newNode = new RedBlackNode(value); // 如果红黑树为空，将该节点作为根节点 if (!this.root) { this.root = newNode; // 根节点为黑色 newNode.color = Color.BLACK; return; } // 初始化搜索变量current和parent let current: RedBlackNode<T> | null = this.root; let parent: RedBlackNode<T> | null = null; // 搜索合适的插入位置 while (current) { parent = current; // 如果value小于当前节点，则继续往左子树搜索 if (value < current.value) { current = current.left; // 否则继续往右子树搜索 } else { current = current.right; } } // 将新节点的父节点设置为搜索到的父节点 newNode.parent = parent; // 将新节点插入到合适的位置 if (value < parent!.value) { parent!.left = newNode; } else { parent!.right = newNode; } // 修复插入导致的红黑树性质破坏 this.fixInsertion(newNode); } private fixInsertion(node: RedBlackNode<T>) { // 当父节点存在且颜色为红时 while (node.parent && node.parent.color === Color.RED) { // 获取祖父节点 let grandParent = node.parent.parent!; // 父节点是祖父节点的左子节点 if (node.parent === grandParent.left) { // 获取叔叔节点 let uncle = grandParent.right; // 叔叔节点存在且颜色为红 if (uncle && uncle.color === Color.RED) { // 将父节点颜色改为黑，叔叔节点颜色改为黑，祖父节点颜色改为红，node节点变为祖父节点，继续循环 node.parent.color = Color.BLACK; uncle.color = Color.BLACK; grandParent.color = Color.RED; node = grandParent; } else { // 当前节点是父节点的右子节点 if (node === node.parent.right) { // 将当前节点变为父节点，进行左旋操作 node = node.parent; this.leftRotate(node); } // 将父节点颜色改为黑，祖父节点颜色改为红，进行右旋操作 node.parent!.color = Color.BLACK; grandParent.color = Color.RED; this.rightRotate(grandParent); } } else { // 父节点是祖父节点的右子节点，与上面的同理 let uncle = grandParent.left; // 如果叔叔节点是红色的 if (uncle && uncle.color === Color.RED) { // 父节点设置为黑色 node.parent.color = Color.BLACK; // 叔叔节点设置为黑色 uncle.color = Color.BLACK; // 祖父节点设置为红色 grandParent.color = Color.RED; // 将当前节点设置为祖父节点 node = grandParent; } else { // 如果当前节点是父节点的左节点 if (node === node.parent.left) { // 将当前节点设置为父节点 node = node.parent; // 右旋父节点 this.rightRotate(node); } // 父节点设置为黑色 node.parent!.color = Color.BLACK; // 祖父节点设置为红色 grandParent.color = Color.RED; // 左旋祖父节点 this.leftRotate(grandParent); } } } // 根节点设置为黑色节点 this.root!.color = Color.BLACK; }
10.3.3.5 红黑树的删除操作
▼typescript复制代码/** * 删除红黑树中的某个节点 * * @param value 要删除的节点的值 */ delete(value: T) { // 先找到要删除的节点 const nodeToDelete = this.search(value); // 如果不存在，就直接退出 if (!nodeToDelete) { return; } // 否则删除节点 this._delete(nodeToDelete); } /** * 删除红黑树中的节点 * @param node 要删除的节点 */ private _delete(node: RedBlackNode<T>) { // 如果该节点同时存在左右节点，则找到右子树的最小节点作为该节点的后继 if (node.left && node.right) { const successor = this.minimum(node.right); node.value = successor!.value; node = successor!; } let child: RedBlackNode<T> | null; // 如果该节点存在左节点，则将该左节点作为它的唯一子节点 if (node.left) { child = node.left; } else if (node.right) { // 如果该节点存在右节点，则将该右节点作为它的唯一子节点 child = node.right; } else { child = null; } // 如果该节点没有子节点，直接删除 if (!child) { // 如果该节点是黑色，则需要特殊处理 if (node.color === Color.BLACK) { this._deleteCase1(node); } this._removeNode(node); } else { // 如果该节点是黑色，则需要特殊处理 if (node.color === Color.BLACK) { // 如果该节点的唯一子节点是红色，则将该唯一子节点设置为黑色 if (child.color === Color.RED) { child.color = Color.BLACK; } else { this._deleteCase1(node); } } // 用该节点的唯一子节点替换该节点 this._replaceNode(node, child); } } private _deleteCase1(node: RedBlackNode<T>) { // 如果有父节点，就进入 Case 2 if (node.parent) { this._deleteCase2(node); } } private _deleteCase2(node: RedBlackNode<T>) { // 找到兄弟节点 const sibling = this._sibling(node); // 如果兄弟节点存在且颜色为红色 if (sibling && sibling.color === Color.RED) { // 父节点颜色变为红色 node.parent!.color = Color.RED; // 兄弟节点颜色变为黑色 sibling.color = Color.BLACK; // 如果删除的节点是左子节点 if (node === node.parent!.left) { // 则向左旋转 this.leftRotate(node.parent!); } else { // 否则向右旋转 this.rightRotate(node.parent!); } } this._deleteCase3(node); } private _deleteCase3(node: RedBlackNode<T>) { const sibling = this._sibling(node); // 当父节点颜色是黑色，兄弟节点颜色是黑色，兄弟节点的左右子节点都是黑色 if ( node.parent!.color === Color.BLACK && sibling && sibling.color === Color.BLACK && (!sibling.left || sibling.left.color === Color.BLACK) && (!sibling.right || sibling.right.color === Color.BLACK) ) { // 将兄弟节点颜色设置为红色 sibling.color = Color.RED; // 递归处理父节点 this._deleteCase1(node.parent!); } else { // 进入下一个情况 this._deleteCase4(node); } } private _deleteCase4(node: RedBlackNode<T>) { const sibling = this._sibling(node); // 当父节点为红色，兄弟节点为黑色，且兄弟节点的左右子树为黑色时 if ( node.parent!.color === Color.RED && sibling && sibling.color === Color.BLACK && (!sibling.left || sibling.left.color === Color.BLACK) && (!sibling.right || sibling.right.color === Color.BLACK) ) { // 将兄弟节点涂红色 sibling.color = Color.RED; // 父节点涂黑色 node.parent!.color = Color.BLACK; } else { // 否则进入下一个删除 case this._deleteCase5(node); } } private _deleteCase5(node: RedBlackNode<T>) { const sibling = this._sibling(node); if (sibling && sibling.color === Color.BLACK) { // 如果当前节点是它父的左节点，并且兄弟节点的右节点存在且为红色 if ( node === node.parent!.left && sibling.right && sibling.right.color === Color.RED ) { // 将兄弟节点的颜色设置为红色 sibling.color = Color.RED; // 兄弟节点的右节点设置为黑色 sibling.right!.color = Color.BLACK; // 对兄弟节点进行左旋 this.leftRotate(sibling); } else if ( node === node.parent!.right && sibling.left && sibling.left.color === Color.RED ) { // 同上 sibling.color = Color.RED; sibling.left!.color = Color.BLACK; this.rightRotate(sibling); } } this._deleteCase6(node); } private _deleteCase6(node: RedBlackNode<T>) { const sibling = this._sibling(node); // 将兄弟节点颜色设置成父节点颜色 sibling!.color = node.parent!.color; // 将父节点颜色设置成黑色 node.parent!.color = Color.BLACK; if (node === node.parent!.left) { // 将兄弟节点的右子节点颜色设置成黑色 sibling!.right!.color = Color.BLACK; // 对父节点左旋 this.leftRotate(node.parent!); } else { // 将兄弟节点的左子节点颜色设置成黑色 sibling!.left!.color = Color.BLACK; // 对父节点右旋 this.rightRotate(node.parent!); } } private _removeNode(node: RedBlackNode<T>) { if (!node.parent) { this.root = null; } else if (node === node.parent.left) { node.parent.left = null; } else { node.parent.right = null; } } private _replaceNode(oldNode: RedBlackNode<T>, newNode: RedBlackNode<T>) { if (!oldNode.parent) { this.root = newNode; } else if (oldNode === oldNode.parent.left) { oldNode.parent.left = newNode; } else { oldNode.parent.right = newNode; } newNode.parent = oldNode.parent; } private _sibling(node: RedBlackNode<T>) { if (!node.parent) { return null; } return node === node.parent.left ? node.parent.right : node.parent.left; }
10.4 AVL树与红黑树对比
10.4.1 性能对比分析
事实上，红黑树的性能在搜索上是不如AVL树的，为什么呢？
图10-15 红黑树性能比对
如图10-15是一棵红黑树，如果我们插入节点30，会被插入到哪里呢？节点27的右边，并且节点30是红色节点时，依然符合红黑树的性质（不存在“红红冲突”，每条路径的黑节点数量没有改变），因此整棵树仍然满足红黑树五条性质，也就是对于红黑树来说，它不需要进行任何操作。PS：插入节点时，默认都是红色节点，因为如果默认插入为黑色，几乎一定会破坏"黑色高度"，如果默认插入为红色，最多只会破坏“不能连续红”的规则。
如果默认插入为黑色，黑高（黑色高度）的定义是：从任一节点到其所有叶子的路径上，黑色节点数量必须相同。如果我们插入一个黑色节点：它所在路径的黑节点数 +1，其他路径不变，于是黑高立刻被破坏。这意味着再去调整整条路径，甚至可能影响整棵树，代价很高。
如果默认插入为红色，黑色节点数量不变，并且黑高保持一致。唯一可能被破坏的是：父节点也是红色（产生红红冲突），但“红红冲突”是一个局部问题，可以通过旋转或者变色在局部范围内修复。
并且在10.3.1小节中，我们说明了第5条性质是最重要的（红黑树的平衡核心是“黑高一致”）。所以设计的原则是插入操作尽量不要改变黑节点数量，因为插入黑色，带来的问题是全局的，相对而言，我们应选择代价更小（局部）的情况：插入红色。
如果是AVL树，那必然要对图10-15所示的节点17、25，27进行一系列的左旋转。但红黑树的高度比AVL树更高，如果同样是搜索节点30，那么红黑树需要搜索4次，AVL树只需要3次，所以红黑树相当于牺牲了一点点的搜索性能，来提高插入与删除的性能（在插入与删除时，AVL树大多数情况都需要调整，而红黑树大多数情况不用，因此红黑树的性能更高）。
10.4.2 应用场景选择
AVL树是一种平衡度更高的二叉搜索树，所以在搜索效率上会更高，但是AVL树为了维护这种平衡性，在插入和删除操作时，通常会进行更多的旋转操作，所以效率相对红黑树较低。
红黑树在平衡度上相较于AVL树没有那么严格，所以搜索效率上会低一些，但是红黑树在插入和删除操作时，通常需要更少的旋转操作，所以效率相对AVL树较高，它们的搜索、添加、删除时间复杂度都是O(logn)，但是细节上会有一些差异。
那开发中如何进行选择呢？在应用场景上，需要看主要的需求是搜索还是插入与删除：
- 如果主要的需求是搜索并且每个节点的高度尽可能地平衡，选择AVL树。
- 如果主要的需求是插入与删除的效率，选择红黑树。
在早期的时候，很多场景会选择AVL树，目前选择红黑树的越来越多（AVL树依然是一种重要的平衡树），比如操作系统内核中的内存管理或者Java的TreeMap、TreeSet底层的源码。
