73
правки
Изменения
м
→Алгоритм
}}
== Алгоритм ==
0. ''Введем следующие понятия''. Две вершины называются совместимой парой, если они соседние или если между ними нет вершин алфавита. Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов, из всех таких выбирается пара с самой левой вершиной, из всех таких та у которой правый узел расположен левее. Минимальной совместимой парой называется наименьшая пара из всех совместимых.
1. ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор пока не останется одна вершина.
