Что общего между лексической игрой "Отгадай слово" и двоичным деревом?

Садовая Ирина Владимировна

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

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

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

Очень четко видно, что экономится объем памяти за счет невыделения места под уже имеющиеся буквы. Данный способ записи данных используется в некоторых архиваторах - перед построением дерева подсчитывается, какие элементы чаще встречаются и именно с них начинается построение дерева.

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

буква "П" - совпадение - спуск вправо
буква "а" - совпадение - спуск вправо
буква "с" - совпадение - спуск вправо
буква "с" - совпадения нет - спуск влево от предыдущей вершины
буква "т" - совпадение - спуск вправо
буква "а" - совпадение - проверка на признак окончания слова - данное слово в дереве присутствует.