基础

• 树: 无环的无向连通图, 个节点的树一共有条边

• 树的节点的度: 子节点的个数
• 度为0 → 叶节点
• 度不为0 → 分支

• 节点的深度: 到根节点的路径上的边数

• 树的高度: 节点深度的最大值

• 当与任意节点相连的边不超过两条时, 树退化为链

二叉树

定义

• 二叉树: 除叶节点外, 每个节点可以分为左右两个子树(可以为空). 二叉树的子节点区分顺序(左/右子树), 而在普通树中不区分(即二叉树是一种标号树)

OI Wiki:

有根二叉树（rooted binary tree）：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。

大多数情况下，二叉树 一词均指有根二叉树。

• 二叉树的性质:
• 若节点数为 , 则总边数为
• 第 层最多有 个元素
• 高度为 的二元树, 至少有 个元素, 至多有 个元素
• 除度为 的节点数(即叶节点数)比出度为 的节点数多

• 有n个节点的二元树, 高度至多为 , 至少为 l

特殊二叉树

• 完整二叉树（full/proper binary tree）：每个结点的子结点数量均为 0 或者 2 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。(没有独生子)

• 完全二叉树（complete binary tree）：最底层节点靠左填充，其他层的节点都被填满且层数相同

• 完美二叉树（perfect binary tree）：所有叶结点的深度均相同，且所有非叶节点的子节点数量均为 2 的二叉树称为完美二叉树。

存储方式

• 广义表 / 邻接表表示
• 为每个节点开辟一个线性链表来存储与该节点相连的节点
• 可以一个表存子节点, 一个表存父节点
💡
广义表（Generalized List）是数据结构中的一种非线性数据结构，它是线性表的推广形式。广义表不仅可以存储单个元素，还可以存储其他广义表，从而形成一个递归的嵌套结构。
特点
1. 递归结构：广义表的元素可以是原子（不可再分的基本数据项），也可以是另一个广义表。
2. 线性表的推广：线性表是广义表的特例，当广义表中所有元素都是原子时，广义表就退化为线性表。
3. 多层嵌套：广义表的层次结构可以非常复杂，支持多层嵌套。
表示方式
广义表通常用括号表示，其中每个元素用逗号分隔。
例如：
• 单层广义表：(a, b, c)
• 多层嵌套广义表：(a, (b, c), d)
定义形式
设广义表 定义如下：
1. 若 是一个空表，则 ；
2. 若 是非空表，则 可表示为 ，其中 是原子或另一个广义表。
广义表的长度和深度
1. 长度：广义表的长度是表中直接包含的元素个数，不论这些元素是原子还是子表。例如， 的长度为 3。
2. 深度：广义表的深度是嵌套层次的最大值。例如， 的深度为 。
常见操作
• 访问元素：访问某个位置的原子或子表。
• 插入与删除：在表中添加或删除原子或子表。
• 遍历：递归遍历整个广义表。
应用场景
广义表在需要处理嵌套数据的场景中非常有用，例如：
• 表达式树
• XML 和 JSON 等嵌套数据格式
• 数据库中的多级索引结构
这种数据结构由于其灵活性和递归特性，在描述复杂结构和实现递归算法时具有重要作用。

• 双亲表示法
• 用一个数组记录每个节点的父节点
• 可以获得的信息较少, 且不利于进行自顶向下的遍历, 常用于自底而上的递推

• 左子女-右兄弟表示法
• 对于有根树, 存在一种简单的表示方法: 首先, 给每个结点的所有子结点任意确定一个顺序. 此后为每个结点记录两个值: 其 第一个子结点 child[u] 和其 下一个兄弟结点 sib[u]。若没有子结点，则 child[u] 为空；若该结点是其父结点的最后一个子结点，则 sib[u] 为空。
💡
child[]用于访问下一层, sib[]用于访问平层
• 可以如下实现对一个节点所有子节点的遍历:

• 表示法1: 标号系统(在堆排序中用到, 此处从0开始, 左子节点为, 右子节点为)





将一般的树作为缺少某些元素的完美二叉树存储, 效果如下:

• 表示法2: 节点存储, 用结构体/类管理节点的左/右子节点和数据

• 表示法3: 指针表示法, 另一种数组实现, 数组val[]存储节点的值, 数组left[]存储左子节点的下标, 数组right[]存储右子节点的下标(-1表示空指针域)

常用操作

• Create()

• IsEmpty()

