javascript - How to minimize visual width of (binary) search tree?

Question

Introduction

I'm building an HTML5 web application that creates a visual representation of a binary search tree from a given list of numbers.

Currently, I have an algorithm which calculates the visual spacing between nodes on each row based on the maximum depth of the tree (which is a base-0 value):

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

From here, the position of the node is determined using this offset and the x-position of its parent.

The algorithm works well, because it's always able to accommodate for the widest-possible tree of any depth. However, this also makes the tree unnecessarily wide at times.

Examples

Tree branching to the left (too wide):

Tree branching to the left http://f.cl.ly/items/0c0t0L0L0o411h092G2w/left.png

Tree branching to both sides (left and right sides could be closer together).

Tree branching to both sides http://f.cl.ly/items/0r3X1j0w3r1D3v1V1V3b/left-right.png

Ideally, the above tree should be shaped like a pyramid, with a smaller width and with the sides straight, as depicted below:

Ideal tree when branching to both sides

Balanced tree (case where the algorithm works best):

Balanced tree http://f.cl.ly/items/203m2j2i3P1F2r2T3X02/balanced.png

Implementation

Properties

I'm using Backbone.js to create nodes from a Node model. Each node has the following properties:

parent (the parent node)
left (the left child node)
right (the right child node)
x (the x-position of the node in pixels)
y (the y-position of the node in pixels)

The x and y properties above are calculated based on the direction the node branches from:

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

At this point, the x and y properties are the exact values used to position the nodes (each is positioned absolute within a container element).

Methods

getDepth() (returns the base-0 depth of a node)
getMaxDepth() (returns the depth of the last row in the tree)
getRow(n) (returns an array of all nodes at depth-n)

Question

Therefore, my question is simple:

What is the best algorithm to minimize the aesthetic width of my binary tree?

score 2 · Accepted Answer

如果您查看类似问题的答案，它可能会对您有所帮助；它们包含指向软件的链接，这些链接正是您想要的那种树状可视化。

美学是高度主观的，所以这只是我的看法。我认为我的指导方针（不是算法）如下。我假设孩子的顺序很重要（因为这些是二叉搜索树）。

只有x坐标是有趣的；y坐标只能由节点的级别确定。（如果违反了这一点，我会觉得很丑陋，但正如我所说，口味不同。但是，其余的都是基于这个假设。）
同一级别中的任何节点都不应比某个固定的最小距离更近（例如D）。
如果一个节点在x1和有两个子节点x2，我希望将其放置在(x1+x2)/2。在某些情况下，最好选择其他坐标[x1..x2]（可能是它的一端）。我想可能会有一些不寻常的情况，外部坐标[x1..x2]会更可取。
如果一个节点有一个孩子 atx1并且它的父节点是 at xp，我希望它被放置在(x1+xp)/2（这样它就位于连接它的父节点和它的子节点的线上）。在某些情况下，最好偏离这一点并在[xp..x1]内部（甚至外部）选择一些其他坐标。
让我们将级别的宽度称为最左侧和最右侧节点之间的距离。最宽层的宽度应该是最小的。

这些准则施加了无法同时满足的约束。因此，您应该优先考虑它们，这又是主观的。例如，更重要的是#4 还是#5？您对 5 节点树的草图暗示＃4 更重要；如果＃5 更重要，您将获得类似房屋的图片（垂直线）；如果两者都很重要，那么您当前的结果会很好。

解决此问题的一种方法是为准则分配权重，并在不遵守这些准则的情况下定义处罚。abs(x-(x1+x2)/2)例如，在准则 #3 中，如果父级放置在x其子级之间的中间位置，则可以进行惩罚；与其他指南相比，您还可以分配一个权重，告诉您这是多么重要。然后，您应该尝试最小化解决方案的总加权惩罚。一般来说，这会给你一个约束优化问题，并且有几种方法可以解决这些问题。

score -1 · Accepted Answer

您可以使用 AVL 树。这些插入时的自平衡在每次插入后为您提供平衡的树。

http://en.wikipedia.org/wiki/AVL_tree