様々な平衡木
平衡木について
データを扱う上でもっとも基本となるのは配列(vector)かと思われますが、それ以外にも色々なデータ構造があって、色々な特徴があります。
連結リスト(list)や環状バッファ(deque)と並んで有名なデータ構造として、木構造が挙げられると思います。
木構造は一般的には集合(set)や写像(map)を実装するのに使われます。
初歩的な木構造として2分木が挙げられます。2分木の様々な操作（検索・挿入・削除）における処理時間は平均的にO(logN)になりますが、最悪の場合の処理時間はO(N)となってしまいます。
そこで、どんな場合においても処理時間をO(logN)にしてしまう木構造として、B木、B木の特殊形としての2-3木、2-3木を2分木の形で表した2色木が挙げられます。
これらの木は、木の深さをできるだけ一様に保とうとするため、平衡木として分類されます。
またこれら平衡木を多次元に拡張したR木などが挙げられます。
私の研究
多次元空間索引であるR木と、その次元縮小を行うための射影法について研究しています。
今後の予定
現在研究室では、次元縮小を用いたPacked R-tree（静的構築）を使っていますが、これだと実験の幅が狭まるので、次元縮小を使ったHilbert R-tree（動的構築）を書いてくれと頼まれています。
学習の甲斐があって、技術的には書けそうではあるのですが、いきなりR-treeのライブラリを書いても、使いづらいものしか作れないのではないかと不安です。
そこで、STLと互換性を持たせた上で2-3木と2色木を書いてみて（それを使ったmapとsetを書いてみる）、それから少しだけ使い方の違うB木を書いてみようかと思います。
それらができてから、R木のライブラリを設計してみる予定です。
とりあえず2-3木と2色木を12月末までに書いてみて、B木を1月末まで、R木を3月末までに書いてみる予定でプログラムを書いていってみようかと思います。
（STL風に書くと、結構色々と面倒なんですよね…だいぶ前ですけど、まともそうなbasic_string書くのに2週間も掛かったし…basic_string