• Root(x)

• MakeTree(root, left, right)

• BreakTree(root, left, right)

• PreOrder(visit, root)

• InOrder(visit, root)

• PostOrder(visit, root)

• LevelOrder(visit, root)

二叉树的遍历

DFS

• 均基于递归实现

• 所谓前中后, 指的是根节点在何时被遍历

前序遍历

• 自身 → 左子树 → 右子树; 子树内部也按照该顺序递归遍历

中序遍历

• 左子树 → 自身 → 右子树; 子树保持规则递归遍历

后序遍历

• 左子树 → 右子树 → 自身; 子树保持规则递归遍历

1. 后序遍历顺序： 左子树 -> 右子树 -> 当前节点。

2. 使用了栈 s 和标记 tag 来记录回溯路径：

• tag == 0：表示当前节点是从左子树进来的。

• tag == 1：表示当前节点是从右子树回来，当前节点已完成左右子树的处理。

1. 通过标记和栈管理，算法能够区分节点的访问阶段，确保每个节点在访问左右子树之后再被处理。

• 从当前节点 p 开始，沿左子树一路深入，直到 p == NULL（没有左子节点）。

• 每次访问一个节点，将其指针和标记压入栈中，标记为从左子树进入。

• 栈顶节点出栈，当前节点指针恢复为栈顶节点的地址。

• 此时需要判断当前节点是从左子树回来的，还是从右子树回来的。

• 如果 tag == 1，表示当前节点已经从右子树回溯，此时可以直接访问当前节点并继续向上回溯。

• 如果栈为空，表示遍历完成，直接返回。

• 如果当前节点是从左子树回来的（tag == 0），将其标记为从右子树回来（tag = 1），重新压栈。

• 转向右子树，将右子树作为新的起点继续遍历。

BFS

层序遍历

• 按照从根节点到叶子节点的层次关系，一层一层的横向遍历各个节点

Morris遍历

1. 如果 cur 为空时遍历停止，否则进行以下过程。

2. 如果 cur 没有左子树，cur 向右移动（cur = cur->right）。

3. 如果 cur 有左子树，找到左子树上最右的节点，记为 mostRight, 则mostRight是根节点cur的中序序列的直接前驱
• 如果 mostRight 的 right 指针指向空，让其指向 cur，然后 cur 移动到左子节点（cur = cur->left）。
• 如果 mostRight 的 right 指针指向 cur，将其修改为 null，然后 cur 向右移动（cur = cur->right）。

GPT:

Morris 遍历是一种二叉树遍历方法，它以 非递归 和 不使用栈 的方式完成遍历，同时保持 O() 的空间复杂度。这种方法通过巧妙地利用树结构中的空闲指针来在节点间导航，而无需额外的空间。

Morris 遍历并不是与线索树直接相关的概念，但它的实现思想与线索树有些类似，因为它会在遍历过程中临时修改二叉树的结构（类似于线索树的线索指针）。

Morris 遍历的核心思想

1. 如果当前节点的左子树为空：
• 访问当前节点（对于中序遍历就是输出当前节点值）。
• 移动到当前节点的右子节点。

2. 如果当前节点的左子树不为空：
• 找到当前节点左子树的最右节点（即左子树中的“中序前驱”）。
• 如果最右节点的右指针为空：
• 将其右指针指向当前节点（临时建立返回路径）。
• 移动到当前节点的左子节点。
• 如果最右节点的右指针指向当前节点（即返回路径已存在）：
• 恢复最右节点的右指针为空。
• 访问当前节点。
• 移动到当前节点的右子节点。

Morris 遍历的分类

1. 中序遍历

• 遵循中序遍历的顺序：左 -> 根 -> 右。

• 每次访问节点时，保证左子树的节点已经被访问。

1. 前序遍历

• 在第一次遇到某个节点时立即访问它，然后处理左子树和右子树。

1. 后序遍历

• Morris 遍历的后序实现稍复杂，一般通过在每个节点的左子树末尾构建反转路径来完成。

Morris 中序遍历的代码示例（Python）

Morris 遍历与线索树的区别

1. 线索树：

• 线索树是对二叉树的静态改造。通过添加线索指针（指向前驱或后继节点）来提高遍历效率。

• 线索树在改造后可以长期使用，而不会破坏树的结构。

1. Morris 遍历：

• Morris 遍历是对二叉树的动态改造。在遍历过程中临时修改指针，在遍历完成后恢复原树结构。

