特殊的树

在离散数学中，N个节点、N-1条边就是树，并不必须要提到根。

至于为什么节点和边是这样的关系，因为不能成环！

树是二部图

二部图是一种特殊的图，它的所有节点可以被划分到两个独立的集合（比如集合A和集合B）中，并且满足：

• 图中的每一条边都连接着一个属于集合A的节点和一个属于集合B的节点。
• 同一集合内部（A内部或B内部）的任意两个节点之间没有边直接相连。

二叉搜索树

1.定义

一个二叉搜索树要么是空树，要么是满足以下性质的二叉树：

1. 每个元素都有一个键值，所有键值都是互异的。
2. 根节点左子树中所有键值小于根节点的键值。
3. 根节点右子树中所有键值大于根节点的键值。
4. 左子树和右子树本身也是二叉搜索树。

核心：利用二叉树结构，通过比较键值实现快速查找。

2. 索引二叉搜索树

• 在普通二叉搜索树的基础上，为每个节点增加一个 leftSize 字段。
• leftSize = 该节点左子树的元素个数 + 1（即包括该节点在内的左子树元素总数）。
• 用途：可以快速查找第 k 小的元素。

---

3. 类结构

• BinaryNode 类：包含 element（可比较的元素）、left（左孩子）、right（右孩子）。
• BinarySearchTree 类：包含根节点 root，以及一系列方法：
  • find(x), findMin(), findMax()
  • insert(x), remove(x)
  • printTree()

---

4. 查找操作

• find(x, t)：递归实现。
  • 如果 t == null，返回 null。
  • 如果 x < t.element，在左子树中查找。
  • 如果 x > t.element，在右子树中查找。
  • 否则，找到并返回该节点。

---

5. 查找最小/最大值

• findMin(t)：递归地一直向左走，直到没有左孩子。
• findMax(t)：非递归地一直向右走，直到没有右孩子。

---

6. 插入操作

• insert(x, t)：
  • 如果 t == null，创建新节点。
  • 否则，递归地插入到左子树或右子树。
  • 如果重复，不做任何操作。

---

7. 删除操作

删除节点分为三种情况：

1. 叶子节点：直接删除。
2. 只有一个非空子树：用其唯一的孩子替换它。
3. 有两个非空子树：
   • 用其右子树中的最小元素（或左子树中的最大元素）替换该节点。
   • 再递归地删除那个最小（或最大）元素。

---

8. 高度与性能

• 最坏情况：插入有序序列，树退化为链表，高度为 O(n)，操作时间复杂度为 O(n)。
• 最好/平均情况：树高度为 O(log n)，操作时间复杂度为 O(log n)。

AVL 树

1. 定义与目的

• AVL 树是一种自平衡二叉搜索树。
• 每个节点的平衡因子 = 右子树高度 - 左子树高度，其值只能为 -1, 0, 1。
• 目的：避免二叉搜索树退化为链表，保证查询、插入、删除的最坏时间复杂度为 O(log n)。

---

2. 平衡因子

• bf(node) = height(right) - height(left)
• 若 |bf| > 1，则该节点不平衡，需要调整。

---

3. 插入操作与旋转

插入后可能导致不平衡，需从插入点向上回溯，找到第一个不平衡节点进行调整。

情况1：外侧插入 → 单旋转

• 左单旋（插入在右子树的右子树）
• 右单旋（插入在左子树的左子树）

情况2：内侧插入 → 双旋转

• 左右双旋（插入在左子树的右子树）：先左旋再右旋。
• 右左双旋（插入在右子树的左子树）：先右旋再左旋。

旋转后，以该节点为根的子树高度恢复为插入前的高度，不会影响更上层的节点。

---

4. 删除操作

• 删除方法与二叉搜索树相同。
• 删除后可能引起多个节点不平衡，需从删除点向上回溯并调整平衡。

---

5. 高度分析

• AVL 树的高度为 O(log n)。
• 最小节点数递推公式：N_h = N_{h-1} + N_{h-2} + 1，与斐波那契数列相关。

B-树:一种多叉平衡搜索树

B-树是一种平衡的多路查找树，注意： B树就是B-树，”-“是个连字符号，不是减号 。 在大多数的平衡查找树（Self-balancing search trees)，比如 AVL 树 和红黑树，都假设所有的数据放在主存当中。那为什么要使用 B-树呢（或者说为啥要有 B-树呢）？要解释清楚这一点，我们假设我们的数据量达到了亿级别，主存当中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 I/O 操作相当耗时，而提出 B-树的主要目的就是减少磁盘的 I/O 操作。

[引用来源：知乎《图解：什么是B树》]

前置知识：

1. 访问节点是在硬盘上进行的，节点内的数据操作是在内存中进行的
2. 硬盘访问次数和树高正相关
3. 硬盘读取物理地址连续的多个字节和读取单个字节耗时几乎没有区别

1. m 路搜索树

• 每个内部节点最多有 m 个子节点，包含 1 到 m-1 个元素。
• 元素按键值升序排列，子树键值范围划分明确。

---

2. B-树的定义

B-树是满足以下条件的 m 路搜索树：

1. 根节点至少有两个孩子。
2. 除根节点外，每个内部节点至少有 ⌈m/2⌉ 个子节点。
3. 所有外部节点在同一层。

外部节点：即空指针，代表查找失败的位置。

/*
节点定义
*/
int *keys; // 存储关键字的数组
int t;  // 最小度 (定义一个结点包含关键字的个数 t-1 <= num <= 2t -1) 
BTreeNode **C; // 存储孩子结点指针的数组
int n;  // 记录当前结点包含的关键字的个数
bool leaf; // 叶子结点的一个标记，如果是叶子结点则为true,否则false

---

3. 性质

• 外部节点数 = 关键字数 + 1。

• 高度 h 满足： \(\log_m (n+1) \le h \le 1 + \log_{\lceil m/2 \rceil} \frac{n+1}{2}\)

---

4. 查找

• 与 m 路搜索树查找方法相同。
• 每次访问一个节点，最多访问 h 次，适合磁盘 I/O 优化。

---

5. 插入

• 总是插入在某个内部节点的关键字列表中。
• 情况1：节点未满，直接插入。
• 情况2：节点已满，进行分裂：
  • 将节点分为两部分，中间关键字提升到父节点。
  • 若父节点也满，继续分裂，可能使树高增加。

---

6. 删除

a) 删除叶子节点中的关键字

• 情况1：删除后节点仍满足最小关键字数要求，直接删除。
• 情况2：删除后关键字数不足：
  • 借关键字：从左或右兄弟节点借一个关键字，并调整父节点。
  • 合并：若兄弟节点也不足，则与兄弟节点及父节点中对应关键字合并。

b) 删除内部节点中的关键字

• 用其前驱（左子树最大）或后继（右子树最小）替换。
• 再递归地删除那个前驱或后继。

---

7. 节点结构

• 表示为：[s, c0, (e1, c1), (e2, c2), ..., (es, cs)]
• s：关键字个数
• ei：关键字
• ci：子节点指针