Treap算法

Published: by Creative Commons Licence

  • Tags:

前言

Treap是一个神奇的数据结构,简单的说它是一个二分平衡树,而且是实现最简单的二分平衡树。

二叉平衡树的主要价值是用于实时插入和查询以及有序遍历。

如果仅考虑维护一个数据结构支持查询和有序遍历而没有额外的插入操作,那么我们可以直接预先排序数组之后通过二分查询法进行查询即可,在保证时间复杂度的同时常数更小,实现还简单。

如果仅考虑维护一个数据结构支持查询和插入,那么我们可以实现一个哈希表,作为CPU缓存的默认实现机制,哈希表的期望时间复杂度低达O(1),完爆所有二叉平衡树。

二叉平衡树是基于比较实现的,其所有查找操作都需要log2(n)的时间复杂度。实际上还能证明这还是所有二叉平衡树查询操作时间复杂度的下界,因为每次比较都势必将剩余的元素二分为两部分,而在最坏情况下被查找的元素会落在较大的那部分中,因此我们为了保证最坏时间复杂度,必须将元素均匀二分,这也实际上就非常类似于二分查找法。

乱序二叉树

考虑我们在维护一个有序二叉树(中序遍历为有序遍历),并且不考虑平衡的要求,这种情况下即使一个有序链表也可以认为是一个有序二叉树,只是查询的时间复杂度上界为O(n)。下面给出插入操作的简单算法:

//将node插入以root为根的树中
insert(root, node){
    if(root == NIL){
        return root;
    }
    if(root.val >= node.val){
        root.left = insert(root.left, node);
    }else{
        root.right = insert(root.right, node);
    }
}

如果使用上面的代码,面对恶意的输入(比如说关键字递增的插入),我们的二叉树会退化为一条有序列表。

假设所有将被插入的元素一开始就可以得知,我们就可以进行离线处理。 离线处理的方式非常简单,就是对所有插入元素进行随机排列。

//打乱数据序列[data[l], data[l + 1], ... , data[r - 1]]
shuffle(data, l, r){
    for(i = l; i < r; i++){
        //randomInt(a, b)随机等概率返回[a, b)中的整数
        swap(data, l, randomInt(i, r));
    }
}

如果randomInt返回的数值是等概率的,我们可以保证执行上面洗牌算法后对于data子序列的所有排列都是等概率的。这里不加以证明。

下面我们证明将打乱后的数据逐一调用上面的插入算法构建我们的二叉树,二叉树中每个结点的期望高度均为O(log2n)

先给出以下定义:假设我们希望将data数组中每个元素都插入到二叉树中,打乱后的数组为suffleData,而排序后的数组为sortedData

首先我们考虑插入的流程,我们可以得到下面的几个命题:

命题1:考虑sortedData[a..b]中第一个插入的元素sortedData[i],所有其余的sortedData[a..b]中元素在插入后均为其子结点。

证明:

在插入sortedData[i]时,如果树的最大高度为0,那么sortedData[i]将作为树根,后面插入的其余元素一定是它的后代结点。

假设当树的最大高度不超过h时,命题均成立。

那么sortedData[i]插入后,其高度至多为h+1。而其余sortedData[a..b]元素插入时,会先于根进行比较,并且比较结果一定与sortedData[i]与根比价的结果形同(即与sortedData[i]落入相同的子树中)。由于这整个是一个递归的过程,因此我们可以认为之后的插入过程就是将元素插入到以高度为2的结点作为根的子树中,此时sortedData[i]在子树中的高度为h,故其余元素一定会作为它的后代结点插入。

根据归纳法,命题得证。

命题2: 插入过程中,sortedData[a]与sortedData[b]发生比较当且仅当sortedData[a..b]中第一个插入二叉树的元素是sortedData[a]或sortedData[b]

证明:

命题1实际上就给出了充分性的证明,现在证明必要性。

当sortedData[i]为sortedData[a..b]中第一个插入的元素,且i不等于a和b。那么sortedData[a]与sortedData[b]在插入的过程中会分别进入sorted[i]的左右子树,将不会发生比较。

因此后续条件也是必要的。到此充要性得证。

命题3:一个元素插入后,其所处高度等于其插入时发生的比较次数。

证明:

命题与插入算法有关,我们可以看到每发生一次比较,trace结点的高度都会增加1。当比较结束,将用新结点替换trace。

命题4:树中所有结点高度之和,等价于插入过程中发生的比较总次数。

证明:

插入过程每发生一次比较,就会使得新结点的插入高度增加1.

命题4:全部元素插入后,所有结点的高度之和的期望值为nlog2n

证明:

这里类似于快速排序的机制。结点的高度之和等价于插入过程中发生的比较总次数,因此我们仅需要计算比较的总次数的期望。同时我们定义X(i,j),若i与j发生比较,则X(i,j)=1,否则X(i,j)=0。因此比较的总次数为:S=X(1,2)+X(1,3)+…+X(1,n)+…+X(2,3)+X(2,4)+…+X(n-1,n)。而我们知道X(i,j)=1的概率为P(i,j)=2/(j-i+1)。因此可以计算期望得到:

C=P(1,2)+P(1,3)+…+P(1,n)+P(2,3)+P(2,4)+…+P(n-1,n)=1/(n-2)+2/(n-3)+…+(n-2)/1<=n*(1/1+1/2+…+1/n)=nlnn=O(nlog2n)。

命题5:每个元素的高度的期望值为log2n

证明:

