CC++ & Algorithm

Treap：树+堆的随机平衡术

较难2
语言版本：C++
概述：Treap是一种结合了二叉搜索树和堆的平衡树，通过给每个节点随机优先级来保证树高期望为对数级别。

Treap：当树遇上堆，平衡变得简单又随机

什么是Treap？它用来干什么？

Treap 是“Tree”（树）和“Heap”（堆）两个单词的组合。它既是一棵二叉搜索树（BST），又是一个堆。我们可以把它想象成一个小游戏：

班里同学去春游，老师让大家按身高排队（二叉搜索树规则：左边的同学比自己矮，右边的同学比自己高）。但是呢，每个人又抽到了一张神秘的“幸运数字”卡片，要求数字大的同学必须站在数字小的同学上面（堆的性质：大根堆中父节点优先级大于子节点）。这样身高和随机数字共同决定了队伍的最终形状——队伍（树）就不会长得歪歪扭扭、特别高了。

Treap 的核心思想是：给每个节点赋予一个随机优先级（priority），然后通过“旋转”操作，既保持二叉搜索树的有序性，又让优先级满足堆的性质。因为优先级是随机的，所以树的高度期望值是 O(log⁡n)O(\log n)，即使输入的数据是有序的，Treap 也能自动“搅拌均匀”。

一、节点结构：每个小朋友都带着两个数据

在写代码之前，我们先设计好“小朋友”长什么样。每个节点包含：

  • key：关键字（比如身高、分数）
  • prio：随机优先级（可以用 rand() 生成）
  • left 和 right：指向左、右孩子
struct Node {
    int key;                 // 关键字，比如考试成绩
    int prio;                // 随机优先级，决定堆结构
    Node *left, *right;      // 左孩子、右孩子指针
    Node(int k) : key(k), prio(rand()), left(nullptr), right(nullptr) {}
    // 构造函数：创建新节点时，key 由你指定，prio 随机生成
};

二、核心操作：左旋和右旋——给队伍“扭一扭”

旋转是 Treap 的“魔法”，它能在不破坏二叉搜索树性质的前提下，调整节点的上下位置，从而修复堆性质。想象一下，你在排队时和前面的人交换位置，但队伍的“大小关系”不变——小个子依然在左边，大个子依然在右边。

右旋：当左孩子的优先级比父节点高时（即左孩子应该站在上面），我们把父节点“扭”到右下方，让左孩子升上来。

     p                 q
    / \               / \
   q   C     =>       A   p
  / \                    / \
 A   B                  B   C

左旋：当右孩子的优先级比父节点高时，把父节点“扭”到左下方。

   p                     q
  / \                   / \
 A   q        =>       p   C
    / \               / \
   B   C             A   B

代码实现如下（注意：这里我们用的是小根堆，即优先级越小越在上面，所以判断条件是 prio <）：

void rotate_right(Node* &p) {   // 对节点 p 进行右旋，p 是当前子树的根
    Node* q = p->left;          // q 是 p 的左孩子
    p->left = q->right;         // p 的左指针指向 q 的右子树
    q->right = p;               // q 的右指针指向 p
    p = q;                      // 更新根为 q
}

void rotate_left(Node* &p) {    // 对节点 p 进行左旋
    Node* q = p->right;         // q 是 p 的右孩子
    p->right = q->left;         // p 的右指针指向 q 的左子树
    q->left = p;                // q 的左指针指向 p
    p = q;                      // 更新根为 q
}

三、插入操作：先放叶子，再“冒泡”上浮

插入一个数字（比如 85分）时，步骤如下：

  1. 先按二叉搜索树的规则：比当前节点小就往左走，比当前节点大就往右走，直到找到空位，把新节点插在叶子处。
  2. 插入后，检查新节点的优先级是否比它的父亲小（因为小根堆要求父节点优先级更小）。如果小，就通过旋转让新节点“冒泡”上去，直到堆性质满足。

这样，新插入的元素就像气泡一样，随机地向上浮，最终停在合适的高度。

代码中已经给出了插入的实现，我们可以再把它拆解得清楚一点：

