11

序章

指定された数値のリストから二分探索木の視覚的表現を作成する HTML5 Web アプリケーションを構築しています。

現在、ツリーの最大深度 (ベース 0 値) に基づいて、各行のノード間の視覚的な間隔を計算するアルゴリズムがあります。

offset = 50
offset *= pow(2, maxDepth - currentDepth)

ここから、ノードの位置は、このオフセットとその親の x 位置を使用して決定されます。

このアルゴリズムは、あらゆる深さの可能な限り広いツリーに常に対応できるため、うまく機能します。ただし、これにより、ツリーが不必要に広くなる場合もあります。

例

左へのツリー分岐 (広すぎる):

左へのツリー分岐 http://f.cl.ly/items/0c0t0L0L0o411h092G2w/left.png

両側に分岐するツリー (左側と右側が接近している可能性があります)。

両側に分岐するツリー http://f.cl.ly/items/0r3X1j0w3r1D3v1V1V3b/left-right.png

理想的には、上のツリーは、以下に示すように、幅が狭く、側面がまっすぐなピラミッドのような形にする必要があります。

両側分岐時の理想樹

バランスの取れたツリー (アルゴリズムが最適に機能する場合):

バランスの木 http://f.cl.ly/items/203m2j2i3P1F2r2T3X02/balanced.png

実装

プロパティ

Node モデルからノードを作成するために Backbone.js を使用しています。各ノードには次のプロパティがあります。

  • 親(親ノード)
  • left (左の子ノード)
  • right (右の子ノード)
  • x (ピクセル単位のノードの x 位置)
  • y (ピクセル単位のノードの y 位置)

上記のxおよびyプロパティは、ノードの分岐元の方向に基づいて計算されます。

if (parent.get('left') === node) {
    x = parentX - offsetX;
    y = parentY + offsetY;
} else if (parent.get('right') === node) {
    x = parentX + offsetX;
    y = parentY + offsetY;
}

この時点で、xプロパティとyプロパティは、ノードの配置に使用される正確な値です (それぞれがコンテナー要素内で絶対的に配置されます)。

メソッド

  • getDepth() (ノードのベース 0 深度を返します)
  • getMaxDepth() (ツリーの最後の行の深さを返します)
  • getRow(n) (深さ n のすべてのノードの配列を返します)

質問

したがって、私の質問は簡単です：

二分木の美的幅を最小化するための最適なアルゴリズムは何ですか?

4

2 に答える 2

2

同様の質問に対する回答を参照してください。それらには、必要な種類のツリーの視覚化を正確に実行するソフトウェアへのリンクが含まれています。

美学は非常に主観的なものなので、これは私の意見です。私のガイドライン（アルゴリズムではありません）は次のようになると思います。子の順序が重要であると想定しています (これらは二分探索木であるため)。

  1. x座標だけが興味深いです。y座標は、ノードのレベルによってのみ決定されます。（これを破るとかなり醜いと思いますが、先ほども言いましたが、好みは人それぞれです。しかし、あとはこの仮定に基づいています。）

  2. 同じレベルのノードは、固定された最小距離 (たとえばD) よりも近くにある必要はありません。

  3. ノードにx1とに 2 つの子がある場合はx2、 に配置することをお勧めし(x1+x2)/2ます。場合によっては、別の座標を選択する方が望ましい場合があります[x1..x2](おそらくその端の 1 つ)。外のコーディネートの方がいいという珍しいケースもあると思い[x1..x2]ます。

  4. ノードに 1 つの子がx1あり、その親が にある場合、 (親と子を結ぶ線上にあるように)xpに配置することをお勧めします。(x1+xp)/2場合によっては、これから逸脱して、他の座標を内側[xp..x1](または外側) で選択することが望ましい場合があります。

  5. レベルの幅を、一番左のノードと一番右のノードの間の距離と呼びましょう。最も広いレベルの幅は最小限にする必要があります。

これらのガイドラインは、すべてを同時に満たすことができない制約を課します。したがって、優先順位を付ける必要がありますが、これもまた主観的なものです。たとえば、4 番目と 5 番目のどちらがより重要ですか? 5 ノード ツリーのスケッチは、#4 がより重要であることを暗示しています。#5 がより重要な場合は、家のような画像 (縦線) が表示されます。両方が重要である場合、現在の結果は問題ありません。

これに取り組む 1 つの方法は、ガイドラインに重みを割り当て、これらに従わない場合の罰則を定義することです。たとえば、ガイドライン 3 ではabs(x-(x1+x2)/2)、親がxその子の中間ではない場所に配置されている場合にペナルティを課すことができます。他のガイドラインと比較して、これがどれほど重要かを示す重みを割り当てることもできます。次に、解の加重ペナルティの合計を最小化するように努める必要があります。一般に、これにより制約の最適化の問題が発生し、そのような問題を解決するにはいくつかの方法があります。

于 2013-11-02T09:36:26.793 に答える