Стр. 33 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
31
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
i
x
i
l
i
r
i
1
2
λ
2
2
5
λ
λ
3
8
1
4
4
11
λ
5
5
16
λ
λ
После включения z = 10:
i
1
2
3
4
5
6
x
i
2
5
8
11
16
10
Дерево поиска
3
4
5
2
1
6
Рис. 22. Дерево поиска после включения
i
x
i
l
i
r
i
1
2
λ
2
2
5
λ
λ
3
8
1
4
4
11
6
5
5
16
λ
λ
6
10
λ
λ
Очевидно, новый ключ дерева всегда можно вставить на место одного из
листьев.
Пусть требуется вставить новое имя
z
на место одного из листьев.
Пусть требуется включить имя
z
в дерево с корнем
p
.
Возможны 4 варианта.
1) если
p
– пусто, то включаем
z
в данную вершину.
2) если
z = x
p
, то
z
уже есть в таблице.
3) если
z < x
p
, то переходим к вершине
l
p
и повторяем там аналогично.