• 它不会长期保存修改，只是为了实现 空间复杂度的遍历。

因此，Morris 遍历和线索树在概念上是独立的，但都涉及到利用树中的 空闲指针 来优化遍历性能。

遍历方式与DFS和BFS的关系

GPT:

1. 先序遍历是DFS的一种实现方式

• 深度优先搜索（DFS）： 遍历时优先访问子节点，直到到达某条路径的末端，再回溯到上一层节点。

• 先序遍历（Preorder Traversal）： 是DFS的一种具体策略。在遍历过程中，先访问当前节点，然后依次递归访问左子树和右子树。这种顺序与DFS的“优先深入”原则一致，因此先序遍历可以看作DFS的一种实现方式。

其他如中序遍历（Inorder）和后序遍历（Postorder）也是DFS的不同实现策略，它们的核心仍是“优先深入后回溯”。

 

2. 层序遍历是BFS的一种实现方式

• 广度优先搜索（BFS）： 遍历时按照层次（水平）逐层访问节点。先访问某一层的所有节点，再访问下一层的节点。

• 层序遍历（Level Order Traversal）： 是BFS在树中的一种实现方式。在遍历过程中，从根节点开始，按层逐层访问节点，通常借助队列来实现。这种遍历方式正是BFS的典型特征。

 

总结

• 先序遍历是DFS的一种实现方式：深度优先搜索可以通过先序、中序、后序等方式实现。

• 层序遍历是BFS的一种实现方式：广度优先搜索在树中的典型应用就是层序遍历。

两者的实现核心在于访问的顺序和使用的数据结构：

• DFS通常借助递归或栈。

• BFS通常借助队列。

题型

• 根据遍历顺序反向构建树



前序遍历序列的第一个元素一定是根节点, 后序遍历序列的第一个元素一定是根节点, 但是只知道一种序列时左右子树部分无法确定
中序遍历的根节点左侧为左子树, 右侧为右子树, 但是单独无法确定根节点
已知其中两种序列时可以构造出完整二叉树, 从而可以得到第三种序列(其中必须有一种是中序序列), 不断利用前序/后序确定根节点, 再利用中序确定左右子树, 递归进行

• 求树高度的方式: height(t) = max(height(t→left), height(t→right)) + 1 (递归过程)
• 边界: if (t == null) return 0;

• 森林的遍历

• 中缀表达式转为前缀/后缀: 对每一个运算符的两个操作数的两侧加上括号, 再将该运算符移动到对应的的括号前(前缀)/后(后缀)

• 前缀表达式的计算: 从后向前遍历前缀表达式, 遇到操作数则入栈, 遇到运算符则出栈对应数量的操作数, 完成运算(后入栈的先算)之后将结果重新入栈

• 后缀表达式的计算: 从前向后遍历前缀表达式, 遇到操作数则入栈, 遇到运算符则出栈对应数量的操作数, 完成运算(先入栈的先算)之后将结果重新入栈

线索二叉树

• 定义: 一个二叉树通过如下的方法“穿起来”：所有原本空闲的左子节点指针改为指向该节点在某种特定遍历序列中的前驱，所有原本空闲的右子节点指针改为指向该节点在遍历序列中的后继。根据遍历顺序可以分为前/中/后序线索二叉树.

• 优势: 充分利用链式存储结构中的 空闲指针 来存放指向该节点的直接前驱或是直接后继的指针. 这些被重新利用起来的空指针就被称为 线索 ，加上了这些线索的二叉树就是线索二叉树。线索二叉树能线性地遍历二叉树, 比递归的中序遍历更快(一直取后继即可)
💡
DFS遍历末端的节点一定有空指针, 可以利用它来指向其前驱/后继, 以在到达末端时绕开回溯, 沿线索继续向后遍历
要构建特定遍历顺序下的线索二叉树, 只需要找到左右孩子不齐全的节点, 让左指针指向其在遍历序列中的直接前驱, 右指针指向其在遍历序列中的直接后继即可

• 线索化: 对二叉树以某种遍历顺序进行扫描并为每个节点添加线索的过程称为二叉树的线索化，进行线索化的目的是为了加快查找二叉树中某节点的前驱和后继的速度。 那么在有 个节点的二叉树中需要利用 个空指针添加线索。这是因为在 个节点的二叉树中，每个节点有2个指针，所以一共有 个指针，除了根节点以外每一个节点都有一个指针从它的父节点指向它，所以一共使用了 个指针。所以剩下 个空指针。

