ВУЗ:
Составители:
110
Рис. 38. Дерево сравнений бинарного поиска
Сравнение K и K
8
на рисунке представлено корневым узлом номер 8.
Если K < K
8
, то алгоритм переходит в левое поддерево и сравниваются K
и K
4
. В противном случае, если K > K
8
, то алгоритм переходит в правое
поддерево и сравниваются K и K
12
. В противном случае при равенстве K
и K
8
алгоритм завершается успешно. Вообще при успешном завершении
поиска алгоритм останавливается в одном из внутренних «круглых» уз-
лов. Например, в круглом узле номер 3 алгоритм остановится при K = K
3
.
Неудачный же поиск приведёт в один из внешних «квадратных» узлов,
пронумерованных от 0 до N. Например, квадратный узел номер 6 будет
достигнут при K
6
< K < K
7
, квадратный узел номер 7 – при K
7
< K < K
8
.
Бинарное дерево, соответствующее бинарному поиску в таблице из
N записей, может быть построено следующим образом. Если N = 0, то де-
рево представляет собой просто квадратный узел номер 0. В противном
случае корневым узлом дерева будет круглый узел с номером N / 2 . При
этом левое поддерево представляет собой бинарное дерево с (N / 2 – 1)
круглыми узлами, а правое поддерево – бинарное дерево с N / 2 круг-
лыми узлами. Отметим, что все числа в узлах правого поддерева увели-
чены на N / 2 по сравнению с числами в соответствующих узлах левого
поддерева.
Точно так в виде бинарного дерева с N узлами, в котором все узлы
пронумерованы числами от 1 до N, может быть представлен любой алго-
ритм поиска в упорядоченной таблице длиной N (если только алгоритм
не выполняет излишние сравнения). Верно и обратное – любое бинарное
дерево соответствует некоторому методу поиска в упорядоченной табли-
це. При этом достаточно просто пометить узлы
16
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Страницы
- « первая
- ‹ предыдущая
- …
- 108
- 109
- 110
- 111
- 112
- …
- следующая ›
- последняя »
