C语言Treap树实现（从零开始掌握随机化平衡二叉搜索树）

Treap 的核心操作：旋转

为了同时满足 BST 和堆的性质，Treap 使用左旋（rotate left）和右旋（rotate right）来调整结构。

右旋（Right Rotation）

// 右旋：以 y 为根，x 为其左孩子Node* rotateRight(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    // 执行旋转    x->right = y;    y->left = T2;    // 返回新的根节点    return x;}  

左旋（Left Rotation）

// 左旋：以 x 为根，y 为其右孩子Node* rotateLeft(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    // 执行旋转    y->left = x;    x->right = T2;    // 返回新的根节点    return y;}  

C语言Treap树实现完整代码

下面我们用 C 语言完整实现一个支持插入、查找和中序遍历的 Treap。

#include <stdio.h>#include <stdlib.h>#include <time.h>// 节点结构typedef struct Node {    int key;    int priority;    struct Node *left, *right;} Node;// 创建新节点Node* newNode(int key) {    Node* node = (Node*)malloc(sizeof(Node));    node->key = key;    node->priority = rand(); // 随机优先级    node->left = node->right = NULL;    return node;}// 右旋Node* rotateRight(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    x->right = y;    y->left = T2;    return x;}// 左旋Node* rotateLeft(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    y->left = x;    x->right = T2;    return y;}// 插入节点Node* insert(Node* root, int key) {    // 1. 按 BST 规则插入    if (root == NULL) return newNode(key);    if (key <= root->key)        root->left = insert(root->left, key);    else        root->right = insert(root->right, key);    // 2. 检查堆性质，必要时旋转    if (root->left != NULL && root->left->priority > root->priority)        root = rotateRight(root);    if (root->right != NULL && root->right->priority > root->priority)        root = rotateLeft(root);    return root;}// 中序遍历（输出有序序列）void inorder(Node* root) {    if (root) {        inorder(root->left);        printf("%d(%d) ", root->key, root->priority);        inorder(root->right);    }}// 主函数测试int main() {    srand(time(NULL)); // 初始化随机种子    Node* root = NULL;    root = insert(root, 50);    root = insert(root, 30);    root = insert(root, 70);    root = insert(root, 20);    root = insert(root, 40);    printf("中序遍历（key(priority)）:\n");    inorder(root);    printf("\n");    return 0;}  

为什么选择 Treap？

相比 AVL 树或红黑树，Treap 的实现更简单，且不需要复杂的平衡因子或颜色标记。它的C语言平衡二叉搜索树特性使其在竞赛和实际工程中都有广泛应用。

此外，Treap 支持高效的区间操作（如分裂与合并），是实现可持久化数据结构的良好基础。

总结

通过本教程，你已经掌握了 随机化二叉搜索树 Treap 的基本原理和 C 语言实现。关键点包括：

• 每个节点有 key 和随机 priority
• 通过旋转维护堆性质
• 插入操作自动保持近似平衡

现在，你可以尝试扩展功能，比如实现删除、查找第 k 小元素等。坚持练习，你将熟练掌握这一优雅的数据结构！

记住，C语言Treap树实现不仅是面试加分项，更是理解高级数据结构的重要一步。