• 节点需要两个额外字段来标记left和right指向的是正常的字节点还是前驱/后继节点(线索)
• leftType：左节点的类型：0：左子树，1：前驱节点
• rightType：右节点的类型：0：右子树，1：后继节点

遍历线索二叉树

• 中序线索化遍历

• 前序线索化遍历

• 注意
1. 根据不同的「序」，考虑如何跳过或进入下一个节点，因为要考虑前驱和后继
1. 中序：由于它的顺序，第一个线索化节点，就是他的顺序的第一个节点，不用管接下来遇到的节点是否已经线索化过了，这是由于它天然的顺序，已经线索化过的节点，不会在下一次处理
2. 前序：由于它的顺序，第一个顺序输出的节点，并不是第一个线索化节点。所以它需要对他的 左右节点进行类型判定，是普通节点的话，再按 自己→左→右 的顺序进行左、右进行递归，因为下一次出现的节点有可能是已经线索化过的节点，如果不进行判定，就会导致又回到了已经遍历过的节点。就会导致死循环了
2. 遍历线索化时：基本上和线索化时的「序」一致去考虑，何时该进行输出？什么时候遇到后继节点时，跳转到后继节点处理。最重要的一点是：遍历时，不用考虑前驱节点，之用考虑何时通过后继节点进行跳转。

霍夫曼树

定义

1. 给定 n 个 权值 作为 n 个 叶节点，构造一颗二叉树，若该树的 带权路径长度（WPL）达到最小，称这样的二叉树为 最优二叉树，也称为 霍夫曼树（Huffman Tree）

2. 霍夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近

重要概念

• 路径 和 路径长度：
在一颗树中，从一个节点往下可以到达的孩子或孙子节点之间的通路，称为 路径。
通路中分支(边)的数目称为路径长度。若规定根节点的层数为 1，则从根节点到第 L 层节点的路径长度为 L-1

• 节点的权 及 带权路径长度
若将树中节点赋给一个有着某种函数的数值，则这个数值称为该节点的 权。
节点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积。

• 树的带权(外)路径长度
所有叶节点的带权路径长度之和，记为 树的带权(外)路径长度WPL（weighted path length），权值越大的节点离根节点越近的二叉树才是最优二叉树



💡
根节点到叶节点的带权路径长度之和 → 外路径长度
根节点到非叶节点的带权路径长度之和 → 内路径长度

• 对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树 称为 霍夫曼树（Huffman Tree）

霍夫曼算法

1. 初始化：由给定的 n 个权值构造 n 棵只有一个根节点的二叉树，得到一个二叉树集合 F (一个森林)。

2. 选取与合并：从二叉树集合 F 中选取根节点权值 最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。

3. 删除与加入：从 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 F 中。

4. 重复 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树。

霍夫曼编码

• 在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即 编码。

• 在进行二进制编码时，假设所有的代码都等长，那么表示 个不同的字符需要 (上取整) 位，称为等长编码。如果每个字符的 使用频率相等，那么等长编码无疑是空间效率最高的编码方法，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种 不等长编码，从而获得更好的空间效率。

• 在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为 前缀编码，其保证了编码被解码时的唯一性。

• 霍夫曼树可用于构造 最短的前缀编码，即 霍夫曼编码（Huffman Code），其构造步骤如下：
1. 设需要编码的字符集为：，他们在字符串中出现的频率为：。
2. 以 d 作为叶结点，作为叶结点的权值，构造一棵霍夫曼树。
💡
最短: 使得出现频率最高的节点最后加入霍夫曼编码树(位置最靠上), 从而使出现频率高的节点编码短
无歧义: 叶节点不可能在从根节点到另一个叶节点的路径上, 故前缀不可能相同
应用: 经常用于数据压缩(重新编码)
3. 规定哈夫曼编码树的左分支边代表 0 ，右分支边代表 1 ，则从根结点到每个叶结点所经过的路径组成的 0、1 序列即为该叶结点对应 字符 的编码。

• 题型如下:

补充: 前缀编码

前缀编码（Prefix Code）是一种特殊类型的编码方式，用于将符号编码成二进制串。其主要特点是 任何一个符号的编码都不会是另一个符号的编码的前缀。这种特性保证了解码过程可以无二义性地进行，无需分隔符。

特点

