Изменения

=== Алгоритм Ху-Таккера ===* Начало.* '''Шаг 0. ''' ''Введем следующие понятия''. **Две вершины называются совместимой парой, если они соседние или если между ними нет вершин алфавита. **Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов, выбирается пара с самой левой вершиной, из всех таких та у которой правый узел расположен левее. **Минимальной совместимой парой называется наименьшая пара из всех совместимых.* '''Шаг 1.''' Изначально мы имеем только алфавит (и соответствующие веса) отсортированный лексикографически.1* '''Шаг 2. ''' ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор пока не останется одна вершина. 2* '''Шаг 3. ''' ''Определение уровней''. Находим номер уровня <tex>l_{i}</tex> каждого листа относительно корня. 3* '''Шаг 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> на вершину стека. * '''Шаг 3. ''' Удалить 2 верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные, если значение нового элемента равно нулю - остановится, иначе перейти к шагу 1.* Конец.