Hello,树

一、树的基本概念

树是一种非线性数据结构，由节点 (Node) 和边 (Edge) 组成，具有以下特性：

根节点：树的起始点，没有父节点。
父子关系：每个节点可以有多个子节点，但只能有一个父节点。
层次结构：节点的子节点形成子树（Subtree）。
无环：树中不存在循环路径。

关键术语示例

**节点深度：**从根到该节点的层数（根节点深度为0）。
**节点高度：**从该节点到最远叶子节点的边数。
**叶子节点：**没有子节点的节点。
**兄弟节点：**共享同一父节点的节点。

1
2
3
4
5
    A (根节点, 深度0, 高度2)
   / \
  B   C (兄弟节点)
 / \
D   E (叶子节点)

二、树的分类与特性

1. 二叉树（Binary Tree)

每个节点最多有 2 个子节点（左子节点和右子节点）。

二叉树变种：

满二叉树：所有叶子节点在同一层，且非叶子节点都有2个子节点。

1
2
3
4
5
     A
   /   \
  B     C
 / \   / \
D   E F   G

完全二叉树： 除最后一层外，其他层节点填满，最后一层节点从左到右填充。

1
2
3
4
5
     A                        A
   /   \                    /   \
  B     C                  B     C
 / \   /                  /     /
D   E F                  D     F

平衡二叉树（AVL树）：

平衡条件：任意节点的左右子树高度差不超过 1。
操作：通过旋转（LL/RR/LR/RL）保持平衡。
应用：内存中的快速查找 (如早期Java的 TreeMap) 。

示例：插入导致不平衡的处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
初始平衡树：
70节点，其左子树高度为2(节点60到叶子节点的最长路径包括2条边)，右子树高度为3(节点80到节点90包括2条边，共3条边)，高度差1，50节点，其左子树高度为 2，右子树高度为 3，高度差为 1，所以树处于平衡状态。
      50
    /    \
  30      70
 /  \    /  \
20   40 60   80
               \
                90

插入节点95，插入后树的结构变为：
      50
    /    \
  30      70
 /  \    /  \
20   40 60   80
               \
                90
                  \
                   95
这时检查节点70，其左子树高度为2,右子树高度为4，高度差为2，破坏了AVL树的平衡条件。需要进行调整，这里发生的是RR型不平衡(新节点在失衡节点的右子树的右子树位置)，通过一次右旋操作(以80为旋转轴)来恢复平衡。旋转后树的结构变为：
      50
    /    \
  30      80
 /  \    /  \
20   40 70   90
          \    \
           60   95

经过这次旋转，所有节点的左右子树高度差都回复到不超过1，重新成为一棵平衡二叉树。

B树（B-Tree)

多叉树：每个节点有多个子节点（扇出系数大）。
平衡条件：所有叶子节点在同一层，内部节点子节点数在[m/2,m]之间（m为阶数)。
应用：外存存储（如文件系统、数据库索引）。

B树(m=3)示例：

1
2
3
4
5
6
7
8
   [10, 20]
   /   |   \
[5] [15] [25]

结构说明：
1. 根节点包含键值 10 和 20，有 3 个子节点
2. 每个子节点存储 1 个键值，子节点数 = 键值数 + 1
3. 所有叶子节点 ([5],[15],[25])位于同一层

B树的键值分界机制

B树是一种多叉平衡树，其每个节点的键值具有以下作用：

分割子节点范围：父节点的键值是其子节点键值的分界点。例如：
- 父节点键值为[10, 20] ,表示：
  - 左子节点的所有键值 <10
  - 中间子节点的所有键值在 10 <= x < 20 之间
  - 右子节点的所有键值>=20
- 保证有序性：子节点的键值必须严格按照父节点的键值划分范围。

父节点与子节点键值的关系

父节点的键值与子节点键值存在以下必然联系：

父节点的键值是子节点的极值：
- 父节点的第 i 个键值等于其第 i+1 个子节点的最小键值。
- 例如：
  - 父节点 [10,20]的右子节点 [25]的最小键是 25,但父节点中并没有 25。这是因为此时父节点的键值尚未覆盖所有子节点范围，需要通过后续插入操作调整。
分裂时的键值提升：
- 当插入新键导致节点分裂时，中间键会被提升到父节点，成为父节点的新键值。例如：
  - 插入 30 到子节点 25 后，节点分裂为 [25] 和 [30] ,中间键 25 被提升到父节点，父节点变为[10,20,25]。此时：
    - 父节点的 25 是右子节点 30 的最小键值的分界点。
    - 子节点[25]的所有键值<=25 ,子节点 [30]的所有键值 >=30。