1. 前缀无歧义性：对于任意两个符号，其编码之间不会出现前缀关系。例如，如果符号 A 编码为 0，符号 B 编码不能是 01，否则在解码过程中会产生歧义。

2. 即时解码：由于前缀编码的前缀无歧义性，一旦读取到一个完整编码，就可以立刻解码，不需要等到后续数据。

常见的前缀编码

1. 哈夫曼编码：一种基于符号频率的最优前缀编码方法，用于数据压缩。

2. 莫尔斯电码：虽然是早期通信中使用的一种编码，也可以看作一种前缀编码。

3. UTF-8：一种编码多字节字符的标准，其中每个字符的编码也符合前缀编码的规则。

示例

假设有以下符号集合及其对应编码：

在这种情况下：

• 编码串 01101110 可以被解析为：0（A），110（C），1110（不存在）——符合前缀编码规则。

• 但如果某个符号的编码是 11，会与 110 和 111 产生冲突，不符合前缀编码的要求。

应用场景

1. 数据压缩：如 ZIP 文件、MP3 音频中常用的哈夫曼编码。

2. 通信协议：用于避免误解或分隔符的需求。

3. 文件格式：如 JSON 等格式解析中的符号分割。

前缀编码在计算机科学中的重要性在于它能高效地表示数据，同时支持快速无歧义解码。

二叉搜索树

定义

1. 空树是二叉搜索树。

2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

4. 二叉搜索树的左右子树均为二叉搜索树。

遍历

查找最小/最大值

搜索元素

• 若 root 为空，返回 false。

• 若 root 的权值等于 value，返回 true。

• 若 root 的权值大于 value，在 root 的左子树中递归搜索。

• 若 root 的权值小于 value，在 root 的右子树中递归搜索。

插入元素

• 若 root 为空，直接返回一个值为 value 的新节点。

• 若 root 的权值等于 value，该节点的附加域该值出现的次数自增 。

• 若 root 的权值大于 value，在 root 的左子树中递归插入权值为 value 的节点。

• 若 root 的权值小于 value，在 root 的右子树中递归插入权值为 value 的节点。

删除元素

• 若该节点的附加 count 大于 1，只需要减少 count。

• 若该节点的附加 count 为 1：



• 若 root 为叶子节点，直接删除该节点即可。
• 若 root 为链节点，即只有一个子树的节点，用这个子树代替它
💡
以上两种情况都没有争议
• 若 count 有两个非空子节点，一般是用它左子树的最大值（左子树最右的节点）或右子树的最小值（右子树最左的节点）代替它 (维持中序序列非降) , 然后删除用于替代的节点 。
💡
找到比它小的里面最大的, 比它大的里面最小的, 以维中序遍历序列不变
找中序序列的直接前驱或后继

求元素的排名

查找排名为 k 的元素

• 若其左子树的大小大于等于k ，则该元素在左子树中；

• 若其左子树的大小在区间  (count 为根节点的值的出现次数)中，则该元素为根节点；

• 若其左子树的大小小于 ，则该元素在右子树中。

与二分查找的关系

1. 分治思想：

1. 有序性要求：

• 二分查找要求数据存储在一个有序数组中。

• 二叉搜索树的结构要求节点按一定的规则排序：

• 对于任意节点，左子树中的所有值小于该节点值，右子树中的所有值大于该节点值。

1. 效率：

• 它们的时间复杂度在理想情况下（平衡状态）都为 。

• 二分查找可以看作是二叉搜索树的特例。

• 二叉搜索树是对二分查找思想的推广。

• 它允许动态地插入和删除节点，同时保持有序性。

• 特殊的平衡二叉树（如AVL树、红黑树）通过算法保证树的平衡，从而确保时间复杂度接近 。

AVL树(平衡二叉搜索树)

平衡性

获得平衡性

• 右旋: 也称为「右单旋转」或「LL 平衡旋转」。对于结点 A 的右旋操作是指：将 A 的左孩子 B 向右上旋转，代替 A 成为根节点，将 A 结点向右下旋转成为 B 的右子树的根结点，B 的原来的右子树变为 A 的左子树。(冲突的右孩变左孩)



💡
A右旋: B < T2 < A(根) < T3 → B(根) < T2 < A < T3
右旋操作只改变了三组结点关联，相当于对三组边进行循环置换一下，因此需要暂存一个结点再进行轮换更新。对于右旋操作一般的更新顺序是：暂存B结点（新的根节点），让A的左孩子指向B的右子树，再让B的右孩子指针指向A，最后让A的父结点指向暂存的B。

