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. Декартовое дерево в системе координат
1...,45,46,47,48,49,50,51,52,53,54 56,57,58,59,60,61,62,63,64,65,...106