以插入30 后的分裂过程为例：

1
2
3
4
5
6
7
8
9
初始结构：
   [10, 20]
   /   |   \
[5] [15] [25]

插入30后：
   [10, 20 ,25]
   /   |    |  \
[5] [15]   [25] [30]

父节点的键值 20 是右子节点 [25] 的最小键值分界点（即25>=20）。
插入 30 后：
- 子节点 25 变为 [25,30] ,超过 m=3 的限制，分裂为 [25] 和 [30]。
- 中间键 25 被提升到父节点，父节点变为 [10, 20, 25]，子节点为 [5]、[15]、[25]、[30]。
父节点的 25 作用：
- 分割子节点 [25] 和 30 的范围：
  - [25] 的所有键值 <= 25
  - [30] 的所有键值 >=30
- 父节点的键值 25 是子节点 [30]的最小键值的分界点。

B树设计的意义

减少磁盘I/O：父节点的键值作为子节点范围的索引，可快速定位目标子节点，减少树的高度。
保证平衡：通过分裂和合并操作，确保所有叶子节点在同一层，维护树的平衡。
外存友好：键值的分界机制与磁盘块的读取效率高度匹配，适合存储大规模数据。

红黑树（Red-Black Tree)
- 平衡条件：通过颜色标记和规则保证最长路径不超过最短路径的 2 倍。
- 规则：
  1. 节点颜色为红或黑。
  2. 根节点为黑。
  3. 叶子节点（NIL）为黑。
  4. 红节点的子节点必须为黑。
  5. 任意路径上的黑节点数相同。
- **应用：**Linux内核、C++ std::map

三、树的操作与算法

1. 遍历方式

前序遍历： 根->左->右（DFS)
**中序遍历：**左->根->右 (仅适用于二叉树)。
后序遍历： 左->右->根。
**层序遍历：**按层从上到下（BFS)

示例(二叉树)

1
2
3
4
5
6
7
8
9
       A
     /   \
    B     C
   / \   / \
  D  E  F   G
先序：A->B->D->E->C->F->G
中序：D->B->E->A->F->C->G
后序：D->E->B->F->G->C->A
层序：A->B->C->D->E->F->G

2. 常见算法

**求树的高度：**递归计算左右子树高度取最大值加1。
**判断平衡二叉树：**递归检查每个节点的高度差。
路径和问题： DFS遍历所有路径，计算满足条件的路径和。

四、树的应用场景

类型	典型应用	优势
二叉树	表达式解析、霍夫曼编码	结构简单，适合快速遍历
AVL树	内存数据库索引、符号表	严格平衡，查找效率稳定O(log n)
B树/B+树	文件系统、关系型数据库索引	减少磁盘I/O，适合外存数据管理
红黑树	操作系统调度、关联容器	近似平衡，插入/删除效率高
Trie树	字典查询、拼写检查	前缀匹配高效，节省存储空间

五、高级扩展

1. B+树（B+Tree)

**特性：**所有数据存储在叶子节点，内部节点仅存储索引。
**优势：**支持范围查询，磁盘访问更高效。
示例：

2. 线段树（Segment Tree)

**用途：**高效处理区间查询和更新（如求区间最大值、和)。
**结构：**每个节点存储一个区间的信息，叶子节点对应单个元素。

3. 并查集（Disjoint Set Union,DSU)

用途: 动态处理集合合并与查询。
**优化：**路径压缩和按秩合并，时间复杂度接近 O(1)。

六、总结

1
树是计算机科学中最基础且灵活的数据结构之一，其设计思想深刻影响了算法、操作系统、数据库等领域。从简单的二叉树到复杂的B+树，每种类型都针对特定场景进行了优化。掌握树的核心概念和应用，将为解决实际问题提供强大的工具。

Hello,树#

一、树的基本概念#

关键术语示例#

二、树的分类与特性#

1. 二叉树（Binary Tree)#

二叉树变种：#

示例：插入导致不平衡的处理#

B树(m=3)示例：#

三、树的操作与算法#

1. 遍历方式#

示例(二叉树)#

2. 常见算法#

四、树的应用场景#

五、高级扩展#

1. B+树（B+Tree)#

2. 线段树（Segment Tree)#

3. 并查集（Disjoint Set Union,DSU)#

六、总结#