Эта версия LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982 [Storer 82].
Базовый алгоритм был улучшен по трем направлениям: (1) упреждающий буфер сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три. Двоичное дерево поиска - это двоичное дерево, в котором левое поддерево каждого узла А содержит узлы, меньшие чем Л, а узлы правого поддерева все больше А. Поскольку узлы нашего двоичного дерева состоят из строк (или слов), прежде всего необходимо определиться, как эти строки следует сравнивать, что значит, одна строка «больше» другой.

Это легко понять, представив себе строки в словаре, где они упорядочены по алфавиту. Ясно, что строка rote предшествует строке said, так как буква r стоит раньше буквы S (хотя о и следует после а). Мы будем считать, что строка rote меньше строки said. Такое упорядочение строк называется лексикографическим. А как быть со строкой «аbс»? Фактически все современные компьютеры используют код ASCII для представления символов (хотя все большее распространение получают коды Unicode, а некоторые старые большие компьютеры IBM, Amdahl, Fujitsu, Siemens работают со старыми 8-битными кодами EBCDIC, разработанными в IBM). В кодах ASCII символ пробела предшествует символам букв, поэтому строка, начинающаяся с пробела будет считаться меньше любой строки, в начале которой стоит буква. В общем случае сортировку последовательностей в компьютере определяет последовательность символов, упорядоченных от меньшего к большему.

Обратите внимание на различие между (почти) сбалансированным деревом (а) и косым деревом (b). Эти деревья состоят из одного числа 14 узлов, но они устроены и ведут себя совершенно по-разному. В сбалансированном дереве любой узел можно достичь не более, чем в 4 шага, а в косом дереве р,ля этого может потребоваться до 14 шагов. В любом случае максимальное число шагов потребуется для того, чтобы достичь узлы, удаленные от корня на полную высоту дерева. Для косого дерева (которое, на самом деле, эквивалентно присоединенному списку), высота дерева - это число его элементов n, а для сбалансированного дерева его высота равна flog2n , что существенно меньше. Более подробные сведения о двоичных деревьях поиска можно найти в любом учебнике по структурам данных.