Стр. 54 - Основы алгоритмов и структур данных

52 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5
3 8
4 7 9
7
4 9
3 5 8
Рис. 53. Примеры деревьев
Заметим: левый и правый – понятия горизонтального направления, а по
вертикали взаимное положение вершин в дереве бинарного поиска
безразлично.
2-й случай.
Пирамида (дерево с приоритетом) управляется следующими инвариантами
(у – это ключ):
если λ . ≠ lp , то р.l.у <= p.y;
если λ . ≠ rp , то p.r.у <= p.y.
Для пирамиды могут применяться обратные инварианты
если λ . ≠ lp , то р.l.у >= p.y ;
если λ . ≠ rp , то p.r.у >= p.y.
Пример пирамиды (по второму случаю):
12 10 9
4 8
12 10 9
8 4
3 3
Рис. 54. Примеры пирамид
Каждая вершина легче каждого из своих потомков. Расположение вершин
по горизонтали в пирамиде роли не играет.
Для решения задач двумерного поиска объединим свойства рассмотренных
структур. Теперь каждой вершине P соответствуют два ключа: p.x и p.y. По