树的层次结构:

                    ┌─────┐
                    │  1  │ ← 根节点 (Root) - 第0层
                    └──┬──┘
                       │
          ┌────────────┼────────────┐
          │            │            │
       ┌──┴──┐      ┌──┴──┐      ┌──┴──┐
       │  2  │      │  3  │      │  4  │ ← 第1层
       └──┬──┘      └─────┘      └──┬──┘
          │                        │
      ┌───┴───┐                ┌───┴───┐
      │       │                │       │
   ┌──┴──┐  ┌──┴──┐          ┌──┴──┐  ┌──┴──┐
   │  5  │  │  6  │          │  7  │  │  8  │ ← 第2层
   └─────┘  └─────┘          └─────┘  └──┬──┘
                                         │
                                      ┌──┴──┐
                                      │  9  │ ← 第3层
                                      └─────┘

树的基本术语:
• 节点: 树中的每个元素 (1-9)
• 边: 连接节点的线
• 根: 树的顶部节点 (1)
• 叶子: 没有子节点的节点 (3, 5, 6, 7, 9)
• 父节点: 有子节点的节点 (1是2/3/4的父节点)
• 子节点: 父节点的下一层节点 (2/3/4是1的子节点)
• 兄弟节点: 同一父节点的子节点 (2,3,4互为兄弟)
• 路径: 从一个节点到另一个节点的边序列
• 深度: 从根到该节点的边数 (节点5深度=2)
• 高度: 从该节点到最深叶子的边数 (树高度=3)
• 度: 节点的子节点数 (节点1度=3)

树的分类体系:

树(Tree)
├── 按子节点数目
│   ├── 二叉树 (Binary Tree)
│   │   ├── 普通二叉树
│   │   ├── 满二叉树 (所有层都满)
│   │   ├── 完全二叉树 (最后一层左对齐)
│   │   ├── 二叉搜索树 BST
│   │   │   └── 左子树 < 根 < 右子树
│   │   ├── 平衡二叉树
│   │   │   ├── AVL树 (左右子树高度差≤1)
│   │   │   └── 红黑树
│   │   └── 堆 (Heap)
│   │       ├── 大顶堆 (父≥子)
│   │       └── 小顶堆 (父≤子)
│   │
│   └── 多叉树 (N-ary Tree)
│       ├── B树/B+树 (数据库索引)
│       ├── Trie树 (字符串检索)
│       └── 并查集 (不相交集合)
│
├── 按用途
│   ├── 搜索树 (BST, AVL, 红黑树)
│   ├── 优先队列 (堆)
│   ├── 区间树 (线段树)
│   ├── 字典树 (Trie)
│   └── 语法树 (表达式树、决策树)
│
└── 特殊性质
    ├── 哈夫曼树 (最优前缀编码)
    ├── 伸展树 (自调整)
    └──  Treap (随机化平衡)

二叉树的链式存储:

┌─────────┐
│  data   │
│   10    │
├─────────┤
│  left   │──→ ┌─────────┐
│  指针    │    │  data   │
├─────────┤    │   5     │
│  right  │─   ├─────────┤
│  指针    │ →  │  left   │──→ NULL
└─────────┘    ├─────────┤
               │  right  │──→ NULL
               └─────────┘

双亲表示法 (数组存储):
┌─────────┬─────────┬─────────┐
│ 索引    │  data   │  parent │
├─────────┼─────────┼─────────┤
│    0    │    1    │   -1    │ (根节点)
│    1    │    2    │    0    │
│    2    │    3    │    0    │
│    3    │    4    │    0    │
│    4    │    5    │    1    │
│   ...   │   ...   │   ...   │
└─────────┴─────────┴─────────┘

孩子兄弟表示法 (适合多叉树):
每个节点存储: data + first_child + next_sibling

       ┌─────┐
       │  1  │ first_child → 2
       └─┬───┘
         │ next_sibling
         ↓
       ┌─────┐
       │  2  │ first_child → 5
       └─┬───┘
         │ next_sibling
         ↓
       ┌─────┐
       │  3  │ first_child → NULL
       └─┬───┘
         │ next_sibling
         ↓
       ┌─────┐
       │  4  │
       └─────┘

BST搜索过程 (查找 40):

       ┌─────┐
       │ 50  │
       └─┬───┘
         │
    ┌────┴────┐
    ↓         ↓
  ┌───┐     ┌───┐
  │ 30│     │ 70 │
  └──┬┘     └─┬─┘
     │         │
  ┌──┴──┐   ┌──┴──┐
  ↓     ↓   ↓     ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 20│ │ 40│ │ 60│ │ 80│
└───┘ └───┘ └───┘ └───┘

步骤:
1. 从根50开始，40 < 50，进入左子树
2. 比较30，40 > 30，进入右子树
3. 比较40，40 == 40 ✓ 找到!

