无旋 Treap 学习笔记

无旋 Treap，又名 FHQ-Treap。无旋 Treap 仅有两种核心操作 —— 分裂与合并，它依靠这两种操作来维护树的平衡，从而省去了旋转操作。这种操作方式使得它天生支持维护序列、可持久化等特性。

本文提供使用原生指针和数组模拟指针两种方法实现的代码，可以点击代码块上方的切换按钮查看两种不同版本的代码。

前言

Treap 是一种弱平衡的二叉搜索树。它的数据结构由二叉树和二叉堆组合形成，名字也因此为 tree 和 heap 的组合。

Treap 的每个结点上除了按照二叉搜索树排序的 $\text{key}$ 值外要额外储存一个叫 $\text{priority}$ 的值。它由每个结点建立时随机生成，并按照最大堆性质排序。因此 Treap 除了要满足二叉搜索树的性质之外，还需满足父节点的 $\text{priority}$ 大于等于两个子节点的值。所以它是期望平衡的。搜索，插入和删除操作的期望时间复杂度为 $O(\log n)$ 。

主要操作

分裂

本节所介绍的分裂操作会按照排名将一棵树分裂为两棵子树，左子树包含 $k$ 个元素，右子树包含剩余元素。

分割时，如果左子树中元素个数不足 $k$ 个，就从右子树中分割 $k - \text{size}(\mathit{left}) - 1$ 个元素放置到左子树中，反之则从左子树中划分出 $\text{size}(\mathit{left}) - k$ 个元素放置到右子树中。

不要忘记 pushup。

std::pair<Treap::node *, Treap::node *> Treap::split(Treap::node *p, int k) {
    if (p == nullptr) return std::make_pair(nullptr, nullptr);
    std::pair<Treap::node *, Treap::node *> o;
    if (k <= getNodeSize(p->left)) {
        o = split(p->left, k);
        p->left = o.second;
        p->pushup();
        o.second = p;
    } else {
        o = split(p->right, k - getNodeSize(p->left) - 1);
        p->right = o.first;
        p->pushup();
        o.first = p;
    }
    return o;
}

std::pair<int, int> Treap::split(int p, int k) {
    if (!p) return std::make_pair(0, 0);
    if (k <= tr[tr[p].l].s) {
        auto o = split(tr[p].l, k);
        tr[p].l = o.second;
        pushup(p);
        o.second = p;
        return o;
    }
    auto o = split(tr[p].r, k - tr[tr[p].l].s - 1);
    tr[p].r = o.first;
    pushup(p);
    o.first = p;
    return o;
}

按值分裂

本节介绍的分裂操作将会按照元素值的大小将一棵树分裂为两棵子树，左子树中的元素均不大于 $\mathit{val}$ ，右子树中的元素均大于 $\mathit{val}$ 。

std::pair<Treap::node *, Treap::node *> Treap::splitByValue(Treap::node *p, int val) {
    if (p == nullptr) return std::make_pair(nullptr, nullptr);
    std::pair<Treap::node *, Treap::node *> o;
    if (p->val < val) {
        o = splitByValue(p->right, val);
        p->right = o.first;
        p->pushup();
        o.first = p;
    } else {
        o = splitByValue(p->left, val);
        p->left = o.second;
        p->pushup();
        o.second = p;
    }
    return o;
}

std::pair<int, int> Treap::splitByValue(int p, int v) {
    if (!p) return std::make_pair(0, 0);
    if (tr[p].v < v) {
        auto o = splitByValue(tr[p].r, v);
        tr[p].r = o.first;
        pushup(p);
        o.first = p;
        return o;
    }
    auto o = splitByValue(tr[p].l, v);
    tr[p].l = o.second;
    pushup(p);
    o.second = p;
    return o;
}

合并

合并操作也就是将两棵 Treap 合并成一棵 Treap，其中一颗 Treap 的所有点的权值均小于或大于另一颗 Treap 任意点的权值。

Treap::node *Treap::merge(Treap::node *x, Treap::node *y) {
    if (x == nullptr) return y;
    if (y == nullptr) return x;
    if (x->key > y->key) {
        x->right = merge(x->right, y);
        x->pushup();
        return x;
    }
    y->left = merge(x, y->left);
    y->pushup();
    return y;
}

int Treap::merge(int x, int y) {
    if (!x) return y;
    if (!y) return x;
    if (tr[x].k > tr[y].k) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    tr[y].l = merge(x, tr[y].l);
    pushup(y);
    return y;
}

内部工具库

获取子树大小

判断子树是否为空，若空返回 $0$ ，非空返回子树大小。

inline int Treap::getNodeSize(Treap::node *node) {
    return node == nullptr ? 0 : node->size;
}

查找元素 (find)

递归查找值为 $\mathit{val}$ 的元素，根据 BST 的性质即可进行。

递归到某个节点时，先判断当前节点的元素值大小，若查询值小于当前节点的元素值时则向左子树递归，反之则向右子树递归。时间复杂度为 $O(\log n)$ 。

