Упорядоченный обход префиксного дерева

#алгоритм #структуры #дерево #структуры_данных

Существует префиксное дерево (нагруженное дерево, trie).


Дерево хранит в себе пару ключ/значение.
Необходимо реализовать упорядоченный обход дерева по значению, т.е. необходимо идти
от ветвей с наибольшим значением к ветвям с наименьшим.
Поскольку первая и вторая пары результирующего набора могут быть в противоположных
ветвях, то возникают сложности.

Обновление

Дерево никак не отсортировано. У каждого узла может быть бесконечно потомков. Думаю
хранить в каждом узле максимальное значение на этой ветви. И пытаться делать прицельный
обход.
    

Ответы

Ответ 1

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

При этом построение кучи O(2n*log n), добавление элемента O(log n)