void insert(Node* &p, int key) {   // 向以 p 为根的树中插入 key
    if (!p) {                        // 如果当前是空位置，直接创建新节点
        p = new Node(key);
        return;
    }
    if (key < p->key) {              // 比当前节点小，往左子树插
        insert(p->left, key);
        // 插入完成后，检查左孩子的优先级是否比当前节点小（小根堆）
        if (p->left->prio < p->prio)
            rotate_right(p);         // 左孩子优先级更小，应该升上来，右旋
    } else if (key > p->key) {       // 比当前节点大，往右子树插
        insert(p->right, key);
        if (p->right->prio < p->prio)
            rotate_left(p);          // 右孩子优先级更小，左旋
    }
    // 如果 key 相等，则什么都不做（不重复插入）
}

四、删除操作：旋转到叶子，再轻轻剪掉

删除比插入稍微复杂一点：不能直接删，因为会破坏堆结构。策略是把要删除的节点旋转到叶子位置，再删掉。

具体步骤：

  1. 找到要删除的节点（比如 key = 85）。
  2. 如果它没有左孩子或右孩子，直接删除并让父节点指向剩下的孩子。
  3. 如果它有两个孩子，就比较左右孩子的优先级：
    • 如果左孩子优先级更小（小根堆中优先级小在上面），就右旋，让左孩子顶上来，原节点沉到右边；
    • 否则左旋，让右孩子顶上来，原节点沉到左边。
  4. 旋转后，原节点变成了叶子（或有一个孩子），接着递归删除它（回到第2步）。

代码实现：

void erase(Node* &p, int key) {     // 从以 p 为根的树中删除 key
    if (!p) return;                  // 没找到，直接返回
    if (key < p->key) {
        erase(p->left, key);         // 到左子树删除
    } else if (key > p->key) {
        erase(p->right, key);        // 到右子树删除
    } else {                         // 找到了！
        // 情况1：至少有一个孩子是空
        if (!p->left || !p->right) {
            Node* temp = p;
            p = (p->left) ? p->left : p->right;  // 用非空孩子替换
            delete temp;               // 释放内存
        } else {
            // 有两个孩子：比较优先级，旋转下去
            if (p->left->prio < p->right->prio) {  // 左孩子优先级更小
                rotate_right(p);
                erase(p->right, key);   // 原节点现在在右子树中
            } else {
                rotate_left(p);
                erase(p->left, key);
            }
        }
    }
}

五、查找操作：和普通BST一样简单

Treap 的查找完全依赖二叉搜索树的性质，优先级不影响查找，所以就是普通的递归或循环比较。

bool find(Node* p, int key) {
    if (!p) return false;
    if (key == p->key) return true;
    if (key < p->key) return find(p->left, key);
    else return find(p->right, key);
}

六、随机优先级为什么能“保证”平衡？

你可能会问：随机数字能靠谱吗？万一抽到坏运气怎么办？

真相是：虽然最坏情况下（极其小的概率）树可能退化成链表，但期望高度是 O(log⁡n)O(\log n) 的。就像掷硬币，连续100次正面可能性极低。在编程竞赛中，我们通常相信随机带来的效果比手写平衡因子更稳定，而且代码简单得多。

实际上，很多Treap实现使用大根堆（优先级大的在上面），原理一样，只需把小于号换成大于号。两种都行，选一种即可。

七、新手容易犯的错误

  1. 忘记初始化随机种子：srand(time(0)) 必须在程序开头调用一次，否则每次运行 rand() 结果一样，平衡效果消失。
  2. 递归深度过大：如果插入的数据极多（比如10万），递归写法可能导致栈溢出。可以用非递归（循环）或调大编译栈空间。但作为学习，递归更易懂。
  3. 旋转后忘记更新引用：rotate_* 函数参数是 Node* &p，这样旋转后根指针自动更新。如果忘记写引用，根指针不会改变，树就乱了。
  4. 删除时忘记释放内存：C++ 中 new 出来的节点要用 delete 释放，否则内存泄漏。虽然小数据没事，但养成好习惯。
  5. 优先级比较方向搞反：确认自己用的是小根堆还是大根堆，插入和删除时条件要一致。本示例代码用的是小根堆（优先级越小的越在上面）。

八、完整可运行代码（带中序遍历验证）

下面是一个完整的程序，包含插入、删除、查找和中序遍历（输出有序序列）来验证 Treap 的正确性。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;                 // 关键字
    int prio;                // 随机优先级
    Node *left, *right;      // 左右孩子
    Node(int k) : key(k), prio(rand()), left(nullptr), right(nullptr) {}
};

void rotate_right(Node* &p) {
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    p = q;
}

