数据结构

Treap

一种比较平衡的二叉搜索树

Posted by Monad on September 21, 2017

概述

Treap是什么？Treap = Tree + Heap !
我们知道，在BST中，插入有序数据会导致BST退化成一条链（有些极限数据就是这样）。那么我们要怎么办呢？
其实其他大神们在此之前已经注意到了这个问题，所以他们就研发了一种新的东西，就是在BST的基础上，给每一个节点额外地加上了一个fix值（中文为修正值），然后这棵树除了要满足BST的性质之外，还要符合堆的性质（堆的值是fix）（这里是最小堆）。所以就有了一个新的东西：Treap。
这样，Treap的形态就不仅仅由value控制，而且还由fix控制。我们只要保证fix足够随机，这棵树就不会轻易地退化成一条链，平均（理想）深度为$\log_n$。

左旋？右旋！

那么不是每次操作都是刚好能同时符合两个性质的。有时候我们改变了一些节点，使它满足BST的性质，但是却破坏了堆的性质，怎么办呢？
因为此时已经满足了BST性质，所以可以在不破坏BST性质的前提下，使它满足堆的性质。
所以Treap的发明者又弄出来了两个东西：左旋、右旋。就是用来修复堆的性质的。

右旋

举个栗子，像下面的图
Treap R 如果B.fix > A.fix，那么就不符合最小堆的性质，那么我们可以对B点进行左旋操作，就是把B改成A的右孩，B的左孩改成β。讲得太抽象了？没事，下面有动画！
Right Rotate 所以右旋的代码是这个样子滴：

void leftRotate(NODE *&p) {
    NODE *t = p->rght;
    p->rght = t->left;
    t->left = p;
    p = t;
    t = p->left;
}

左旋

举个栗子，还是下面的图
Treap L 如果A.fix > B.fix，那么就不符合最小堆的性质，那么我们可以对A点进行左旋操作，就是把A改成B的左孩，A的右孩改成β。讲得太抽象了？没事，下面还是有动画！
Left Rotate 所以左旋的代码是这个样子滴：

void rghtRotate(NODE *&p) {
    NODE *t = p->left;
    p->left = t->rght;
    t->rght = p;
    p = t;
    t = p->rght;
}

一句话，旋转就是一种不会破坏BST性质还会修复堆性质的旋转
算了，还是证明一下比较好，证明不会破坏BST性质：
首先，以左旋为例，旋转前，value[A]<value[β]<value[B]（α和γ没有变，所以可以不讨论）；旋转后，依然还是value[A]<value[β]<value[B]，所以不会破坏BST性质。

遍历 & 查找

因为这棵树也是一棵BST树，所以这些操作跟BST的完全相同！
遍历：

void print(const NODE *p) {
    if (p) {
        printf("(");
        print(p -> left);
        printf(" %d ", p -> value);
        print(p -> rght);
        printf(")");
    }
}

查找：

NODE* find(NODE *p, const int value) {
    if      (!p)                return NULL;
    else if (p->value == value) return p;
    else if (p->value >  value) return find(p->left, value);
    else                        return find(p->rght, value);
}

插入

插入的标准操作就是这样：

  1. 从根节点开始插入；
  2. 如果要插入的值小于等于当前节点的值，在当前节点的左子树中插入，插入后如果左子节点的修正值小于当前节点的修正值，对当前节点进行右旋；
  3. 如果要插入的值大于当前节点的值，在当前节点的右子树中插入，插入后如果右子节点的修正值小于当前节点的修正值，对当前节点进行左旋；
  4. 如果当前节点为空节点，在此建立新的节点，该节点的值为要插入的值，左右子树为空。

太烦了？一句话概括，就是在底端合适的位置先插入，然后再用左右旋把这个节点一步一步地旋转上去。
按照上面的操作，可得代码：

void insert(NODE *&p, const int value) {
    if (!p) {
        p = new NODE();
        p->fix   = rand();
        p->value = value;
    }
    else if (value < p->value) {
        insert(p->left, value);
        if (p->left->fix < p->fix)
            rghtRotate(p);
    }
    else {
        insert(p->rght, value);
        if (p->rght->fix < p->fix)
            leftRotate(p);
    }
}

删除

如果这个点至多有一个孩子（一个或没有），那么这个节点肯定是可以被立刻删除的。（可以用孩子代替该点的位置）
但是如果有两个孩子那怎么办呢？我们可以通过旋转使这个节点变成可以立刻删除的点。如果该节点的左孩的修正值小于右孩的修正值，右旋该节点，否则左旋该节点。直到只有一个孩子就可以删除了。
所以删除的代码如下：

void remove(NODE *&p, const int value) {
    if (!p) return;
    if (value == p->value) {
        if (!p->rght || !p->left) {
            NODE *t = p;
            if (!p->rght) p = p->left;
            else          p = p->rght;
            delete t;
        }
        else {
            if (p->left->fix < p->rght->fix) {
                rghtRotate(p);
                remove(p->rght, value);
            }
            else {
                leftRotate(p);
                remove(p->left, value);
            }
        }
    }
    else if (value < p->value) remove(p->left, value);
    else                       remove(p->rght, value);
}

时间复杂度

因为这是一棵BST树，而且在Treap算法的优化下能优化到平均深度为$\log_n$，所以查找、插入、删除的时间复杂度是$O(\log_n)$。

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：Treap”
CATALOG
    FRIENDS