На этом шаге мы введем понятие декартового дерева.
Ж.Вуйлемен (J.Vuillemin) ввёл понятие "декартовы деревья", в которых каждый узел имеет два ключа (x,y) [1, с.513]:
- (1) часть x упорядочена слева направо, как в бинарных деревьях поиска;
- (2) часть y упорядочена сверху-вниз, как в случае структуры данных "Куча".
С.Р.Арагон и Р.Г.Зайдель (C.R.Aragon, R.G.Seidel) назвали такие структуры данных treap (название получено в результате комбинирования частей слов trees и heaps; русским термином является дуча - от "дерево" и "куча").
- Теорема.
- Только одна дуча может быть построена на основе n данных пар
(x1,y1),(x2,y2),...,(xn,yn).
Пример графической иллюстрации декартова дерева.
Пусть декартово дерево содержит следующие пары:
(1,2), (2,5), (6,4), (3,1), (5,3), (7,10), (4,6), (8,7).
Построим декартово дерево на декартовой плоскости:
Рис.1. Декартово дерево
Первым способом построения дучи является:
- (1) классическое включение ключа xi в качестве листа бинарного дерева поиска;
- (2) корректировка формы дерева в соответствии с порядком, определяемым ключом yi.
Второй способ построения дучи см. [2, с.121-123].
(1)Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. - М.: Издательский дом "Вильямс", 2000. - 832 с.
(2)Шестимеров А.А. Декартовы деревья: пример и реализация двоичного дерева поиска. / Московские учебно-тренировочные сборы по информатике. Весна-2006. - М.: МЦНМО, 2007, с.116-127.
На следующем шаге мы рассмотрим несколько демонстрационных примеров.
