2 / 14
В.П. Корвяков
34
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
Рис. 1.
Формирование хромосом при скрещивании в процессе работы генетического
алгоритма
Требование существования строго двух поддеревьев у каждого нелистового уз-
ла является ограничением, которое можно снять, если рассмотреть строго бинар-
ное дерево с
N
+ 1 листьями как расширенное к обычному бинарному дереву с
N
узлами. При этом
N
узлов обычного бинарного дерева можно ассоциировать с
«внутренними» (т. е. нелистовыми) узлами исходного дерева (рис. 2). В работе [2]
Д. Кнут показывает, что такая трансформация бинарных деревьев является одно-
значной и взаимной. С учетом изложенного, задача кодирования строго бинарного
дерева с
N
+1 листьями сводится к кодированию обычного бинарного дерева с
N
узлами. Далее перейдем к задаче кодирования обычных бинарных деревьев с
N
уз-
лами и будем иметь в виду ее эквивалентность исходной задаче кодирования строго
бинарных деревьев с
N
+1 листьями.
Рис. 2.
Схемы преобразований расширенного (
а
) и обычного (
б
) бинарных деревьев
Метод решения задачи.
Задача разработки алгоритма минимального и не-
противоречивого кодирования бинарных деревьев представляет отдельный ин-
терес. Последовательность битов должна кодировать любую структуру бинар-
ного дерева с заданным числом узлов
N
. Число неизоморфных бинарных дере-
вьев с
N
узлами равно
N
-му числу Каталана [3]:
( )
(
)
=
=
+
+
2
2 !
1
.
1
1 ! !
N
N
N
C
N N
N N
(1)
Если рассмотреть бинарное дерево, каждая структура которого имеет рав-
ную вероятность, как сообщение, то его энтропия равна
=
=
= −
= −
=
2
2
2
1
1
1
1
log
log
l
.
og
N
N
C
C
i
i
N
N
N
i
i
H p p
C
C
C