Я работал над реализацией радикального дерева (для строк / массивов символов), но у меня возникла некоторая дилемма, выясняющая, как хранить узлы дерева, являющиеся дочерними элементами определенного узла дерева.
Я видел реализации связного списка, используемые в Trie'ах (что-то похожее на радикальные деревья) и, возможно, в некоторых радикальных деревьях (с тех пор, как я в последний раз исследовал эту тему, прошло довольно много времени), но похоже, что он оченьплохо, особенно если у вас есть набор данных, который содержит много общих префиксов.
Теперь мне интересно, будет ли использование другой структуры данных (например, бинарного дерева поиска) лучшим выбором для проектирования?Я думаю, что могу увидеть очень существенное улучшение скорости по сравнению с простым связанным списком (O(log(n)) против O(n)), когда есть данные с большим количеством общих префиксов, но могут ли быть существенные компромиссы с производительностью в другом месте?
В частности, меня беспокоят случаи, когда не существует большого числа общих префиксов, или любые другие возможные препятствия, которые могут побудить вас выбрать связанный список из дерева двоичного поиска.
В качестве альтернативы, есть ли лучший (то есть более быстрый / использует меньше памяти) метод для хранения дочерних узлов?