【アルゴリズム】SortedSet(平衡二分探索木)のインデックスアクセス

平衡二分探索木には様々なアルゴリズムが開発されている。私が実装に使っているのは赤黒木なのですが(というよりそれ以外は実装したことない)、たまにインデックスアクセスしたいことがあります。

二分木でインデックスアクセスしようとするとO(N)の計算量(※N=要素数)かかると勘違いしている人がたまにいるのですが、O(logN)でアクセスできます。

とりあえずソートListと平衡二分探索木の特徴をまとめてみます。

SortedList(ソートリスト)

検索 : O(logN)

挿入 : O(N)

インデックスアクセス : O(1)

SortedSet(平衡二分探索木)

検索 : O(logN)

挿入 : O(logN)

インデックスアクセス : O(logN)

メモリ量は平衡二分探索木のほうが重いですが、挿入の比重が重く、インデックスアクセスは普段しないので、平衡二分探索木を使っとけば間違いないです。

そして、二分探索木でインデックスアクセスする方法ですが、

実装は各ノードに、そのノードの子孫ノードにおいて自分より小さなノードの(つまり左下ノード)総数を記憶しておくだけでいいです。

アクセスする際はルートノードから和を累積していき、累積がアクセスしたいインデックスになるようなノードを見つけるだけです。

ノードを回転する時、挿入or削除の際に木を辿りながら、書き換えるだけなので計算量に影響はありません。

C#(VB)のSortedSetですが、インデックスアクセスもサポートされていませんし、

ソートされているという特徴上、次の(大きい)ノードをO(1)で探索できるのに、前や後ろを参照する関数もサポートされていない。

また、ある値(以上、以下、よりも大きい、未満)の値を取得する関数もありません。O(logN)

独自で作ると非常に使いやすく、よきプログラミングライフがおくれるのでお勧めです。