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
. По
1...,44,45,46,47,48,49,50,51,52,53 55,56,57,58,59,60,61,62,63,64,...106