9 / 14
Алгоритм кодирования бинарного дерева с минимальной избыточностью
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
41
В случае функции
decode
основные вычисления вне рекурсивных вызовов
выполняются при расчете формулы (2). На каждом этапе суммирования вычис-
ления произведения
1
,
i N i
C C
− −
что имеет суммарную сложность
( )
.
O N
С учетом
допущения о том, что поиск останавливается после
N
итераций, функция
( )
f n
пропорциональна
2
.
n
Для заданных условий выполняются следующие условия:
( )
2
2
;
2
n
T n T n
=
+
( )
( )
Ω ,
c
f n n
=
2;
c
=
log ,
b
c
a
>
2;
a b
= =
( )
n af
kf n
b
≤
для
0, 5.
k
=
Эти условия соответствуют третьей форме основной теоремы о рекуррентных
соотношениях, при которой время работы функции
decode
имеет асимптотиче-
скую оценку
( )
( )
(
)
( )
2
Θ
Θ .
T n
f n
n
=
=
Для функции
encode
при тех же допущениях можно применить рассужде-
ния, аналогичные рассуждениям, использованным для функции
decode
, и
оценка времени работы алгоритма также равна
( )
2
Θ .
n
Результаты.
Примеры использования разработанного метода для перечис-
ления всех структур бинарных деревьев с тремя и четырьмя узлами приведены
на рис. 5 и рис. 6. Это перечисление было проведено программно, пример реа-
лизации алгоритма на языке
Python
можно найти в работе [10]. Для визуализа-
ции деревьев были использованы язык разметки
dot
[11] и система
Graphviz
.
Каждое показанное на рисунках бинарное дерево было построено на основании
индекса
I
и числа узлов
.
N
Рис. 5.
Бинарные деревья, построенные на основании индекса
ܫ
и числа узлов
N
= 3
(в скобках указаны представления индексов в двоичной системе счисления):
а
—
I
= 0 (000
b
);
б
—
I
= 1 (001
b
);
в
—
I
= 2 (010
b
);
г
—
I
= 3 (011
b
);
д
—
I
= 4 (100
b
)
Сравнение размеров битовых последовательностей при кодировании алгорит-
мом, требующим ровно
2
N
бит
( )
1
,
L
и кодировании разработанным алгоритмом
( )
2
,
L
а также относительные избыточности кода для существующего
( )
1
R
и