Стр. 34 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
32
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4) если
z > x
p
, то переходим к вершине
r
p
и повторяем там аналогично.
Заметим, что если пустой лист заменяем на вершину, то необходимо
заменить указатель на неё от отцовской вершины.
Алгоритм 6.
p
– указатель на корень
z
– новый
insert (z,p)
{
if p =
λ
{
p = новая вершина(n+
1
)
x
p
= z;
l
p
=
λ
;
r
p
=
λ
;
}
else
╓
║ z = x
p
: < z уже есть >;
║
case ─╢ z < x
p
: insert(z, l
p
);
║
║ z > x
p
: insert(z, r
p
);
╙
}
Параметр
p
должен передаваться по ссылке, а не по значению, а параметр
z
– по значению.
Заметим, что после включения, отношение лево – право по – прежнему
отражает больше-меньше.
4.4.1.2. Исключение
Исключение начинаем с поиска.
Возможны следующие варианты:
1)
z
в таблице нет.
2) если
z
является листом, то решение простое: уничтожаем лист.
3)
z
имеет одного сына. Объявляем сына
z
сыном отца
z
.