• 左旋操作为右旋操作的镜像. (冲突的左孩变右孩)

• 右旋增长右子树缩短左子树, 左旋增长左子树缩短右子树

1. LL 型：失衡节点的左孩子的左子树过长导致平衡性破坏。
调整方式：右旋失衡节点。

2. RR 型：与 LL 型类似，失衡节点的右孩子的右子树过长导致平衡性破坏。
调整方式：左旋失衡节点。

3. LR 型：失衡节点的左孩子的右子树过长导致平衡性破坏。
调整方式：先左旋失衡节点的左儿子，成为 LL 型，再右旋失衡节点。

4. RL 型：与 LR 型类似，失衡节点的右孩子的左子树过长导致平衡性破坏。
调整方式：先右旋失衡节点的右儿子，成为 RR 型，再左旋失衡节点。

AVL树定义

AVL树上的操作

• 右旋

• 左旋(右旋的严格镜像, 只需交换left和right)

• 统一的旋转方法封装

• 插入节点: AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在 AVL 树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡。代码如下所示：
注: 平衡子树经增删操作后变为不平衡子树, 再调整为平衡子树, 始末高度不变 → 结论: 调整不会影响到不平衡子树以外的结点。故调整范围可以限制在插入结点的最小不平衡子树中进行,即从根到达插入结点的路径上,离插入结点最近的, 并且平衡系数≠0的结点为根的子树内。插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各节点左右子树的高度差， 如果发现某点高度不平衡则停止回溯并处理当前子树即可。至多调整一次(距插入位置最近的失衡节点)
💡
由插入节点造成的AVL树失衡 → 只需要调整距插入位置最近的一个失衡节点, 就可以使得整个树回复平衡

推论解释:

这个推论是正确的，可以用于理解平衡二叉树（如AVL树）中的插入操作及其调整过程。以下是对该推论的逐步分析和解释：

1. 不平衡子树调整的范围限制：

平衡二叉树（例如AVL树）定义中，任何节点的左右子树高度差不超过1。插入或删除节点时，可能导致某些节点的平衡性被破坏。调整的目标是恢复这些节点的平衡，而不影响整个树的结构。

1. 调整不会影响不平衡子树以外的节点：

如果某一子树根节点不平衡，其失衡的原因仅由该子树的结构决定。因此，调整只需在失衡子树内进行，调整过程不会影响子树之外的节点的结构和高度。

1. 最小不平衡子树的定位：

在插入节点后，从插入位置向上回溯，依次检查各节点的平衡因子（左右子树高度差）。第一个出现失衡的节点（即平衡因子变为±2的节点）就是需要调整的根节点。

1. 停止回溯：

一旦找到第一个失衡节点并完成调整，回溯可以停止，因为调整后该节点及其子树恢复平衡，并且调整不会引入新的失衡。

1. 调整操作的局部性：

调整操作（如AVL树中的旋转）是局部的，通常只涉及失衡节点及其直接子节点的重构，确保调整过程效率高且不影响整个树。

结论：

该推论正确且具有指导性。调整范围可以限制在插入结点的最小不平衡子树中进行，这样可以优化操作效率。每次插入新节点后，从插入位置回溯到根节点，检查并处理最近的失衡点即可。



AVL树就通过多次插入操作构建.

• 删除节点:
与插入操作相比, 删除操作后可能有多个祖宗节点需要调整, 可能需要调整多次才能获得新的AVL树
💡
删除节点后维护平衡需要一路追溯到根节点, 检查是否失衡

解释:

插入和删除对路径上节点高度的影响本质上源于AVL树平衡因子的定义，以及高度的增减如何在树中传播。

插入操作为何只能影响一个节点的高度

1. 插入的位置总是叶子节点或将成为叶子节点的位置

插入操作总是在某个节点的子树中新增一个节点，而这个新节点会成为叶子节点。新节点的加入只会使它的直接父节点的高度增加1。

1. 高度变化的局部性

在插入节点后，从插入点回溯向上的路径上，只有一个节点的高度可能会因为插入而增加。因为AVL树每个节点的高度由其左右子树的最大高度决定，其他路径上的节点高度不受影响。

1. 失衡的传播机制

插入导致的失衡仅发生在回溯路径上的第一个不平衡节点（平衡因子变为±2）。通过旋转调整后，该节点及其子树的高度会恢复到插入前的状态，这会自动消除插入对更高层祖先节点的影响。

