この木なんの木

理系関連のトピックに関して、Wikipediaには初学者向けに優れた記述が多いように感じているけど、その中でも特にコンピュータサイエンスに関しては英語、日本語ともにコンパクトで読みやすい解説が多いように思う。

Wikipediaで木構造について色々と読み漁って、だいたいどんなツリーがあって、それぞれどういう特徴があるのかということが分かった。ツリーの本質は高さをlog nに抑えるためにバランスさせることで、そのための基本操作に「木の回転」があると知った。順序を変えずに文字通りグルリと左右に回す。操作は局所的だけど、うまくやると左右のバランスの悪いツリーの高さを調整できる。パズルっぽい。

n要素の2つのツリーがあって、これを回転操作で一致させる場合、それに要する操作数を回転距離といい、「nノードの木の集合」というのは一種の距離空間となっているという。おもしろい。しかも、「回転距離を求める多項式時間のアルゴリズムが存在するかどうかは分かっていない」のだけど、「任意の2つのnノードの木（n ≥ 11 の場合）の回転距離が最大で 2n − 6であり、この距離の木の組合せが無数に存在する」ことも分かっているという。なんてこった。

AVL木、赤黒木、スプレー木、トライ木あたりをつらつらと実装してみるといいのかしら。買ったときに眺めて以来、開いてもいなかったコルメンのアルゴリズム教科書を再び開いてみると、読めるような気がしてきた。

そういえば、ビッグオー記法の厳密な定義もWikipediaで初めてみた。Ω記法やΘ記法が何に使われるのか、よく分からない。