ВУЗ:
Составители:
112
Рис. 39. Бинарное дерево поиска
На рисунке 39 показано бинарное дерево поиска, содержащее назва-
ния одиннадцати знаков зодиака
*
. Если приступить к поиску двенадцато-
го имени, SAGITTARIUS, начиная от корня дерева, то выяснится, что оно
больше (лексикографически), чем CAPRICORN, и нужно идти вправо.
Оно больше, чем PISCES, и необходимо опять идти вправо. Оно меньше,
чем TAURUS, и нужно идти влево. Оно меньше, чем SCORPIO, и мы по-
падаем во внешний узел номер 8. Поиск оказался неудачным, и теперь
можно вставить имя SAGITTARIUS в то место, где завершился поиск, т.е.
на место внешнего узла номер 8. Таким образом, таблица может расши-
ряться без перемещения уже существующих записей.
Заметим, что дерево на рис. 39 было получено путём последова-
тельной вставки в пустое дерево ключей CAPRICORN, AQUARIUS,
PISCES, ARIES, TAURUS, GEMINI, CANCER, LEO, VIRGO, LIBRA,
SCORPIO в указанном порядке. В этом дереве ключи левого поддерева
меньше (в лексикографическом порядке), чем CAPRICORN, а все ключи
правого поддерева – больше его. То же самое справедливо для левого и
правого поддеревьев любого узла. Отсюда следует, что при обходе дере-
ва в симметричном порядке (левое поддерево, корень, правое поддерево)
*
Список знаков зодиака, упорядоченный по месяцам таков: Козерог (Capri-
corn), Водолей (Aquarius), Рыбы (Pisces), Овен (Aries), Телец (Taurus), Близнецы
(Gemini), Рак (Cancer), Лев (Leo), Дева (Virgo), Весы (Libra), Скорпион (Scorpio),
Стрелец (Sagittarius).
CAPRICORN
AQUARIUS PISCES
ARIES GEMINI TAURUS
CANCER LEO SCORPIO VIRGO
0
1
2
3
11
4
5
6
7
8
9
10
LIBRA
Страницы
- « первая
- ‹ предыдущая
- …
- 110
- 111
- 112
- 113
- 114
- …
- следующая ›
- последняя »
