一文读懂：2-3-4树、红黑树、B树家族与哈夫曼树

一文读懂：2-3-4树、红黑树、B树家族与哈夫曼树

引用

CSDN

1.

https://blog.csdn.net/jukuya/article/details/145501244

在数据结构的世界里，树是一种非常重要的非线性结构。除了常见的二叉树，还有许多特殊类型的树，它们各自有着独特的性质和广泛的应用。本文将深入介绍2-3-4树、红黑树、B树、B+树和哈夫曼树，帮助读者全面理解这些特殊树结构的特点和应用场景。

2-3-4 树

基本概念

2-3-4 树是一种多路搜索树，它的每个节点可以有 2 个、3 个或 4 个孩子。每个 2 - 节点包含 1 个元素和 2 个孩子；3 - 节点包含 2 个元素和 3 个孩子；4 - 节点包含 3 个元素和 4 个孩子。并且所有叶子节点都在同一层。

特点

1. 自平衡：它始终保持平衡状态，避免了二叉搜索树在最坏情况下退化为链表的情况，保证了操作的时间复杂度为 O (log n)。
2. 插入和删除操作相对简单：通过节点的分裂和合并来维持树的结构和性质。

应用场景

在文件系统和数据库索引等需要高效查找和插入的数据场景中有应用。

红黑树

基本概念

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。

特点

1. 红黑性质：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 每个叶节点（NIL 节点，空节点）是黑色的。
• 如果一个节点是红色的，则它的两个子节点都是黑色的（即不能有两个连续的红色节点）。
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

1. 时间复杂度：保证了在最坏情况下，查找、插入和删除操作的时间复杂度为 O (log n) 。

应用场景

广泛应用于各种编程语言的集合类（如 Java 的 TreeMap 和 TreeSet）、C++ 的 STL 中的关联容器等，用于实现高效的排序和查找。

B 类树（B 树）

基本概念

B 树是一种多路平衡查找树，它的每个节点可以包含多个关键字和多个子节点。B 树的阶数 m 表示每个节点最多能有 m - 1 个关键字和 m 个子节点。

特点

1. 平衡：所有叶子节点都在同一层，保证了树的平衡，使得查找效率稳定。
2. 节点存储：节点可以存储多个关键字，减少了树的高度，从而减少了磁盘 I/O 操作次数（因为磁盘 I/O 操作相对较慢，减少 I/O 次数能提高效率）。

应用场景

主要用于文件系统和数据库索引，因为它能很好地适应磁盘等外存设备的读写特性，提高数据的检索效率。

B + 树

基本概念

B + 树是 B 树的一种变形，它与 B 树的主要区别在于：B + 树的所有数据都存储在叶子节点，非叶子节点只存储关键字和指向子节点的指针；叶子节点之间通过双向链表相连。

特点

1. 范围查询高效：由于叶子节点之间有链表相连，所以对于范围查询非常高效，只需要遍历链表即可。
2. 更适合外存：相比 B 树，B + 树的结构更紧凑，更适合在磁盘等外存设备上存储和查找数据。

应用场景

在数据库索引中广泛应用，尤其是在需要频繁进行范围查询的场景中，如数据库的查询优化。

哈夫曼树

基本概念

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。它根据给定的权值集合来构建，每个权值对应一个叶节点。

特点

1. 带权路径长度最小：通过贪心算法构建，使得整棵树的带权路径长度达到最小，从而实现数据的最优编码。
2. 应用于数据压缩：利用哈夫曼树可以对数据进行编码，将出现频率高的数据用较短的编码表示，出现频率低的数据用较长的编码表示，从而达到数据压缩的目的。

应用场景

主要应用于数据压缩领域，如哈夫曼编码在文件压缩、图像压缩等方面都有广泛应用。