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

Содержание 53
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
компоненте x используем инварианты дерева бинарного поиска, а по
компоненте y - инварианты пирамиды:



<
≤
⇒≠
;. ..
; . ..
λ . xp xlp
yp ylp
lp



>
≤
⇒≠
;. ..
; . ..
λ . xp xrp
yp yrp
rp
В каждом дереве 2 ключа (x,y):
5, 1
3, 6 8, 4
4,10 7,10 10,8
Рис. 55. Декартовое дерево
Такие деревья называют Декартовыми, или деревьями приоритетного
поиска, так как их структура хорошо интерпретируется в двумерной
Декартовой системе координат.
0 5 10 х
5
10
у
5, 1
8, 4
10,8
7,10
3, 6
4,10
Рис. 56. Декартовое дерево в системе координат