Treap树从入门到精通（C++ Treap树实现详解）

什么是 Treap？

Treap 是一种平衡二叉搜索树（Balanced BST），它的每个节点包含两个值：

• key：用于维持二叉搜索树的性质（左子树 < 根 < 右子树）。
• priority：一个随机生成的优先级，用于维持堆的性质（通常为最大堆：父节点优先级 ≥ 子节点）。

由于 priority 是随机分配的，Treap 在期望情况下是平衡的，其高度为 O(log n)，因此所有操作的时间复杂度均为 O(log n)。

Treap 的核心操作：旋转（Rotation）

为了同时满足 BST 和 Heap 的性质，Treap 使用左旋（Left Rotate）和右旋（Right Rotate）来调整结构。这是实现插入和删除的关键。

右旋（Right Rotation）

// 右旋：将 y 作为新的根，x 成为其右子Node* rightRotate(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    // 执行旋转    x->right = y;    y->left = T2;    return x; // 新的根}

左旋（Left Rotation）

// 左旋：将 x 作为新的根，y 成为其左子Node* leftRotate(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    // 执行旋转    y->left = x;    x->right = T2;    return y; // 新的根}

C++ Treap 节点定义

首先，我们定义 Treap 的节点结构：

#include <iostream>#include <cstdlib> // 用于 rand()#include <ctime>   // 用于 srand(time(0))struct Node {    int key;          // 键值    int priority;     // 随机优先级    Node *left, *right;    Node(int k) {        key = k;        priority = rand(); // 随机生成优先级        left = right = nullptr;    }};

插入操作（Insert）

插入时，先按 BST 规则找到插入位置，然后通过旋转恢复堆性质：

Node* insert(Node* root, int key) {    // 1. 执行标准 BST 插入    if (!root)        return new Node(key);    if (key <= root->key) {        root->left = insert(root->left, key);        // 如果左子优先级更高，右旋        if (root->left->priority > root->priority)            root = rightRotate(root);    } else {        root->right = insert(root->right, key);        // 如果右子优先级更高，左旋        if (root->right->priority > root->priority)            root = leftRotate(root);    }    return root;}

完整 C++ Treap 示例代码

#include <iostream>#include <cstdlib>#include <ctime>using namespace std;struct Node {    int key, priority;    Node *left, *right;    Node(int k) : key(k), priority(rand()), left(nullptr), right(nullptr) {}};Node* rightRotate(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    x->right = y;    y->left = T2;    return x;}Node* leftRotate(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    y->left = x;    x->right = T2;    return y;}Node* insert(Node* root, int key) {    if (!root) return new Node(key);    if (key <= root->key) {        root->left = insert(root->left, key);        if (root->left->priority > root->priority)            root = rightRotate(root);    } else {        root->right = insert(root->right, key);        if (root->right->priority > root->priority)            root = leftRotate(root);    }    return root;}void inorder(Node* root) {    if (root) {        inorder(root->left);        cout << "(" << root->key << ", " << root->priority << ") ";        inorder(root->right);    }}int main() {    srand(time(0)); // 初始化随机种子    Node* root = nullptr;    root = insert(root, 10);    root = insert(root, 20);    root = insert(root, 5);    root = insert(root, 15);    cout << "中序遍历 (key, priority):\n";    inorder(root);    cout << endl;    return 0;}

为什么选择 Treap？

相比 AVL 树或红黑树，Treap 的实现更简单，且通过随机化保证了期望平衡。它是学习随机化平衡树的理想起点，也是竞赛和面试中的热门数据结构。

总结

本文详细讲解了 C++ Treap树实现 的原理与代码，包括节点定义、旋转操作、插入逻辑，并提供了完整可运行的示例。Treap 是一种优雅而高效的平衡二叉搜索树C++实现方式，特别适合初学者理解平衡树的核心思想。

掌握 Treap 后，你可以进一步探索删除操作、区间查询、分裂与合并等高级功能。希望这篇教程能帮助你轻松入门 Treap 数据结构！

关键词：C++ Treap树实现, Treap数据结构教程, 平衡二叉搜索树C++, 随机化平衡树