时间复杂度: O(h)，h为树高度
平衡时 h=log n，最坏时 h=n

BST插入过程 (插入 35):
1. 50 → 左子树 (30)
2. 30 → 右子树 (40)
3. 40 → 左子树 (NULL)
4. 在40的左子树位置插入35

       ┌─────┐
       │ 50  │
       └─┬───┘
         │
    ┌────┴────┐
    ↓         ↓
  ┌───┐     ┌───┐
  │ 30│     │ 70 │
  └──┬┘     └─┬─┘
     │         │
  ┌──┴──┐   ┌──┴──┐
  ↓     ↓   ↓     ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 20│ │ 40│ │ 60│ │ 80│
└───┘ └─┬─┘ └───┘ └───┘
        ↓
      ┌───┐
      │ 35│ (新节点)
      └───┘

平衡因子 = 左子树高度 - 右子树高度
平衡因子 ∈ {-1, 0, 1} → 平衡
平衡因子 < -1 或 > 1 → 不平衡，需要旋转

平衡因子计算:
       ┌─────┐
       │ 30  │ ← 平衡因子 = 0 (左右高度都是2)
       └─┬───┘
         │
    ┌────┴────┐
    ↓         ↓
  ┌───┐     ┌───┐
  │ 20│     │ 40│
  └──┬┘     └─┬─┘
     │         │
  ┌──┴──┐   ┌──┴──┐
  ↓     ↓   ↓     ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 10│ │ 25│ │ 35│ │ 50│
└───┘ └───┘ └───┘ └───┘

不平衡情况及旋转:

情况1: 左左不平衡 (LL) → 右旋
      30              20
     /               /  \
   20      →       10    30
  /                        \
10                         40

情况2: 右右不平衡 (RR) → 左旋
  30                    40
    \                  /  \
     40      →       30    50
       \
        50

情况3: 左右不平衡 (LR) → 先左旋再右旋
      30               30            25
     /                /            /  \
   20      →        25    →      20   30
     \            /
      25         20

时间复杂度:
搜索、插入、删除都是 O(log n) - 严格保证!

红黑树的五个性质:
1. 每个节点是红色或黑色
2. 根节点是黑色
3. 所有叶子(NIL)是黑色
4. 红色节点的子节点必须是黑色
   (不能有连续红色节点)
5. 从任一节点到其叶子的所有路径包含相同数目的黑色节点
   (黑高度相同)

红黑树结构示例:
       ┌─────┐
       │ 30B │ ← 根节点黑色
       └─┬───┘
         │
    ┌────┴────┐
    ↓         ↓
  ┌───┐     ┌───┐
  │20R│     │40R│ ← 红色节点
  └─┬─┘     └─┬─┘
    │         │
  ┌─┴─┐     ┌─┴─┐
  ↓   ↓     ↓   ↓
┌───┐┌───┐ ┌───┐┌───┐
│10B││25B│ │35B││50B│ ← 黑色叶子
└───┘└───┘ └───┘└───┘

为什么红黑树比AVL树更实用?
• AVL树严格平衡，插入删除需要更多旋转
• 红黑树插入最多2次旋转，删除最多3次旋转
• 红黑树查询略慢但插入删除更快
• 实际应用（如C++ map/set、Java TreeMap）多用红黑树

时间复杂度:
搜索、插入、删除都是 O(log n)

大顶堆结构:

        ┌─────┐
        │ 100 │ ← 堆顶，最大值
        └──┬──┘
           │
      ┌────┴────┐
      ↓         ↓
   ┌─────┐   ┌─────┐
   │ 80  │   │ 60  │
   └──┬──┘   └──┬──┘
      │         │
   ┌──┴──┐   ┌──┴──┐
   ↓     ↓   ↓     ↓
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
 │50 │ │30 │ │20 │ │10 │
 └───┘ └───┘ └───┘ └───┘

数组表示 (索引从1开始):
索引:  1    2    3    4    5    6    7
     ┌────┬────┬────┬────┬────┬────┐
     │100 │ 80 │ 60 │ 50 │ 30 │ 20 │ 10│
     └────┴────┴────┴────┴────┴────┘

节点关系:
• 父节点(i)的左子节点 = 2i
• 父节点(i)的右子节点 = 2i + 1
• 子节点(i)的父节点 = ⌊i/2⌋

插入操作 (插入 90):
1. 将90放到数组末尾
2. 上浮操作: 与父节点比较，若大于父节点则交换
3. 重复直到满足堆性质

      100                    100
     /   \       插入90      /   \
   80     60      →       90     60
  / \    /               /  \    /
50  30 20              80  30  20
                       /
                      50
                      交换90和80后 →
                      
      100                100
     /   \               /   \
   90     60            90     60
  / \    /             / \    /
80  30 20             80 30  20
/                     /
50                    50
                      无需再交换，完成!

