Сравнивая узлы дерева

Question

Предположим, что у нас есть простое дерево узлов:

Node 1      0 
|-Node 1.1     1 
| |-Node 1.1.1    2 
|  |-Node 1.1.1.1   3 
|  |-Node 1.1.1.2   4 
|-Node 1.2     5 
    |-Node 1.2.1    6 

... etc. 

Мне нужно, чтобы иметь возможность сравнить любые 2 узла своей плоской позиции в дереве. Самый простой способ - пройти дерево и назначить каждому узлу индекс (как показано выше в крайнем правом столбце), а затем сравнить индексы. Однако есть 2 недостатка:

1. Для больших деревьев расчет индексов может занять много времени и нецелесообразно, если нам нужно сравнить только два узла дерева, содержащих миллионы узлов.
2. После изменения дерева (вставляемые/удаленные узлы) индексы необходимо пересчитать.

Следовательно, мой вопрос: есть ли лучший подход, который позволил бы мне сравнивать узлы дерева по их положению без необходимости вычислять индексы для каждого узла?

Answer 1

Одним из подходов может быть использование «материализованного пути» и сравнение этих путей (то есть путь может быть "1.1.1.2" и т. Д.). В зависимости от того, знаете ли вы, сколько узлов на уровне вы ожидаете, вы можете использовать части деталей фиксированного размера, например. "001.001.001.002", а затем простое сравнение строк должно сделать трюк.

Таким образом, при вставке/удалении узла вам необходимо обновить материализованные пути для нового узла и затронутого поддерева. При изменении порядка узлов вы делаете то же самое для всех узлов/поддеревьев, порядок которых был изменен.

Другой подход будет использовать «вложенные наборы», смотрите здесь для короткого урока на обоих: https://communities.bmc.com/docs/DOC-9902

В основном ваша проблема, кажется, связано с тем, как отобразить дерево в таблице БД, т.е. преобразуйте древовидную структуру в плоский список и обратно.