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

Содержание 55
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
1) xmin ≤ p.x < x max .
2) p.l соответствует интервал [xmin, M[ .
p.r соответствует интервал [ M, xmax [ .
M= (x min + x max)/2;
Пример корневого дерева:
0 10 50 90 х
1 [a,b[ = [10, 90[
5
10
у
Рис. 58. Корневое дерево
Сыновья каждой вершины должны попадать: левый – в левый
подынтервал, правый – в правый подынтервал. (RPST – radix priority search
tree)
Ограничением на использование корневых деревьев является требование
того, чтобы никакие 2 вершины не имели одинаковые компоненты Х.
Быстродействие. Пусть дискретность по Х составляет некоторую величину
∆, тогда с каждым шагом поиска начальный интервал неопределенности [ a,b[
сокращается вдвое и в худшем случае становится равной ∆. Таким образом, в
худшем случае число шагов будет log2 ((b-a)/ ∆).
(Алгоритмы поиска / включения / исключения – самостоятельно!)