Consistent Binary Tree Layout(1)

名著アルゴリズム Cの特筆すべき点の一つとして、可視の美しさが挙げられます。特に二分木の可視は美しく、計算されつくされた様にいつも唸らされます。

以下は、アルゴリズム C 第2巻の14章、初等的な検索法の章に掲載されている二分木の可視です。この木は95個の接点から成り立っています。なかなかよく平衡した木で、極端に込み合っていたりもしていませんが、それを差し置いても大変美しく可視されていると言えるでしょう。


また以下は、同じ章に掲載されている二分検索木の可視です。キー群ASEARCHIを用いて構築した二分検索木にキー群NGEXAMPLEを挿入する過程を可視しています。新たなキーが挿入されるにつれ接点の数が増加しているにも関わらず、それぞれの段階における可視は一貫しており、美しいのです。


さて、木の配置を注意深く見てみましょう。以下は、kd-tree Visualization(1) - agwの日記で可視を試みたkd木を、アルゴリズムCにて用いられている方法にしたがって再度可視したものです。

垂直方向に関しては、木の深さに比例して接点を配置していけば良さそうですが、水平方向の配置には一見規則性がないように思えるかもしれません。これは、通りがけ順にて接点群を走査した順番を元に描画しています。

通りがけ順とは木の走査方法の一つを指し、その特性から中央順、対称順とも呼ばれています。英語ではinorder、symmetric orderと表記されます。二分木や二分検索木との親和性が高いため、それらの木を走査する代表的な方法として知られています。アルゴリズム Cでは第1巻の4章、その名も木の章で紹介されています。

さて、上の図では元々の可視に基づき、kd木に接点を挿入する順番を接点として描画していますが、通りがけ順にて木を走査した順番を描画してみることにしましょう。

確かに、水平方向にてより左にある接点はその右側の接点群に比べより値が小さくなっていることが分かります。

また以下は、通りがけ順による木の走査を可視したものです。上の図に比べ、各々の接点を訪れる様がより明白となります。

このアルゴリズムを用いて可視した木は、均衡が取れ、一貫性を持ったものとなるように感じています。以下は同じくkd-tree Visualization(1) - agwの日記で可視を試みた、極端に整列している座標群をkd木として構築したものです(是非画像をクリックして、オリジナルの大きさのものをご覧ください)。

以下、元の可視と比較すると、その美しさが際立ちます。また接点の情報が明瞭になったために、情報の質が大幅に向上していることが分かります。

前回可視を試みた際は、描画がろくに出来ない、だからバランスが悪い木であり効率も悪い、というように結論を導いていました。勿論、バランスが悪い木であることは変わりませんが、きちんと可視するとにより、バランスが悪くとも規則性を備えた、美しい木であったことが分かりました。ちょっと反省しています。


しかし、やはりアルゴリズム Cの可視は美しいですね。そしてその可視は計算されつくしているのみならず、またきっちり計算されたものであることを再発見し、驚きました。


次回のエントリでは、代表的な木の走査方法である行きがけ順、通りがけ順および帰りがけ順を可視し、比較検討を行いたいと思っています。

アルゴリズムC〈第1巻〉基礎・整列

アルゴリズムC〈第1巻〉基礎・整列

アルゴリズムC〈第2巻〉探索・文字列・計算幾何

アルゴリズムC〈第2巻〉探索・文字列・計算幾何

追記(2010/6/10)

Parse Tree Visualization - agwの日記として、二分木ではない木の配置アルゴリズムについて記載しました。