Treap の解析

手抜きです。

解析

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

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

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

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

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

dp[i]:=サイズ i の二分木の高さの期待値、とする。1..i を使って二分木を構築するとき、j が根になる確率は 1/i である。j を根としたとき、左部分木には [1,j)、右部分木には(j,i] が入る。左部分木、右部分木の高さは j の選択に依存せず、サイズのみで決まるため、両者の max をとって 1 足したものが求めたいものとなる。

\begin{equation}
dp[i] = \frac{1}{i} \sum_{j=0}^{i-1} \max(dp[j], dp[i-1-j])+1
\end{equation}

となる。

#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

実際に二分木に挿入して計測してみた。100回試した平均を出力する。
https://gist.github.com/pekempey/0c59ddb7665a44a7e28ff7d8964b345a

      1: 0.0000
     10: 4.6700
    100: 12.2300
   1000: 20.8800
  10000: 30.1600
 100000: 39.2900
 200000: 42.8500
 500000: 46.4100
1000000: 49.1200

大分差がある気がする。