数据结构与算法(七)：树型结构的变种

二叉树的各种变种：通过在基本二叉树（每个节点最多有两个子节点）的基础上增加不同的规则或约束，来满足特定的性能要求或应用场景。

二叉搜索树

• 定义与特点：虽然是最基础的变种，但它是许多高级结构的基础。其核心特点是：对于树中的任意节点，其左子树上所有节点的值都小于它，其右子树上所有节点的值都大于它。

• 设计目的：为了实现高效的查找、插入和删除操作。在树平衡的情况下，这些操作的时间复杂度为 O(log n)。

• 缺点：如果插入的数据是有序的（如1,2,3,4,5），它会退化成一条链表，查找效率降至 O(n)。

• 举例：

          5
         / \
        3   7
       / \   \
      1   4   9
  

自平衡二叉搜索树

这是为了解决BST可能退化的问题而设计的一系列变种。它们通过在插入或删除操作后执行旋转等操作来自动保持树的平衡。

AVL 树

• 定义与特点：它要求对于树中的任意节点，其左子树和右子树的高度差（平衡因子）绝对值不超过1。这是通过四种旋转操作（左旋、右旋、左右旋、右左旋）来维持的。
• 优点：严格的平衡保证了查询性能是所有BST中最优的，几乎完全是O(log n)。
• 缺点：为了维持高度平衡，插入和删除操作可能需要更多的旋转操作，因此在频繁修改的场景下性能稍差。
• 适用场景：查询密集型应用，且数据集不常修改。

红黑树

• 定义与特点：通过一组复杂的规则（涉及节点颜色——红色或黑色）来近似平衡，确保从根到叶子的最长路径不会超过最短路径的两倍。
• 优点：虽然不如AVL树那样完全平衡，但其平衡性足以保证查找、插入、删除操作的时间复杂度为O(log n)。更重要的是，它在插入和删除操作中需要的旋转次数更少，性能更稳定。
• 缺点：平均查询效率略低于AVL树。
• 适用场景：需要高效插入、删除和查询的综合场景。是工业界应用最广泛的平衡BST，例如：
  • Java中的 TreeMap, TreeSet
  • C++ STL中的 std::map, std::set
  • Linux内核的进程调度器

堆（Heap） - 完全二叉树变种

• 定义与特点：堆是一种完全二叉树，它满足堆序性质：
  • 最大堆：父节点的值大于或等于其所有子节点的值。根节点是最大值。
  • 最小堆：父节点的值小于或等于其所有子节点的值。根节点是最小值。
• 设计目的：快速访问最大值或最小值，而不是进行任意查找。
• 适用场景：优先队列、堆排序、图算法（如Dijkstra算法）。

线索二叉树

• 定义与特点：在二叉树的基础上，利用原本为空的左指针指向节点的前驱，右指针指向节点的后继（根据某种遍历顺序，如中序）。这些指向前驱和后继的指针被称为“线索”。
• 设计目的：在不使用递归或栈的情况下，更快地进行中序（或其他顺序）遍历，并且可以随时直接找到某个节点的前驱或后继。
• 优点：节省了遍历时所需的栈空间，加快了遍历速度。
• 缺点：插入和删除操作更复杂，需要维护线索。

其他重要变种

满二叉树

• 定义：除叶子节点外，每个节点都有两个子节点。或者说，每一层的节点数都达到了最大值。

完全二叉树

• 定义：除最后一层外，其他层的节点数都达到最大值，且最后一层的节点都集中在左边。堆就是基于完全二叉树实现的。

霍夫曼树（最优二叉树）

• 定义与特点：一种带权路径长度最短的二叉树。它不遵循BST的规则，而是根据叶子节点的权值（如字符频率）来构建：权值越大的节点离根越近。
• 设计目的：用于数据压缩（如ZIP文件）和编码（如霍夫曼编码），出现频率高的字符用更短的编码表示。

伸展树

• 定义与特点：一种自调整形式的BST。它不严格保持平衡，但最近被访问的节点会被“伸展”到根节点的位置。
• 设计目的：利用“局部性原理”（最近访问的数据很可能再次被访问），为后续的访问提供更快的速度。它不需要存储任何额外信息（如平衡因子、颜色）。

替罪羊树

• 定义与特点：另一种非旋转的自平衡BST。它通过一个权重平衡因子α（如0.5）来监控树的平衡。当某个节点的不平衡度超过阈值时，就以该节点为根，将其子树拍平并重构为一棵完全平衡的二叉树。
• 优点：无需旋转，概念简单。

总结对比表

变种名称	核心规则/特点	主要优点	典型应用场景
BST	左 < 父 < 右	简单，平均效率高	基础查找
AVL树	严格平衡（高度差≤1）	查询速度极快	数据库索引（查询为主）
红黑树	近似平衡（通过颜色规则）	插入删除效率高，综合性能好	系统库（Map/Set）、内核调度
堆	父 > 所有子（最大堆）或 父 < 所有子（最小堆），且是完全二叉树	快速访问最大/最小值 O(1)	优先队列、堆排序
线索二叉树	空指针指向前驱/后继	无需栈进行遍历，节省空间	需要频繁遍历和查找前驱后继的场景
霍夫曼树	带权路径最短（权大节点离根近）	数据压缩效率高	文件压缩（ZIP）、编码
伸展树	最近访问的节点移动到根	利用局部性，访问过的节点更快	缓存、垃圾回收算法
替罪羊树	不平衡时重构子树	无需旋转，概念简单	算法竞赛、教学