Consistent Binary Tree Layout(2)

先日のエントリにて、一貫した二分検索木の可視を行うアルゴリズムについて記載しました。また、木構造、特に二分木や二分検索木と親和性が高い、通りがけ順について説明しました。

以下は、通りがけ順にてkd木を走査する様子を可視したものです。

さて、木の走査法は接点を訪れる順序によって分類することが出来ます。主たる木の走査法には、通りがけ順の他にも行きがけ順、帰りがけ順と呼ばれる走査法があり、用途によって使い分けることが出来ます。

行きがけ順は先行順とも呼ばれ、英語ではpreorderと表記されます。接点の部分木を訪れる前に接点自身を訪れます。以下は、行きがけ順にて木を走査する様子を可視したものです。

また、帰りがけ順は後行順とも呼ばれ、英語ではpostorderと表記されます。接点の部分木を訪れた後に接点自身を訪れます。以下は帰りがけ順にて木を走査する様子を可視したものです。

これらの可視にはそれぞれの走査法の特徴が表れていてなかなか面白いのですが、その特徴をずばり言い当てるほどまでには整理されていない印象も受けます。

さて、これまでは接点の配置に通りがけ順の順序と接点の深さを用いてきました。では、水平方向の配置に行きがけ順、帰りがけ順の順序を用いるとどのような可視となるのでしょうか。

以下は水平方向に関し、行きがけ順にて接点を配置し、行きがけ順による走査法が接点を訪れる様を可視したものです。

配置と走査法に同じ手法を用いているため、走査の方向は左から右に向かいます。また、通りがけ順を用いた配置を基調とした可視に比べると、木構造全体をせん断したようなものとなっています。

この可視によって、行きがけ順による走査が部分木を訪れるよりも先に接点を訪れる様がより明瞭となりました。また、接点の左側の部分木が右側の部分木よりも優先して走査されていることも分かります。さらに、左側の部分木は深さが浅いものが、右側の部分木はより深いものが優先されていることも分かります。

同様に、以下は水平方向に関し、帰りがけ順にて接点を配置し、帰りがけ順による走査法が接点を訪れる様を可視したものです。

この可視では、部分木の走査を接点よりも優先していることがより明瞭になっています。接点を訪れるのは左側、右側双方の部分木を訪れた後です。また、左側の部分木は右側の部分木よりもかなり優先されることが分かるかと思います。

これら行きがけ順、および帰りがけ順を接点の配置の基調とした木の可視を見る機会は少ないと思いますが、用途によってはなかなか説得力のある可視を提供します。本エントリの応用として、次回は解析木の可視に関して記載してみたいと思っています。

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

追記(2010/6/10)

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