Стр. 56 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
54
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Алгоритм поиска написать самостоятельно!
Декартовы деревья не получили широкого распространения поскольку
алгоритмы включения-исключения на них реализуются крайне неэффективно и
не позволяют строить сбалансированные деревья.
Пример:
Новая вершина
Структура дерева до
включения
Структура дерева
после включения
Рис. 57. Пример включения вершины в декартовое дерево
(До включения – стрелочки, после включения - пунктир)
Чтобы избежать потерь на включение-исключение, вместо декартовых
деревьев, применяют их модификацию, так называемые корневые деревья
бинарного поиска.
Корневые деревья двумерного поиска строятся таким образом:
по компоненте
у
– как декартовое дерево, по компоненте
x
есть различие.
Допустим, известно, что ключ
x
вообще лежит в интервале [
а,b
[ (
a
–
включительно,
b
- невключительно ), тогда говорят, что корню дерева
соответствует интервал [
а,b
[ . Пусть некоторой вершине
р
соответствует
некоторый интервал [x
min
, x
max
[ . Тогда:
