Изменения

''Алфавитное дерево'' - дерево в котором при просмотре листьев слева направо символы идут в алфавитном порядке , и код последующего лексикографически больше предыдущего.

**Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов, выбирается пара с самой левой вершиной, из всех таких та , у которой правый узел расположен левее.

* '''Шаг 1.''' Изначально мы имеем только алфавит (и соответствующие веса) , отсортированный лексикографически.* '''Шаг 2.''' ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор , пока не останется одна вершина.

* '''Шаг 4.''' ''Перестройка''. После того, как номера уровней <tex>l_{1}, l_{2}, ..., l_{n}</tex> всех листьев определены, просматриваем последовательность слева направо и находим самый левый среди максимальных номер максимального уровня, скажем, <tex>l_{i}=q</tex>. Тогда и <tex>l_{i+1}=q</tex> (в последовательности <tex>l_{1}, l_{2}, ..., l_{n}</tex> максимальные номера уровней всегда располагаются рядом). Создаем вершину уровня <tex>q-1</tex> вместо вершин уровня <tex>q</tex>. Другими словами, последовательность уровней <tex>l_{1}, l_{2}, ..., l_{q}, l_{q}, ..., l_{n}</tex> заменяется на <tex>l_{1}, l_{2}, ..., l_{q}-1, ..., l_{n}</tex>. Повторяем этот процесс до тех пор пока не останется одна вершина с уровнем 0.

* '''Шаг 0.''' [[Стек ]] пуст.* '''Шаг 1.''' Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу 2, иначе к шагу 3.* '''Шаг 2.''' Поместить следующий элемент <tex>l_{i}</tex> на вершину стека. Перейти к шагу 1.* '''Шаг 3.''' Удалить 2 верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные, если . Если значение нового элемента равно нулю {{- остановится--}} остановиться, иначе перейти к шагу 1.

Выполним третий шаг , воспользовавшись стековым алгоритмом , и получим необходимое дерево.

Осталось только назначить код для каждого символа, это . Это делается аналогично [[Алгоритм Хаффмана|коду Хаффмана]], : левым ребрам назначается 0, а правым 1.

Разберем оценку. Для доказательства такой оценки времени введем понятие ''локально минимальной совместимой пары'' (л.м.с.п), пара <tex>(w_{l},w_{r})</tex> является л.м.с.п, когда выполнены следующие условия <tex>w_{r}<w_{i}</tex> для всех вершин <tex>i</tex> совместимых с <tex>l</tex> и <tex>w_{l} \le w_{j}</tex> для всех вершин <tex>j</tex> совместимых с <tex>r</tex>. Так же Также докажем следующую лемму.:

Пусть <tex>a</tex> — {{---}} любая вершина в последовательности, состоящей из вершин алфавита и вершин , образованных в результате комбинации, <tex>w_{i}</tex> — {{---}} вес наименьшей вершины <tex>i</tex>, совместимой с <tex>a</tex>. Если в результате комбинирования некоторой л.м.с.п. какая-нибудь новая вершина <tex>d</tex> становится совместимой c <tex>a</tex>, то <tex>w_{i}<w_{d}</tex> . В частности, л.м.с.п. в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.

Заметим, что <tex>w_{i}</tex> может находиться в любой стороне от <tex>a</tex>. Если вершина <tex>w_{i}</tex> лежит справа от <tex>a</tex>, то она не вершина алфавита. Пусть <tex>d</tex> — {{---}} вершина, которая становится совместимой с <tex>a</tex> после слияния <tex>(b, c)</tex> (она может быть как алфавитной так и слитой). Тогда <tex>d</tex> должна быть совместима с <tex>c</tex> в исходной последовательности и в силу локальной минимальности пары <tex>(b, c)</tex> имеем <tex>w_{b} \le w_{d}</tex>.

Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго, достаточно . Достаточно лишь находить л.м.с.п. , при этом не важно , в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <tex>n</tex> , из которого мы будем удалять л.м.с.п и создавать новую вершину, на . На нем легко будет осуществлять поиск л.м.с.п. А так же необходим массив размера <tex>2n</tex> хранящий дерево, для реализации следующего шага, хранящий дерево. Второй шаг легко осуществить проходом по дереву, имея сохраненное дерево, проходом по дереву. Третий шаг , реализованный стековым алгоритмом , работает за <tex>2n</tex> времени и необходимо требует <tex>4n</tex> памяти, <tex>n</tex> на стек, <tex>n</tex> на хранения уровней вершин и <tex>2n</tex> на хранение итогового дерева. Итак , общая оценка как раз получается <tex>O(n)</tex> памяти и <tex>O(n \log n)</tex> времени.