由于一个结点的高度与其插入时发生的比较次数相同,而sortedData[i]在插入时与sortedData[j]发生比较当且仅当sortedData[j]是sortedData[i..j]中第一个插入的结点,其概率p(j)=1/|i-j+1|。

同上面证明,sortedData[i]发生比较次数的期望为 C=P(1)+P(2)+…+P(i-1)+P(i+1)+…+P(n)<=2*(1/1+1/2+1/3+…+1/n)=O(lnn)=O(log2n)

Treap

尽管用乱序插入的方法可以给出不俗的查询性能,并满足了有序遍历的性质。但是就如我们之前所说,这仅能适用于离线处理的情况。而离线情况下我们有一个更优的选择,就是将数组进行排序后之后每次查询都对应一次二分查找。

为了让乱序插入变得更加实用,我们需要让他支持实时插入。下面我们来讲述Treap的实现和原理:

我们每次要插入一个新元素时,我们同时为其赋予一个随机的权值weight(互不相同),换言之,现在一个结点拥有key和weight两个属性。

Treap名称是由Tree和Heap组合而来,就如名字所暗示,Treap结构拥有两个特殊的性质:

  1. Treap中每个结点的左子树中所有结点的key均小于自己的key(树的性质),右子树中所有结点的key均大于自己的key。
  2. Treap中每个结点的父结点

Treap的结构要求每个结点的左子树中所有结点的key均小于自己的key(树的性质),而且还要求每个结点的weight小于其孩子的weight(最小堆的性质)。

接下来给出一些Treap的性质:

命题1:任意一组结点(已知key和weight)均可以组成一株满足Treap定义的二叉树。

证明:

按weight进行从小到大排序后,按照二叉树的规则逐一进行插入即可得到。

命题2:任意一组结点(已知key和weight)所对应的满足Treap定义的二叉树都是唯一的。

证明:首先根节点一定weight最小的元素,因此根结点时确定的。之后根结点的左子树的根,一定时key小于根结点key的结点中权值最小的。同理可以得到所有结点的位置都是唯一确定的。

命题3:合法Treap树拥有乱序二叉树的所有性质

证明:很明显,由于weight随机分配,因此等价于乱序二叉树的随机重排过程。因此组成的满足Treap性质的二叉树一定也拥有乱序二叉树的性质。

但是说了这么多,如何保证Treap的实时增删改查呢?下面我们讲述Treap的神奇的实现方式。(这里实际说的是无旋Treap,带旋Treap不在考虑范围内)

Treap仅支持两个基本操作,split和merge。其余所有操作都是由常数次这两个操作所实现的,因此仅需要考虑它们的时间复杂度即可。

先看看split操作:

//将以node为根的子树切分为两部分,返回值[0]位存储key小于等于x的部分,其余存储在[1]位
split(node, x){
    if(node == NIL){
        return [NIL, NIL];
    }
    if(node.key > x){
        part = split(node.left, x);
        node.left = part[1];
        part[1] = node;
    } else {
        part = split(node.right, x);
        node.right = part[0];
        part[0] = node;
    }
    return part;
}

再看merge操作:

//将Treap树a和b合并,要求a中最大key小于b中的最小key
merge(a, b){
    if(a == NIL){
        return b;
    }
    if(b == NIL){
        return a;
    }
    if(randomBoolean()){
        a.right = merge(a.right, b);
        return a;
    } else {
        b.left = merge(a, b.left);
        return b;
    }
}

你们一定很奇怪,为什么最核心的两个操作都没有使用之前提到的weight属性呢。事实上在使用Treap的时候,我们并不会位这个属性额外分配一段空间,而是在真正需要使用weight来决定谁位于上方谁位于下方的时候才会利用randomBoolean来做决定。(因为我们设计weight的核心目的是希望任意两者的weight比较结果等概率为小于和大于)。

下面我们来分析一下时间复杂度,split的递归结束于遇到叶结点,而该叶结点的深度的期望为O(log2n),因此其期望时间复杂度应该为O(log2n)。merge会合并得到一株treap树,而合并完成时正好会访问到某个特殊结点,该结点的深度的期望为O(log2n),因此时间复杂度的期望应该为O(log2n)。

Treap拓展

利用切分和合并可以实现很多很有趣的性质。

名次

我们可以为每个结点增加属性size,表示以该结点为根的子树中所含的结点数目。

而一个结点node在以其为根的子树中的名次为node.left.size+1。

名次本身又为Treap拓展了更多的玩法,包括实现一个动态数组,其支持连接,拆分,按下表取值赋值等。

插入

insert(root, node){
    part = split(root, node.key);
    part[0] = merge(part[0], node);
    return merge(part[0], part[1]);
}

删除

delete(root, node){
    part1 = split(root, node.key);
    part2 = split(part1[1], node.key - 1);
    part1[0] = part2[0];
    return merge(part1[0], part1[1]);
}

查询

query(root, node){
    part1 = split(root, node.key);
    part2 = split(part1[1], node.key - 1);
    return part2[1];
}

持久化

之所以学习非旋Treap而非选择Treap的最大原因我想就是持久化的支持。由于非旋,因此我们不必为每个结点保存一个father值,这样子树就可以同时被多个父亲所复用,故可以实现我们所希望的持久化。

要实现持久化只需要在原来的代码上稍加修改,在修改结点成员之前先对该结点进行克隆,并将修改作用在克隆结点上而非原始结点,最后返回克隆结点即可。

区间操作

区间操作是基于我们可以切分Treap为多个区间并得到它们的根所得到的。