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

Введение

Я создаю веб-приложение 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

В идеале, вышеупомянутое дерево должно быть сформировано как пирамида с меньшей шириной и с прямыми сторонами, как показано ниже:

Ideal tree when branching to both sides

Сбалансированное дерево (в случае, когда алгоритм работает лучше всего):

Сбалансированное дерево 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, который не находится на полпути между его дочерними элементами; вы также можете назначить вес, который расскажет вам, насколько это важно, по сравнению с другими рекомендациями. Затем вы должны попытаться свести к минимуму общее взвешенное наказание решения. В общем, это даст вам проблему оптимизации ограничений, и есть несколько способов решения таких проблем.

Ответ 2

Вы можете использовать дерево AVL. Эти самобалансировки при вставке дают вам сбалансированное дерево после каждой вставки.

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