删除堆顶:
1. 将堆顶与最后一个元素交换
2. 移除最后一个元素（原堆顶）
3. 下沉操作: 与子节点中较大者交换
4. 重复直到满足堆性质

时间复杂度:
• 建堆: O(n)
• 插入: O(log n)
• 删除堆顶: O(log n)
• 查询堆顶: O(1)

B+树结构 (阶数m=3):

                ┌─────────────────┐
                │     20     50   │
                └────────┬────────┘
                         │
         ┌───────────────┼───────────────┐
         │               │               │
    ┌────┴────┐     ┌────┴────┐     ┌────┴────┐
    │ 10   15 │     │ 30   40 │     │ 60   70 │
    └────┬────┘     └────┬────┘     └────┬────┘
         │               │               │
    ┌────┴────┐     ┌────┴────┐     ┌────┴────┐
    ↓         ↓     ↓         ↓     ↓         ↓
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐
│5│8│10 │→│12│15 │→│20│25 │→│30│35 │→│40│45 │→│50│55 │→│60│65 │→│70│75 │
└───────┘ └───────┘ └───────┘ └───────┘ └───────┘ └───────┘ └───────┘
 数据页    数据页    数据页    数据页    数据页    数据页    数据页
 
特点:
• 非叶子节点存键值，不存数据
• 叶子节点存实际数据，且有序连接
• 查询效率稳定: O(log n)
• 非常适合磁盘存储（减少I/O）

查找 35:
1. 根节点: 20 < 35 < 50 → 走中间分支
2. 中间节点: 30 < 35 < 40 → 走中间分支
3. 叶子节点: 找到35

范围查询 15-45:
1. 找到15所在的叶子
2. 顺着叶子链表遍历直到超过45
3. 返回15, 20, 25, 30, 35, 40

二叉树的三种DFS遍历:

      ┌─────┐
      │  F  │
      └─┬───┘
        │
   ┌────┴────┐
   ↓         ↓
 ┌───┐     ┌───┐
 │ B │     │ G │
 └─┬─┘     └───┘
   │
┌──┴──┐
↓     ↓
┌───┐ ┌───┐
│ A │ │ D │
└───┘ └─┬─┘
        │
     ┌──┴──┐
     ↓     ↓
   ┌───┐ ┌───┐
   │ C │ │ E │
   └───┘ └───┘

前序遍历 (根→左→右): F, B, A, D, C, E, G
中序遍历 (左→根→右): A, B, C, D, E, F, G
后序遍历 (左→右→根): A, C, E, D, B, G, F

遍历的应用:
• 前序: 复制树、序列化
• 中序: BST中得到有序序列
• 后序: 删除树、计算目录大小

层序遍历 (使用队列):

      ┌─────┐         队列: [F]           结果: []
      │  F  │
      └─┬───┘
        │
   ┌────┴────┐
   ↓         ↓
 ┌───┐     ┌───┐
 │ B │     │ G │
 └─┬─┘     └───┘
   │
┌──┴──┐
↓     ↓
┌───┐ ┌───┐
│ A │ │ D │
└───┘ └─┬─┘
        │
     ┌──┴──┐
     ↓     ↓
   ┌───┐ ┌───┐
   │ C │ │ E │
   └───┘ └───┘

过程:
1. 队列: [F]      出队F，入队B,G → 队列: [B,G]     结果: [F]
2. 队列: [B,G]    出队B，入队A,D → 队列: [G,A,D]   结果: [F,B]
3. 队列: [G,A,D]  出队G，无子节点 → 队列: [A,D]     结果: [F,B,G]
4. 队列: [A,D]    出队A，无子节点 → 队列: [D]       结果: [F,B,G,A]
5. 队列: [D]      出队D，入队C,E → 队列: [C,E]     结果: [F,B,G,A,D]
6. 队列: [C,E]    出队C，无子节点 → 队列: [E]       结果: [F,B,G,A,D,C]
7. 队列: [E]      出队E，无子节点 → 队列: []        结果: [F,B,G,A,D,C,E]

最终结果: F, B, G, A, D, C, E

应用:
• 查找最短路径（无权树）
• 按层打印树
• 查找某层的所有节点

┌─────────────────────────────────────────────────────────┐
│ 场景                           │ 推荐树结构              │
├────────────────────────────────┼──────────────────────┤
│ 需要动态排序                    │ BST/红黑树             │
│ 需要严格O(log n)保证            │ AVL树                 │
│ 频繁插入删除，偶尔查询            │ 红黑树                 │
│ 需要优先队列                    │ 堆                    │
│ 数据库索引                      │ B+树                  │
│ 前缀匹配（自动补全）              │ Trie树               │
│ 区间查询                        │ 线段树                │
│ 不相交集合合并                   │ 并查集                │
└────────────────────────────────┴──────────────────────┘