二分木画像化レシピ

http://hayamin.com/upload/rb_node_small.png

作り方について質問が出たので、一応参考までに簡単に説明。

  1. 好きな言語で、二分探索木のプログラムを書く
  2. 二分探索木をトラバースしながら、PostScriptを出力する

以上。PostScriptについては、A First Guide to PostScript(英語)がわかりやすい。PostScriptで作った画像をpngとかgifに変換したい場合は、ImageMagickを使いました。

PostScript自体はとても簡単で、上の画像のソースはこんな感じ。

1.000000 setlinewidth
newpath 400.000000 580.000000 moveto 590.000000 568.085106 lineto stroke
newpath 400.000000 580.000000 moveto 210.000000 568.085106 lineto stroke
0.550000 setlinewidth
newpath 590.000000 568.085106 moveto 685.000000 556.170213 lineto stroke
newpath 590.000000 568.085106 moveto 495.000000 556.170213 lineto stroke
0.325000 setlinewidth
newpath 685.000000 556.170213 moveto 732.500000 544.255319 lineto stroke
newpath 685.000000 556.170213 moveto 637.500000 544.255319 lineto stroke
(以下同様に続く)

ちなみに、アニメーションを作るときは、上に書いたPostScriptを出力するプログラムに流しこむデータの量を変化させながら、何枚も画像を出力していった後に、全部gifに変換してgifアニメーションにまとめただけ。これもImageMagickでやった。

ちなみに、データ数が10000あって、100枚の画像でアニメーションさせるときに流しこむデータ量は、100, 200, 300, ... としていくと綺麗なアニメーションにはならないので注意。木の高さはデータ数の対数に比例してゆくので、流しこむデータ量は指数的に変化させたほうが同じ速度で木が成長しておもしろい。