Treap::node *Treap::find(Treap::node *p, int val) {
    if (p == nullptr) return nullptr;
    if (p->val == val) return p;
    if (p->val > val) return find(p->left, val);
    return find(p->right, val);
}

int Treap::find(int p, int v) {
    if (!p) return 0;
    if (tr[p].v == v) return p;
    if (tr[p].v > v) return find(tr[p].l, v);
    return find(tr[p].r, v);
}

封装函数

插入

先将整个 Treap 按照给定的值分割成两个子树，再在这两个子树的中间插入新值即可。

void Treap::insert(int val) {
    auto o = splitByValue(root, val);
    o.first = merge(o.first, new Treap::node(val));
    root = merge(o.first, o.second);
}

void insert(int v) {
    auto o = splitByValue(root, v);
    int p = ++cnt;
    tr[p] = node(v);
    o.first = merge(o.first, p);
    root = merge(o.first, o.second);
}

删除

本删除操作在遇到多个相同的数时只会删除一个。具体操作与插入类似，不再过多叙述。

void Treap::erase(int val) {
    auto o = splitByValue(root, val);
    auto t = o;
    if (find(o.second, val) != nullptr) {
        t = split(o.second, 1);
        delete t.first;
    }
    root = merge(o.first, t.second);
}

void Treap::erase(int v) {
    auto o = splitByValue(root, v);
    auto t = o;
    if (find(o.second, v)) {
        t = split(o.second, 1);
    }
    root = merge(o.first, t.second);
}

排名

将整棵树按值分裂，左子树的大小再加 $1$ 即为该数的排名。

int Treap::getRank(int val) {
    auto x = splitByValue(root, val);
    int r = getNodeSize(x.first) + 1;
    root = merge(x.first, x.second);
    return r;
}

int Treap::getRank(int v) {
    auto x = splitByValue(root, v);
    int r = tr[x.first].s;
    root = merge(x.first, x.second);
    return ++r;
}

第 k 大元素

将整棵树分裂为由前 $k - 1$ 个元素和其余节点组成的两棵子树，则右子树的第一个元素即为所求。

int Treap::getKth(int k) {
    auto x = split(root, k - 1);
    auto y = split(x.second, 1);
    Treap::node *o = y.first;
    root = merge(x.first, merge(y.first, y.second));
    return o == nullptr ? 0 : o->val;
}

int Treap::getKth(int k) {
    auto x = split(root, k - 1);
    auto y = split(x.second, 1);
    int o = y.first;
    root = merge(x.first, merge(y.first, y.second));
    return tr[o].v;
}

代码

需要的外部函数：rand（定义于头文件 <cstdlib>）。

指针版和数组版的 Treap 类暴露出的接口是一样的。

// Definition
class Treap {
  private:
    struct node {
        node *left, *right;
        int size, val, key;

        node();
        node(int);
        ~node();

        void pushup();
    } * root;

    int getNodeSize(node *);
    node *find(node *, int);
    std::pair<node *, node *> split(node *, int);
    std::pair<node *, node *> splitByValue(node *, int);
    node *merge(node *, node *);

  public:
    Treap();
    ~Treap();

    void insert(int);
    void erase(int);
    int getRank(int);
    int getKth(int);
} tree;

// === Treap ===

// struct Treap::node

Treap::node::node()
    : left(nullptr), right(nullptr), size(0), val(0), key(rand()) {}

Treap::node::node(int _val)
    : left(nullptr), right(nullptr), size(1), val(_val), key(rand()) {}

Treap::node::~node() {
    delete left, right;
}

inline void Treap::node::pushup() {
    size = 1;
    if (left != nullptr) size += left->size;
    if (right != nullptr) size += right->size;
}

// class Treap

Treap::Treap()
    : root(nullptr) {}

Treap::~Treap() {
    delete root;
}

inline int Treap::getNodeSize(Treap::node *node) {
    return node == nullptr ? 0 : node->size;
}

std::pair<Treap::node *, Treap::node *> Treap::split(Treap::node *p, int k) {
    if (p == nullptr) return std::make_pair(nullptr, nullptr);
    std::pair<Treap::node *, Treap::node *> o;
    if (k <= getNodeSize(p->left)) {
        o = split(p->left, k);
        p->left = o.second;
        p->pushup();
        o.second = p;
    } else {
        o = split(p->right, k - getNodeSize(p->left) - 1);
        p->right = o.first;
        p->pushup();
        o.first = p;
    }
    return o;
}

std::pair<Treap::node *, Treap::node *> Treap::splitByValue(Treap::node *p, int val) {
    if (p == nullptr) return std::make_pair(nullptr, nullptr);
    std::pair<Treap::node *, Treap::node *> o;
    if (p->val < val) {
        o = splitByValue(p->right, val);
        p->right = o.first;
        p->pushup();
        o.first = p;
    } else {
        o = splitByValue(p->left, val);
        p->left = o.second;
        p->pushup();
        o.second = p;
    }
    return o;
}

