Как минимизировать визуальную ширину (двоичного) дерева поиска?

Введение

Я создаю веб-приложение HTML5, которое создает визуальное представление двоичного дерева поиска из заданного списка чисел.

В настоящее время у меня есть алгоритм, который вычисляет визуальное расстояние между узлами в каждой строке на основе максимальной глубины дерева (которое является значением base-0):

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

Отсюда позиция node определяется с использованием этого смещения и 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

Реализация

Свойства

Я использую Backbone.js для создания узлов из модели node. Каждый node имеет следующие свойства:

родительский (родительский node)
left (левый дочерний элемент node)
справа (правый ребенок node)
x (x-позиция node в пикселях)
y (y-позиция node в пикселях)

Вышеуказанные свойства x и y вычисляются в зависимости от направления ветвления node:

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 в node)
getMaxDepth() (возвращает глубину последней строки в дереве)
getRow (n) (возвращает массив всех узлов на глубине-n)

Вопрос

Поэтому мой вопрос прост:

Каков наилучший алгоритм для минимизации эстетической ширины моего двоичного дерева?

Ответ 1

Это могло бы помочь вам, если бы вы посмотрели ответы на аналогичный вопрос; они содержат ссылки на программное обеспечение, выполняющее именно ту визуализацию дерева, которую вы хотите.

Эстетика очень субъективна, так что это только мое мнение. Я думаю, что мои рекомендации (а не алгоритм) будут следующими. Я предполагаю, что порядок детей важен (так как это деревья двоичного поиска).

Интересны только координаты x; Координаты y должны определяться только уровнем node. (Я бы счел это довольно уродливым, если бы это было нарушено, но, как я уже сказал, вкусы отличаются. Однако все остальное основывается на этом предположении.)
Ни один узел на одном уровне не должен быть ближе некоторого фиксированного минимального расстояния (скажем D).
Если node имеет двух детей в x1 и x2, я бы предпочел, чтобы он был помещен в (x1+x2)/2. В некоторых случаях было бы предпочтительнее выбрать некоторую другую координату в [x1..x2] (возможно, один из ее концов). Я предполагаю, что могут быть необычные случаи, когда предпочтительна координата вне [x1..x2].
Если node имеет один дочерний элемент в x1, а его родительский элемент находится в xp, я бы предпочел, чтобы он был помещен в (x1+xp)/2 (так, чтобы он лежал на линии, соединяющей ее родительскую с его ребенок). В некоторых случаях было бы предпочтительнее отклоняться от этого и выбирать некоторую другую координату в [xp..x1] (или даже вне).
Позвольте ширине звонка установить расстояние между левым и правым node. Ширина самого широкого уровня должна быть минимальной.

Эти руководящие принципы налагают ограничения, которые не могут быть выполнены в одно и то же время. Поэтому вы должны расставить приоритеты, и это снова субъективно. Например, что более важно, №4 или №5? Ваш эскиз для дерева < node подразумевает, что # 4 является более важным; если # 5 было более важно, вы бы получили изображение, похожее на дом (вертикальные линии); если оба важны, то ваш текущий результат будет в порядке.

Один из способов борьбы с этим - назначить веса руководящим принципам и определить штрафы, если они не соблюдены. Например, в руководстве №3 вы можете и наказать abs(x-(x1+x2)/2), если родитель находится в x, который не находится на полпути между его дочерними элементами; вы также можете назначить вес, который расскажет вам, насколько это важно, по сравнению с другими рекомендациями. Затем вы должны попытаться свести к минимуму общее взвешенное наказание решения. В общем, это даст вам проблему оптимизации ограничений, и есть несколько способов решения таких проблем.