pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Treap の解析

手抜きです。

解析

treap の高さの期待値が O(logn) になるのは、愚直な二分木にランダムな要素を挿入したときの高さの期待値が O(logn) になることに由来する。それはなぜか。

それは key と priority を与えると treap の形状が一意に確定するためである。なぜか。

heap 条件があるので treap の根は確定する。さらに二分木条件があるので、左(右)部分木に含まれる要素の種類も確定する。再帰的に部分木の根が確定するので、結果的に一意に定まる。

よって treap と、priority が 1 から n の順で挿入した普通の二分木の形状は同じになる。ランダムに挿入したとき高さが O(logn) になるから、treap の高さも O(logn) だと分かる。

さて、問題になるのはランダムに挿入した二分木が本当に平衡するのかということである。解析は難しくないが、式変形するだけで面白くもないので、DPで計算してみよう。

#include <bits/stdc++.h>

using namespace std;

const int N = 1000001;
double dp[N];
double s[N];

int main() {
	for (int i = 1; i < N; i++) {
		dp[i] = 1 + 2 * (s[i - 1] - s[(i + 1) / 2 - 1]) / i;
		if ((i - 1) % 2 == 0) {
			dp[i] += dp[(i - 1) / 2] / i;
		}
		s[i] = s[i - 1] + dp[i];
	}

	for (int x : {1, 10, 100, 1000, 10000, 100000, 200000, 500000, 1000000}) {
		printf("%7d: %.6f\n", x, dp[x]);
	}
}

愚直にやると O(n2) 掛かってしまうので、累積和を使って O(n) に落としている。一応愚直と比較はしてるので大丈夫だとは思う。

実行結果は以下のようになった。

      1: 1.000000
     10: 5.604233
    100: 12.618705
   1000: 20.070311
  10000: 27.568926
 100000: 35.072275
 200000: 37.331137
 500000: 40.317211
1000000: 42.576097

実際の treap も大体このくらいの高さになっている。十分に平衡している。