Какое максимальное количество узлов в дереве Хаффмана если мощность алфавита 256 символов?
3
-
2Ну, как мне кажется, это будет в случае вырожденного дерева. 256 листьев + 255 внутренних узлов, так что если считать листья узлами — 511.– Harry28 ноя 2021 в 15:30
-
2Дерево Хаффмана - двоичное дерево у которог каждый внутренний узел имеет двух потомков. По индукции доказывается что число внутренних узлов на один меньше числа листьев. См. комментарий @Harry далее.– Stanislav Volodarskiy28 ноя 2021 в 16:34
-
@StanislavVolodarskiy Да, как-то не сложилось в голове, что глубина и число узлов — вещи перпендикулярные. Так что ответ дал верный, но неверный... :)– Harry28 ноя 2021 в 18:09
Добавить комментарий
|