Изменения

Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.Покажем на примере, как двоичное дерево способно ускорить поиск в словаре.

Покажем, как двоичное дерево способно ускорить поиск в словаре. Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного упреждающего буфера. После ввода первых <math>16+5</math> символов скользящее окно выглядит так: