Другие языки программирования и технологии

Бинарные деревья в алгоритме поиска слов

Читал статью, где предлагалось использовать для хранения слов бинарное дерево. Но, простите - как?
От каждого узла есть лишь две ветви, а сам узел, как я понял, представляет собой определённую букву слова, на определённой позиции. То есть, при добавлении в дерево какого-нибудь нового слова, которое пересекается с какими-либо двумя до символа N, а дальше предлагает совершенно другую букву, оно нарушит тип дерева. Разъясните, пожалуйста, как применять (если это вообще реально) бинарные деревья для задачи поиска, например, синонимов к слову?
Как я в данный момент представляю решение (для русского алфавита):
Создать дерево, где каждый узел имеет следующий вид:
-Номер буквы
-Массив из 33 элементов такого же типа
-Флаг завершения слова. Используется в том случае, если данный узел определённой глубины является конечной буквой в некотором слове, может представлять из себя, например, группу байт, определяющих порядковый номер блока данных уже в самой базе синонимов.

Как перестроить то же на бинарное дерево?
СГ
Сергей Гурнович
49
Делать это именно бинарным деревом действительно абсурдно. Хотя и вполне возможно. Но проще использовать, например, http://habrahabr.ru/post/111874/ - достаточно близко к тому, что ты придумал.
Аскар Капаров
Аскар Капаров
56 479
Лучший ответ
Вы определитесь, что вам конкретно надо. Вы сейчас описали отнюдь не бинарное дерево, а так называемое префиксное дерево, где вы сохраняете в структуру множество слов. Эффективность префиксного дерева в том, что она соединяет одинаковые префиксы слов. И нет, буква это не узел, а связь в этом случае. Бинарное же дерево совершенно другая структура, где у каждого узла максимум две связи: больше и меньше.
https://ru.wikipedia.org/wiki/Префиксное_дерево
https://ru.wikipedia.org/wiki/Двоичное_дерево
АС
Алексей Солдатенко
86 823
Не, всё совсем не так. Слово - неделимый объект, нельзя его делить на буквы. Между объектами определены отношения сравнения (больше, меньше, равно). Задача поиска синонимов не из этой области.
Сергей Величко
Сергей Величко
27 070
Строки-ключи сравниваются в двоичном дереве поиска в лексикографическом порядке, вот как раз в этом и есть суть, если меньше то левое поддерево, если больше правое поддерево, если нуль значит найден искомый ключ-строка. Но для строк есть различные деревья, такие как префиксное дерево, суфиксное дерево...
p.s. трудно изобрести свой эффективный "велосипед" без знаний хотя бы уже придуманных.
Denis Kozhaev
Denis Kozhaev
11 372
Дали бы ссылку на статью, было бы полегче понять, что вы хотите. Вы о Radix tree?

Просто бинарное дерево жутко неэффективное для поиска по началу слова. Применяются похожие на словари структуры:
-- на верхнем уровне массив букв, к каждой из которых привязана ссылка на второй уровень. Это уровень типа букв в телефонной книге.
-- на втором уровне тоже массив, но трехбуквенных сочетаний - это как в углу страницы словаря пишут КОН-КОР - слова начинающиеся на КОН и КОР, этот уровень ссылается либо на массив из ссылок на записи с полным словом, либо на следующий уровень, если слов, допустим на КОН- очень много.
-- на третьем уровне могут быть 4-буквенные сочетания типа КОНА-КОНГ, которые под собой уже имеют массив реальных указателей нс слова с таким началами.

Вам предлагают разбивать слова на части и хранить на разных уровнях (то есть вместо КОНА-КОНГ хранить А-Г, так как КОН уже выше уровнем), это по-идее экономит место, но не сильно, так как ссылки обычно занимают значительно больше места, чем несколько символов. Это просто не выгодно, а бинарное дерево даёт даже большие накладные расходы.

Такие структуры обычно хранятся с основными данными и периодически перестраиваются с нуля, начиная либо с какой-то ветви. Либо аналогично алгоритмам Б-дерева
Khil Evgeniy
Khil Evgeniy
11 112

Похожие вопросы