Бинарные деревья

Бинарными называют упорядоченные деревья, в которых каждый узел имеет не более двух, непосредственно следующих

за ним узлов (рис. 9).

a

c b d

g e f

h i

Рис. 9

Бинарные деревья наиболее часто используются для представления информации, обрабатываемой с помощью вычислительных машин. Рекурсивно бинарное дерево можно определить как конечное множество узлов, которое или пусто, или состоит из корня и двух не имеющих общих узлов бинарных деревьев – левого и правого.

Приписывая дуге, ведущей из произвольного узла к левому дереву, символ «0», а дуге, ведущей к правому дереву, символ «1», можно любой путь из корневой вершины (а вместе с ним и конечную вершину этого пути) закодировать с помощью нулей и единиц.

Например, на рис. 9 корневая вершина a получает в качестве кода пустую последовательность ∅, а остальные вершины следующие коды:

b – 1; c – 10; e – 100; f – 101;

d – 11; g – 111; h – 1110; i – 1111.

Найдем число различных бинарных деревьев с заданным числом вершин.

Пусть bn – число различных бинарных деревьев с n вершинами. Ясно, что b0 = 1 (имеется ровно одно пустое бинарное дерево) и b1 = 1.

При n > 0 всякое бинарное дерево с n вершинами имеет вид (a; (T0, T1)), где T0 – бинарное дерево с k < n вершинами, а T1 – бинарное дерево с n – k – 1 вершиной. Число способов расположить одно бинарное дерево с k < n вершинами слева от

корня, а другое бинарное дерево с n – k – 1 вершиной справа от корня равно bkbn–k–1. Следовательно, суммируя по всем k < n,

получаем:

bn = b0bn–1 + b1bn–2 + … + bn–1b0. (1)

В частности:

b1 = b02 = 1; b2 = b0b1 + b1b0 = 2;

b3 = b0b2 + b1b1+ b2b0 = 5; … .

Последние равенства показывают, что последовательность чисел (bn) – это последовательность чисел Каталана (см. 11.4).

Для полноты изложения напомним коротко, как могут быть

получены явные выражения в факториалах для чисел bn.

Запишем производящую функцию:

B(z) = b0 + b1z + b2z2 + … . (2)

Основываясь на (1), получаем:

B(z)2 = b02 + (b0b1 + b1b0)z + (b0b2 + b1b1+ b2b0)z2 … =

= b1 + b2z + b3z2 + … .

Умножая обе части последнего равенства на z и добавляя 1,

приходим к соотношению

z⋅B(z)2 +1 = B(z).

Таким образом, y = B(z) удовлетворяет квадратному уравнению

z⋅y2 – y +1 = 0.

Решая его, находим:

B( z) 

1 1−

2z

1 − 4 z .

Теперь разложим правую часть полученного равенства,

воспользовавшись биномом Ньютона:

 1/ 2 

B(z) 

∑ (−1)k 

⋅22n 1 zn .

n ≥0

n 1

Сравнивая (1) и (2), приходим к заключению, что для всех n

справедливо следующее равенство:

 1/ 2 

1 2n

bn =

(−1)k 

⋅22n 1 =

  . (3)

n 1

n 1 n 

Пример.Перечислим все бинарные деревья с 4 вершинами.

В соответствии с формулой (3) имеем:

b  1 8  8⋅7 ⋅6⋅5

14 .

 

4 5 4



5 ⋅ 4 ⋅ 3 ⋅ 2

 

На рис. 10, представлены четырнадцать бинарных деревьев с четырьмя вершинами.

Рис. 10

Применим к (3) формулу Стирлинга. Получаем:

1 4рn ⋅(2n)2n e− 2n

22n

bn ≈

n  1

 2рn ⋅n

ne− n 2

=

(n 1)

. (4)

рn

Формула (4) дает хорошее приближение даже при сравнительно малых значениях n. Например, при n = 4 имеем:

b4 ≈

≈ 14,4.

4р