Префиксное дерево

[pu4koff]

Сообщение от flance

Привет коллегам.

Можете мне объяснить в чем суть префиксных деревьев?

Я понял про ключи.
Понял, что это ассоциативный массив, в котором ключи в дереве. И что каждый ключ добавляет символ. И при обращении к нему мы указываем всю строку до него и включая его.
Ну вот как здесь
http://upload.wikimedia.org/wikipedi...xample.svg.png

Только я не понимаю - какой в этом смысл?
Какие преимущества дает это. В сравнении с простым массивом.

Осознать не могу полезность)

А никакого смысла нет, равно как и в разных алгоритмах сортировки. Всё это для дураков, а реальные пацаны используют массив и сортировку пузырьком. Зачем нам списки, стеки, деревья,... когда есть массивы.

[flance]

спасибо за книгу, почитаю

pu4koff
Ну почему. Я использую не только массивы, но и стеки, и очереди. У них есть очевидные преимущества в определенных случаях.


Вот в том-то и дело, что я не пойму преимуществ этого префиксного дерева.

[flance]

Ну так-то я догадываюсь, что например это может быть для того, что в этом дереве есть три слова chance charge change
до тех пор пока вводишь каждую из первых трех букв он советует все три слова, если потом введешь n , то он уже советует chance и change.

Это по-моему полезно.
Типа подсказчика в поисковике.

[flance]

я в общем попробовал написать свой класс.
вот что получилось.
там ошибка. я обратился в спец. раздел.

http://www.programmersforum.ru/showt...47#post1216947

[pu4koff]

Сообщение от flance

Вот в том-то и дело, что я не пойму преимуществ этого префиксного дерева.

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

[Son Of Pain]

1) Экономия памяти (не нужно хранить повторяющиеся куски ключей по многу раз).
2) Скорость поиска зависит от длины ключа, а не только от высоты дерева. В некоторых ситуациях это будет эффективнее использования обычных деревьев поиска.
3) При добавлении/удалении элементов не нужно перебалансировать его, как в случае с красно-черными деревьями, например.
4) Можно просто и эффективно найти все элементы, начинающиеся с какого-то префикса (удобно в спелчекерах/автодополнялках, например).