二分探索木

とは、お金のなる木と同じようなものです(大いなるウソ)。

とまぁ、誰にもわからないウソをついたのですが。この記事では順列における二分探索木の同型問題について話そうと思います。また、文章だけで説明できるかチャレンジしてみようと思います(絶対ムリ)。二分探索木を知っている人は絵がある所から読んでください。

さて、二分探索木とは、データ構造というものらしいです。現実に植わっている訳ではありません。これはですね、二分木と呼ばれる各ノードが最大で2つの子を持つ木、かつ、すべてのノードが左の子<=親<右の子というルールを持つ木構造のことを指します。何言っているかわかりませんね。

想像してください、絵を一緒に書くと良いでしょう。あなたは数字の神様です。しかし、神様の癖に9,7,10,3,12,8の数字しか持っていません。悲しくなって、これを二分探索木という形で海の上にばら蒔きたくなります。ちなみにあなたは神の視点で海を上から見ています。

数字を海にばら蒔くと沈むので島を作りたくなります。一つ目に作った島を二分木用語ではルート(根)といいます。そして、その島に9を置きたくなり、置きます。

次に、作った島の斜め左右に二本の橋を建てたくなります。そして、あなたは7という数字を置きたくなります。しかし、二分探索木という形で置きたいので、必然的に左の橋の先に島を作って、置きます。なぜなら、7<9であり、左の子<=親<右の子というルールがあるからです。一つ目以外の島をノードといいます。また、ややこしいことに7の島ができたお陰で、9の島は7の島の親であり、7の島は9の島の子供という関係が発生します。親、子供というのも二分木用語です。この7の島にも二本の橋を架けたくなります。

次に10を置きたくなります。9<10なのでルールより、9の島の右橋先に島を作り10を置きます。二本の橋を作っておきます。今度は3を置きたくなります。3は3<9なので9の島から左橋先の島に置こうとしますが、7がいるので置けません。困ったときはルールを思い出します。左の子<=親<右の子です。3<7なので7の島の左橋先に島を作り、置きます。3と7には親子関係が発生します。

次に12を置きたくなります。12は9<12,10<12なので10の島の右橋先の島に置きます。これを繰り返して残り8を置くと

こんなのが出来上がるはずです。たぶん…。キーワードは、二分探索木はデータ構造ということです。あとはググってどうぞ…。

`本題`

本題はですね、二分探索木の同型問題なのですが。状況設定はですね、1からn番目までの数字列の順列を作りたくなります。このできた数字列1つ1つを二分探索木に収めたくなります。このとき、同じ木の形ができることがあるんですね。それを判断したいのですよ。

例えば、1から3の順列を考えます。123, 132, 213, 231, 312, 321の6通りの数字列ができるわけです。この各数字列を先頭から順に木に収めると、下の絵みたいに同じ木の形になるものがあるのですよ。入力の順番は異なっても。

で、絵を描けば一発でわかるのですが二分探索木を作るプログラム上ではわからんのですよ。ここで記事を書いてる人は考えました。順列においては！順列お・い・ては！ここ重要なので二回言いました。同じ木の形＝各ノードの場所に同じ数字がある、この考えを用いると同じ木かどうか判断できるのです。

方針は、二分探索木を回るときに同じ道筋を辿るのですよ。数字は同じ場所にあるのだから、同じ木であれば同じ数字が回った先にはあるわけですね。で、二分探索木の巡回方法には前順、中順、後順があります。中順にまわり各ノードの数字を出力すると、数字の場合は昇順にソートされたものが出てきます。これではすべて123…となって意味がないので、前順または後順でまわり各ノードのを出力すると同じ木は同じ数字列になります。

というのはすぐに思いつきました。では、順列からできた木の異なる形の木だけ取り出して線形リストにしようと思いたちます…C言語で実装したのですが苦労しました。下記の絵のイメージをしていただければいいと思います。idとかは気にしないでください。よかったら実装してみてください。1からnまでの数字列の順列を二分探索木にして、異なる木だけを線形リストにするという実装を。プログラミングの練習になると思います。なんたって、かだi…ゲフンゲフンだもの。二分探索木の挿入や巡回、探索などは再帰呼出しを使うと短いコードで書けるのですが実装するにあたってわざわざ再帰呼出しなしで挿入したり巡回しましたね…