ВУЗ:
Составители:
73
Рис. 5.22. Произвольное двоичное дерево
Как уже говорилось выше, для выполнения различных процедур обра-
ботки данных наиболее удобны симметричные деревья. Процедура перестройки
несимметричного дерева в симметричное производится в два этапа. На первом
этапе исходная последовательность записей упорядочивается по возрастанию
или убыванию ключей. На втором этапе определяются
ключи, размещаемые в
узлах различных уровней дерева. В корневом узле размещается ключ, соответ-
ствующий середине диапазона ключей всей последовательности. Ключи, деля-
щие пополам левую и правую половины диапазона последовательности, разме-
щаются в узлах второго уровня левого и правого поддеревьев соответственно.
Указанная процедура продолжается до тех пор, пока не будет построено все
дерево.
Построим симметричное дерево для рассмотренной выше последова-
тельности. Для этого упорядочим ее по возрастанию значений ключей: 7, 19, 21,
33, 36, 38, 51, 63, 100, 180, 260, 286, 290. Ключ со значением 51 помещается в
корень дерева. Узлом второго уровня в левом поддереве могут стать ключи 21
или 33, а в правом – 180 или 260. Выберем ключи 33 и 180 соответственно.
Продолжая эту процедуру, получим двоичное симметричное дерево, показанное
на рис. 5.23.
Рис. 5.23. Двоичное симметричное дерево
286
7
36
63
51
260
290
180
100
38
33
21
19
286
1
80
38 100
63
1
9
51
367 21 260 290
33
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
