C 语言中的 Treaps
4.83/5 (11投票s)
C 语言中的 Treap 实现
引言
Treap 是一种数据结构，它结合了堆（binary heap）和二叉搜索树（BST）。它是一种自组织、自平衡的数据结构。与 AVL 树或红黑树等其他自平衡树相比，它的主要优势在于实现简单且性能相当不错。在实现其他数据结构（如优先级队列）时，它可以作为一种高效的后端。Treap 上所有操作的时间复杂度都是 O(log n)，这使其成为一种非常有吸引力的数据结构。
有关这种数据结构的更多详细信息，我鼓励读者参考 Wikipedia 上简洁而精彩的描述。
在本文的其余部分，我将假设读者对数据结构构建和维护的原理已有基本了解。
背景
最近我需要用 C 实现一个优先级队列。我花了一段时间思考该使用哪种数据结构？我的第一个想法当然是 堆。访问具有最低优先级的元素是 O(1)，这正是我所需要的。但我的另一个要求是能够快速找到任何元素，而不仅仅是具有最低优先级的那个。这就有问题了。考虑数组堆的实现，查找具有最低优先级的元素将是 O(1)，但查找任何其他（随机访问）元素将是 O(n)。如果你的堆很小，这可以接受，但随着大小的增加，性能会迅速下降。
经过一些研究，我最终决定使用 Treap。使用 Treap 会使查找具有最低优先级的元素变慢。它是 O(log n)，但随机查找元素也同样是 O(log n)，这似乎是一个公平的权衡。
当然，如果你的随机数生成器非常差，Treap 中的查找时间可能会恶化，任何操作甚至可能达到 O(n)。但在大多数情况下，使用标准的 POSIX rand()，我得到了相当令人满意的结果。
实现细节
我引入了两种数据类型来实现 Treap。必不可少的一种代表 Treap 的节点。它包含堆的优先级、实际数据以及指向子节点的 BST 指针。这是最基本的需求，但大多数时候我喜欢有一个包装器，将数据结构本身作为一个单独的实体来表示。这样我可以存储一些额外的信息。
/**
* @brief leaf enumeration
*/
typedef enum _treap_leaf {
L_LEFT = 0,
L_RIGHT,
L_MAX,
} treap_leaf;
/**
* @brief treap node declaration
*/
struct treap_node {
struct treap_node *l[L_MAX];
/* random priority */
int p;
/* the data */
treap_data_t d;
};
/**
* @brief treap data type declaration
*/
struct treap {
struct treap_node *root;
treap_cmp_t cmp;
size_t n;
};
使用代码
有一些先决条件。该实现提供了朴素的类型无关性。正如 `struct treap_node` 声明所示，需要 `treap_data_t` 类型定义。另一件事是 `struct treap` 定义中可见的 `treap_cmp_t`。这是一个对封装的数据类型进行操作的比较函数。`treap.h` 头文件要求在包含路径中存在 `treap_data_type.h` 头文件。该头文件应定义 `treap_data_t` 并声明上述比较函数。这里有一个 `int` 的示例
typedef int treap_data_t;
int treap_int_cmp(treap_data_t *a, treap_data_t *b);
比较函数在格式上与标准库的 qsort 使用的几乎相同。它的作用也应该相同。示例文本可能看起来像这样
int treap_int_cmp(treap_data_t *a, treap_data_t *b) {
return (*a > *b ? 1 : (*a == *b ? 0 : -1));
}
这些都是先决条件。为了使用 Treap，需要对其进行分配。该实现提供了一组统一的 API 来操作它。示例如下
void treap_usage() {
struct treap *t = treap_alloc();
struct treap_node *n = NULL;
int min, max;
t->cmp = treap_int_cmp;
treap_insert(t, 123);
treap_insert(t, 456);
treap_insert(t, 789);
n = treap_find(t, 456);
if (n) treap_delete(t, n);
min = treap_min(t)->d;
max = treap_max(t)->d;
treap_dealloc(t);
}
提供了以下一组操作（大多数函数名是不言自明的，Doxygen 文档包含了其余必要的详细信息）
-
treap_alloc
-
treap_dealloc
-
treap_insert
-
treap_delete
-
treap_modify
-
treap_traverse_in
-
treap_traverse_level
-
treap_max_height_get
-
treap_balance_factor_get
-
treap_parent_find
-
treap_find
-
treap_min
-
treap_max
关注点
基于该数据结构实现的优先级队列表现相当不错。在我的用例中，需要同时具有随机访问和最低优先级元素访问，性能非常令人满意。它比数组堆实现和线性搜索要好得多。
关于该数据结构的自平衡能力，我也为其实现编写了一套简单的测试。一个测试用例（它实际上不做任何代码验证）将 10000 个元素按排序顺序插入 Treap，然后删除其中三分之一，再插入另外 10000 个。目的是只测量树的平衡因子。提醒一下，平衡因子是根节点的左子树和右子树之间的差值。它越接近零，平衡性越好。我做了一些测试。确实存在 rand() 没有提供均匀分布的随机数范围的情况，这显然会对平衡产生影响。然而，大多数时候平衡性相当好，尤其考虑到传入的数据总是以排序顺序插入。为了有一些参考，我运行了几次测试，这里是一些示例数字
32 次运行后。
平均平衡因子
#6667 个元素: -1.44
#10000 个元素: 0.59
#16667 个元素: -0.13
最佳观测平衡因子
#6667 个元素: 0
#10000 个元素: 1
#16667 个元素: 0
最差观测平衡因子
#6667 个元素: 13
#10000 个元素: 17
#16667 个元素: 14