void rotate_left(Node* &p) {
    Node* q = p->right;
    p->right = q->left;
    q->left = p;
    p = q;
}

void insert(Node* &p, int key) {
    if (!p) {
        p = new Node(key);
        return;
    }
    if (key < p->key) {
        insert(p->left, key);
        if (p->left->prio < p->prio) rotate_right(p);
    } else if (key > p->key) {
        insert(p->right, key);
        if (p->right->prio < p->prio) rotate_left(p);
    }
    // 相等不处理
}

void erase(Node* &p, int key) {
    if (!p) return;
    if (key < p->key) {
        erase(p->left, key);
    } else if (key > p->key) {
        erase(p->right, key);
    } else {
        if (!p->left || !p->right) {
            Node* temp = p;
            p = (p->left) ? p->left : p->right;
            delete temp;
        } else {
            if (p->left->prio < p->right->prio) {
                rotate_right(p);
                erase(p->right, key);
            } else {
                rotate_left(p);
                erase(p->left, key);
            }
        }
    }
}

bool find(Node* p, int key) {
    if (!p) return false;
    if (key == p->key) return true;
    if (key < p->key) return find(p->left, key);
    else return find(p->right, key);
}

void inorder(Node* p) {               // 中序遍历，输出升序序列
    if (!p) return;
    inorder(p->left);
    cout << p->key << " ";
    inorder(p->right);
}

int main() {
    srand(time(0));                   // 初始化随机种子
    Node* root = nullptr;

    // 插入一些数字（比如班级成绩）
    int scores[] = {85, 92, 78, 90, 88, 76, 95};
    for (int s : scores) {
        insert(root, s);
        cout << "插入 " << s << " 后中序遍历: ";
        inorder(root);
        cout << endl;
    }

    // 查找
    cout << "查找 88: " << (find(root, 88) ? "找到" : "未找到") << endl;
    cout << "查找 100: " << (find(root, 100) ? "找到" : "未找到") << endl;

    // 删除
    cout << "删除 78" << endl;
    erase(root, 78);
    cout << "删除后中序遍历: ";
    inorder(root);
    cout << endl;

    // 再次查找
    cout << "查找 78: " << (find(root, 78) ? "找到" : "未找到") << endl;

    return 0;
}

运行效果示例（每次结果因随机种子不同而不同，但中序遍历始终有序）：

插入 85 后中序遍历: 85 
插入 92 后中序遍历: 85 92 
插入 78 后中序遍历: 78 85 92 
...
删除 78
删除后中序遍历: 85 88 90 92 95
查找 78: 未找到

九、相关知识点指引

  • Splay树：另一种基于伸展（旋转）的平衡树，常用在区间操作（如文艺平衡树）。
  • 红黑树：C++ STL 中 set 和 map 的底层实现，要求平衡更严格（但代码复杂）。
  • FHQ Treap（无旋Treap）：不需要旋转，通过分裂和合并实现，代码更简洁，适合持久化。
  • 左偏树：一种可并堆，类似堆但能高效合并。
  • 堆排序：用堆（优先队列）排序，时间复杂度 O(nlog⁡n)O(n\log n)。

总结：Treap 用随机性换来了简单优雅的平衡实现，是学习平衡树非常好的起点。你不需要记住复杂的平衡因子，只要会旋转、会递归，就能写出一棵能用的平衡树。快去试试自己动手写一个吧！

例题精讲

1单选题

在Treap中，为了维护堆性质，当插入一个新节点时，如果其优先级大于其父节点（假设使用大根堆），应采取什么操作？

A左旋
B右旋
C先左旋后右旋
D无需旋转
2单选题

下列关于Treap随机优先级的设计，哪一项是正确的？

A优先级必须互不相同，否则无法保证平衡
B优先级通常用真实随机数生成，以保证确定性
C优先级可以相同，但需要特殊处理以避免破坏堆性质
D优先级值越大越靠近根，因此可以人为设定为节点值本身
3判断题

Treap的期望时间复杂度为O(log n)，但最坏情况下可能退化为O(n)。

4填空题
在Treap插入的递归过程中，当插入到左子树后，如果左子节点优先级大于当前节点，需要进行旋转。请写出第一个填空处应填的代码（使用已经定义的rotate函数）。
5填空题
在查找第k小元素的递归过程中，如果k小于等于左子树的大小，则答案在左子树中。请写出第一个填空处应填的代码。