Как можно доказать, что для каждого абсолютного бинарного дерева (каждый узел имеет либо 0, либо 2 потомков) существует ряд Хаффмана, который может быть представлен этим деревом.
Любые подсказки будут высоко оценены!
Докажите: каждое абсолютное бинарное дерево может представлять собой ряд Хаффмана.
comment
Что говорят ваши конспекты лекций?
- person Jonas Bötel schedule 06.12.2013
Ответы (1)
Конструктивное доказательство: если a_1,..., a_k - глубины листьев, то ряд может быть b_1 = 2^(-a_1),..., b_k = 2^(-a_k).
- Сумма всех b_i = 1. Доказательство по индукции: для одного узла это верно; два родственных листа глубины A могут быть сведены к своему родителю и дадут один узел глубины A-1, при этом сумма b_i не изменится.
- Почти так же можно доказать, что последовательность b_i может дать в точности заданное дерево, если использовать алгоритм Хаффмана.
person
Ivan Smirnov
schedule
06.12.2013
