Библиотека Java или алгоритм вычисления координат узлов дерева/чертеж

Question

Я ищу библиотеку, которая даст мне точные координаты каждого узла в дереве (любое дерево, а не только двоичные деревья).

Допустим, я определяю дерево в следующих обозначениях

(() (() (()()())) 

А некоторые библиотеки дает мне координаты, как это:

[500 0]([200 50]() [600 50]([500 100]() [750 100]([600 150]() [700 150]() [800 150]())) 

или любые другие обозначения, которые однозначно представляет собой дерево.

Этот вид библиотеки позволил бы использовать экономичный рисунок деревьев, а также решить проблему перекрытия узлов и ссылок. Например, если дерево представляет собой список infact, я бы хотел, чтобы эта библиотека учитывала это и устраивала узлы в одном столбце или строке, чтобы сэкономить место.

Если ничего подобного не существует, алгоритм также будет полезен, при условии, что он может быть реализован относительно легко.

Answer 1

Я думаю, что модель Nested Set может вам помочь.

Алгоритм довольно прост и очень эффективен для чтения, хотя обновления дерева немного дороже, потому что границы узлов должны обновляться каскадным способом. Here is the algorithm implemented in SQL.