FHQ Treap

\(\text{FHQ Treap}\)是一种好写好用的平衡树。

它的平衡策略和普通\(\text{Treap}\)相似,采用在维护\(\text{BST}\)性质的同时维护随机的堆的形态来维持平衡;
但是维护结构的方式和\(\text{Treap}\)不同,不采用旋转,而是采用拆和合并的方法来维持树和堆的特性。

同时,由于\(\text{FHQ Treap}\)的操作所涉及的节点和基于旋转的其他平衡树相比少(仅\(\log n\)个),它支持可持久化


在实现\(\text{FHQ Treap}\)的时候,一般将多个相同的数作为多个节点保存,这样便于各种针对单个节点的操作。左子树即存放了所有权值\(\leq\)当前节点的点。

Merge

将两棵树合并成一颗树,使得新树含有原来两棵树的所有节点。要求两棵树中的一颗树的所有权值均小于另一棵树的权值

这是一个递归的过程:我们现在手上有两个子树\(x\)和\(y\),不妨设权值\(x.val<y.val\);
我们想让新的树满足小根堆的性质,进而我们要让堆权值\(key\)较小的那个节点在上方;

所以,我们直接把另一个节点和子节点合并成为新的子节点。结合递归的思想,我们就可以得到如下的代码:

node* merge(node* x, node* y) {
    if (!x || !y)                     // 如果两个节点之中有一个空节点:直接返回另一个节点
        return x ? x : y;             // (如果都是空节点就随便返回一个空节点)
    if (x->val > y->val)
        swap(x, y);
    if (x->key < y->key) {
        x->rson = merge(x->rson, y);
        update(x);
        return x;
    } else {
        y->lson = merge(y->lson, x);
        update(y);
        return y;
    }
}

Split

将一颗树以一个权值\(val\)为界拆成两颗树,使得拆出的两棵树中其中一颗\(l\)的所有节点权值\(\leq val\),另一颗\(r\)的权值\(>val\)。

我们在递归时传入拆出的两棵树当前的子树应该接在的位置(使用引用)。

void splitval(node* p, int val, node*& left, node*& right);

在函数中:

  • 如果当前节点为空则\(l\)和\(r\)都设为空。
  • 如果当前节点的权值\(p.val \leq val\),这个节点应当接到\(l\)上:
    我们直接把当前节点接到\(l\)上,然后递归把当前节点的右子,拆到\(l=\) 当前节点右子,\(r=r\)的两个地方。
if (p->val <= val) {
    left = p;
    splitval(p->rson, val, p->rson, right);
}
  • 如果当前节点的权值\(p.val \leq val\),这个节点应当接到\(r\)上:
    和上面一样,我们直接把当前节点接到\(r\)上,然后递归把当前节点的右子,拆到\(l=l\) ,\(r=\) 当前节点左子的两个地方。
else { /* p->val > val */
    right = p;
    splitval(p->lson, val, left, p->lson);
}

完整的代码如下:

void splitval(node* p, int val, node*& left, node*& right) {
    if (!p)
        left = right = 0;
    else {
        if (p->val < val) {
            left = p;
            splitval(p->rson, val, p->rson, right);
        } else { /* p->val > val */
            right = p;
            splitval(p->lson, val, left, p->lson);
        }
        update(p);
    }
}

剩下的写完了再补

发表评论

电子邮件地址不会被公开。 必填项已用*标注