树的基础概念

树的基础概念

1. 理解树的基本术语

树是由节点（Node）组成的层次结构，每个节点通过边连接。以下是树的基本术语：

  • 节点：树的基本单位，包含数据和指向其他节点的连接。
    • 节点结构：通常包含以下信息：
      1. 父节点的地址（如果有）。
      2. 节点的值。
      3. 子节点的地址列表。
  • 子节点：某节点的直接下属节点，表示该节点的分支。
  • 父节点：某节点的直接上级节点，连接到该节点的上一层。
  • 兄弟节点：同一父节点的子节点。
  • 叶子节点：没有子节点的节点，通常表示树的末端。
  • 非叶子节点：至少有一个子节点的节点。
  • 节点的度：节点拥有的子节点数量。例如，度为 0 的节点是叶子节点。
  • 节点的高度：从该节点到叶子节点的最长路径的边数。
  • 节点的深度：从根节点到该节点的路径的边数。
  • 树的高度：从根节点到最深叶子节点的最长路径。
  • 树的深度：树中所有节点的最大深度。
  • 层次：节点的层级，从根节点开始为第 1 层，依次递增。
  • 说明：
    • A 是根节点，深度为 0，高度为 2。
    • B 和 C 是子节点，深度为 1，高度为 1。
    • D、E 和 F 是叶子节点，深度为 2，高度为 0。
    • 树的深度为 2（所有节点的最大深度）。

2. 掌握树的基本结构

树的结构具有递归特性，每个子树本身也是一棵树。

  • 递归性质：树的定义具有递归特性，便于通过递归算法进行操作。

以下是树的递归性质的示意图：

研究特殊的树结构

1. 二叉树

  • 定义：每个节点的度（子节点数量）最多为 2。
  • 性质：
    • 第 i 层最多有 2^(i-1) 个节点。
    • 深度为 k 的二叉树最多有 2^k - 1 个节点。
    • 所有叶子节点的深度差不超过 1。

2. 二叉查找树

  • 定义：二叉树的一种，满足以下性质：
    1. 左子节点的值小于父节点。
    2. 右子节点的值大于父节点。
  • 性质：
    • 中序遍历二叉查找树可以得到一个递增序列。
    • 根节点的值介于左子树的最大值和右子树的最小值之间。

3. 平衡二叉树

  • 定义：任意节点的左右子树高度差不超过 1。
  • 优势：提高查找效率，避免退化为链表。
  • 性质：
    • 每个节点的高度由其子节点的高度决定。
    • 树的高度接近 log(n)，其中 n 是节点总数。

4. 旋转操作

  • 定义：调整树的结构以保持平衡。
  • 术语：
    • 左旋：将右子节点提升为父节点，原父节点成为左子节点。
    • 右旋：将左子节点提升为父节点，原父节点成为右子节点。
  • 组合旋转：
    1. 左左（LL）：连续两次右旋。
    2. 左右（LR）：先左旋，再右旋。
    3. 右左（RL）：先右旋，再左旋。
    4. 右右（RR）：连续两次左旋。

5. 红黑树

  • 定义：一种自平衡二叉查找树。
  • 规则：
    1. 节点是红色或黑色。
    2. 根节点是黑色。
    3. 红色节点的子节点必须是黑色。
    4. 从任意节点到其每个叶子节点的路径中，黑色节点的数量相同。
  • 性质：
    • 树的高度接近 log(n)。
    • 通过颜色规则保持平衡。

参考资料

  1. 《数据结构与算法分析》 - Mark Allen Weiss
  2. 《算法导论》 - Thomas H. Cormen 等
  3. 维基百科 - 树 (数据结构)