示例：

• 插入一个节点后，假设高度增加传递到了某祖先节点 ，使 失衡（高度差为±2）。

• 通过一次旋转（单旋转或双旋转），可以恢复 的平衡，且其高度不会增加。

• 因此，插入操作对路径上的更高层祖先节点没有影响。

删除操作为何可以影响多个节点的高度

1. 删除的位置可以在任何层级

删除节点可能发生在任意层级，而被删除的节点的缺失会直接导致其父节点的子树高度减小。

1. 高度减少的传播性

删除一个节点会导致其所在子树的高度减小1。这种高度减小会沿着回溯路径向上传递，因为AVL树的高度是由左右子树的最大高度决定的。如果高度变化的路径影响到了某个祖先节点的平衡因子（平衡因子变为±2），需要调整该节点。

1. 调整后可能仍需继续调整

与插入不同，删除操作的调整（通过旋转）可能会使当前节点恢复平衡，但无法阻止高度减少向更高层传播。这种传播可能导致路径上的其他祖先节点失衡，需逐级调整，直到回溯到根节点或整棵树恢复平衡。

示例：

• 删除某个节点后，使其父节点 的平衡因子变为±2， 失衡。

• 对 进行调整后，虽然 恢复了平衡，但 的高度可能变小，继续向上传递高度减少的影响。

• 如果更高层的祖先节点失衡，需要再次调整。

总结比较

插入操作: 仅增加路径上一个节点的高度, 调整第一个失衡节点后, 其高度恢复到插入前的状态, 影响不会向上传递。

删除操作: 减少路径上多个节点的高度, 调整失衡节点后, 其高度可能变小, 高度减少的影响会继续向上传递，导致需要逐级检查并调整多个节点。

删除操作的复杂性来源于其传播性, 而插入操作的调整局限于一个局部子树, 因此插入操作更高效。

• 查找节点 → 与二叉搜索树一致

B-树(多叉平衡搜索树)

定义

1. 读写磁盘的速度相比内存读写慢很多。

2. 每次读写磁盘的单位要比读写内存的最小单位大很多。

• B-树有一层空的节点 → 外部节点, 仅代表查找失败, 故又称失败节点; 其余节点 → 内部节点. 一般称内部节点的最后一层为叶节点

• 子树在父节点的键值之间见缝插针(故子树的数量比父节点键值树大1). 键值左侧子树中所有数均小于键值, 右侧子树中所有数均大于键值.

特性

• 平衡 → 所有叶节点必须在同一层

• 有序 → 任何节点内的多个数据都有顺序(从小到大), 且子树从左到右依然保持从小到大的顺序(左儿子<根节点<右儿子)

• 多路 → 对于 阶B树的节点: 最多 个元素, 个分支; 根节点最少 个分支 个元素, 其他节点至少 个元素, 个分支

操作

插入

• 可能引起节点元素的上溢出

• 解决方案:
1. 将该节点以中间元素(第 个)为界分割为中间元素的左侧, 中间元素以及中间元素的右侧
2. 中间元素上移到父节点, 左右两半分别成为父节点的两个子节点
💡
该过程可能在父节点引发连锁的上溢出, 故需要递归处理.
如果一直递归到根节点(没有父节点), 则中间元素上移成为新的根节点, 树的高度增加.

构建

删除

• 第一步操作与二叉搜索树中相同, 若待删除节点为叶节点则直接删除, 若为非叶节点则用其直接前驱/后继替换之

• 可能引起节点元素的下溢出

• 删除操作本身依旧遵循搜索树的删除操作, 即用中序遍历的直接前驱/后继来替换该元素

• 下溢出处理方案:
1. 兄弟够补 → 父下来, 兄上去
父节点元素补充到下溢出节点, 兄弟节点上去一个元素补充到父节点, 保证有序性
若兄弟节点有最左(最右)子树, 则该子树需要一并移动到下溢出节点下的新增子树槽位
左右兄弟在够补时没有硬性规定如何选择 → B树不唯一
2. 兄弟都不够借 → 减少子树个数, 父节点降辈分(家族规模不够)
先让父节点下到下溢出节点的左/右兄弟节点
再让下溢出节点与兄弟节点合并(若有子树则携带子树一同合并)
最终移除掉空的父节点元素和子树.
💡
可能引起父节点下溢, 故需要递归处理.