Математическое моделирование на графах. Часть 1. Берцун В.Н. - 35 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Глава 1. Основные понятия теории графов 35
На рис. 1.39 представлено бинарное четырехъярусное дерево ре-
шений для сортировки по убыванию трехэлементного массива про-
стым выбором
x
1
x
2
x
3
12
x
1
x
2
x
3
x
1
x
3
x
1
x
2
x
3
x
2
x
2
x
3
x
1
x
3
x
2
x
1
x
1
x
1
x
2
x
3
x
2
x
3
x
3
x
3
x
x
Рис. 1.39
Если корень дерева соответствует первому ярусу, то на m-м ярусе
бинарного дерева находится 2
(m–1)
узел, а у полного двоичного (иде-
ального) дерева с k ярусами 2
k
– 1 узел. У дерева с N! листьями чис-
ло ярусов k есть наименьшее целое число, для которого
N! ≤ 2
(k–1)
или log
2
N! ≤ k – 1 .
Если у каждой вершины дерева, кроме последней, есть только
один потомок, то такое дерево называется вырожденным и соответ-
ствует линейному списку. Для числа бинарных деревьев на n верши-
нах, которое определяется как сумма чисел возможных комбинаций
левых и правых поддеревьев, имеют место формулы [20]
(1)
2
/
(1), 2 ,
nn
nn v
tC n t
−
=+=
где t
n
– число бинарных деревьев, t
v
– число вырожденных деревьев.
На рис. 1.40 приведены все возможные вырожденные деревья для
n = 3.
Рис. 1.40

Страницы