5 / 14
Алгоритм кодирования бинарного дерева с минимальной избыточностью
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
37
При этом левое поддерево комбинации
1
1
N
C
−
−
будет полностью ориентировано
по правую сторону. На индексе
1
N
C
−
один узел должен быть перенесен из левого
в правое поддерево:
1
;
N
I C
−
=
2;
L
N N
= −
1.
R
N
=
Следующие
2
N
C
−
индексы пе-
речисляют различные комбинации левого поддерева
(
2),
L
N N
= −
при правом
поддереве, состоящем из одного узла (рис. 3,
б
,
в
).
Рис. 3.
Первые
1
N
C
−
комбинаций дерева
(
а
) и комбинации с
1
N
C
−
(
б
)
по
1
2
1
N
N
C C
−
−
+
−
(
в
)
На комбинации
1
2
N N
C C
−
−
+
еще один узел должен быть перенесен из лево-
го в правое поддерево:
1
2
;
N N
I C C
−
−
= +
3,
L
N N
= −
2.
R
N
=
Начиная с
2
R
N
=
число возможных структур правого поддерева отлично от единицы и равно
.
R
N
C
В общем случае это правило можно распространить и на
{ }
0, 1 ,
R
N
=
так
как
0
1
1.
C C
= =
Таким образом, для каждого
L
N
от
1
N
−
до 0 число различных
комбинаций левого и правого поддеревьев равно
1
L
L
N N N
C C
− −
. Это соответству-
ет формуле рекуррентного соотношения для вычисления чисел Каталана:
0
1
C
=
и
1
1
0
N
N
i N i
i
C C C
−
− −
=
=
для
0.
N
>
С учетом изложенного, для получения чисел
L
N
и
R
N
необходимо найти такое
K
, что
1
0
;
K
N i
i
i
C C I
− −
=
<
(2)
1
1
0
;
K
N i
i
i
C C I
+
− −
=
>
;
R
N K
=
1.
L
N N K
= − −
Для определения параметров
L
I
и
R
I
необходимо предварительно вычислить
индекс текущей комбинации для заданных значений
L
N
и
R
N
:
1
0
ˆ
.
K
N i
i
i
I I
C C
− −
=
= −
Значение ˆ
I
равно разности заданного индекса комбинации и индекса последней
комбинации, на которой было выполнено перемещение узла из левого поддерева в
правое (т. е. уменьшение числа
L
N
и увеличение числа
).
R
N