Treap::node *Treap::merge(Treap::node *x, Treap::node *y) {
    if (x == nullptr) return y;
    if (y == nullptr) return x;
    if (x->key > y->key) {
        x->right = merge(x->right, y);
        x->pushup();
        return x;
    }
    y->left = merge(x, y->left);
    y->pushup();
    return y;
}

Treap::node *Treap::find(Treap::node *p, int val) {
    if (p == nullptr) return nullptr;
    if (p->val == val) return p;
    if (p->val > val) return find(p->left, val);
    return find(p->right, val);
}

void Treap::insert(int val) {
    auto o = splitByValue(root, val);
    o.first = merge(o.first, new Treap::node(val));
    root = merge(o.first, o.second);
}

void Treap::erase(int val) {
    auto o = splitByValue(root, val);
    auto t = o;
    if (find(o.second, val) != nullptr) {
        t = split(o.second, 1);
        delete t.first;
    }
    root = merge(o.first, t.second);
}

int Treap::getRank(int val) {
    auto x = splitByValue(root, val);
    int r = getNodeSize(x.first) + 1;
    root = merge(x.first, x.second);
    return r;
}

int Treap::getKth(int k) {
    auto x = split(root, k - 1);
    auto y = split(x.second, 1);
    Treap::node *o = y.first;
    root = merge(x.first, merge(y.first, y.second));
    return o == nullptr ? 0 : o->val;
}

// Definition
const int N = 100005;

class Treap {
  private:
    int root, cnt;

    struct node {
        int l, r, s, v, k;

        node();
        node(int);
    } tr[N];

    void pushup(int);
    std::pair<int, int> split(int, int);
    std::pair<int, int> splitByValue(int, int);
    int merge(int, int);
    int find(int, int);

  public:
    void insert(int);
    void erase(int);
    int getRank(int);
    int getKth(int);
} tree;

// === Treap ===

// struct Treap::node

Treap::node::node()
    : l(0), r(0), s(0), v(0), k(rand()) {}
Treap::node::node(int _v)
    : l(0), r(0), s(1), v(_v), k(rand()) {}

// class Treap

inline void Treap::pushup(int u) {
    tr[u].s = tr[tr[u].l].s + tr[tr[u].r].s + 1;
}

std::pair<int, int> Treap::split(int p, int k) {
    if (!p) return std::make_pair(0, 0);
    if (k <= tr[tr[p].l].s) {
        auto o = split(tr[p].l, k);
        tr[p].l = o.second;
        pushup(p);
        o.second = p;
        return o;
    }
    auto o = split(tr[p].r, k - tr[tr[p].l].s - 1);
    tr[p].r = o.first;
    pushup(p);
    o.first = p;
    return o;
}

std::pair<int, int> Treap::splitByValue(int p, int v) {
    if (!p) return std::make_pair(0, 0);
    if (tr[p].v < v) {
        auto o = splitByValue(tr[p].r, v);
        tr[p].r = o.first;
        pushup(p);
        o.first = p;
        return o;
    }
    auto o = splitByValue(tr[p].l, v);
    tr[p].l = o.second;
    pushup(p);
    o.second = p;
    return o;
}

int Treap::merge(int x, int y) {
    if (!x) return y;
    if (!y) return x;
    if (tr[x].k > tr[y].k) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    tr[y].l = merge(x, tr[y].l);
    pushup(y);
    return y;
}

int Treap::find(int p, int v) {
    if (!p) return 0;
    if (tr[p].v == v) return p;
    if (tr[p].v > v) return find(tr[p].l, v);
    return find(tr[p].r, v);
}

void Treap::insert(int v) {
    auto o = splitByValue(root, v);
    int p = ++cnt;
    tr[p] = Treap::node(v);
    o.first = merge(o.first, p);
    root = merge(o.first, o.second);
}

void Treap::erase(int v) {
    auto o = splitByValue(root, v);
    auto t = o;
    if (find(o.second, v)) {
        t = split(o.second, 1);
    }
    root = merge(o.first, t.second);
}

int Treap::getRank(int v) {
    auto x = splitByValue(root, v);
    int r = tr[x.first].s;
    root = merge(x.first, x.second);
    return ++r;
}

int Treap::getKth(int k) {
    auto x = split(root, k - 1);
    auto y = split(x.second, 1);
    int o = y.first;
    root = merge(x.first, merge(y.first, y.second));
    return tr[o].v;
}

技巧

求数 $x$ 的前驱

// Treap tree;
int prev = tree.getKth(tree.getRank(x) - 1);

求数 $x$ 的后继

// Treap tree;
int next = tree.getKth(tree.getRank(x + 1));

参考资料

谈谈各种数据结构^{（文件存档备份）}，范浩强，WC2012。
Treap，OI Wiki，2022 年 2 月 7 日。
某科学的无旋 Treap（FHQ-Treap），星夜，2021 年 1 月 25 日。