Использование квадро-деревьев



Скачать 16.67 Kb.
Дата02.07.2013
Размер16.67 Kb.
ТипДокументы
Использование квадро-деревьев.
Квадро-деревья - это деревья с полустепенью исхода(out-degree) 4. То есть у каждого узла может быть до 4 сыновей.
Корень дерева делит область на 4 квадранта СВ, СЗ, ЮЗ, ЮВ (в соответствии с картой). Пернумеруем квадранты 1, 2, 3, 4.

Исходная картинка и полученное по картинке дерево:


Линии принадлежат квадрантам 1 и 3 (это соглашение неважно для дерева, но удобно для целей быстрого решения в каком квадранте от корня лежит данный узел). Не учитывается совпадение точек. Если таковые могут быть, то в узле можно иметь ссылку на список точек.
Введем функцию Compare(A, B) - по отношению к двум записям А и В она дает целочисленный результат, указывающий номер квадранта А, который содержит В. Compare(A, A) = 0.
Удобна также функция Conjugate(Direction) - сопряженность. Conjugate(3)=1,

Conjugate(N)=((N+1)mod 3)+1.
Обозначим node – узел дерева (все дерево – тоже узел). Поддерево узла, скажем 3-е поддерево узла ELM обозначается ELM(3). NULL - пустой узел. ELM(0) = NULL;
Поиск в дереве.
procedure RegSearch(P : node; L, R, B, T : real);

{L-left, R-right, B-bottom, T-top -- регион поиска}

xc, yc: real; {координаты узал в дереве}

xc := x(P); yc := y(P);

if in_region(xc, yc) then Found(P);

if P[1]<>NULL and Rect_overlaps_Region(xc, R,yc,T) then RegSearch(P[1], xc, r, yc,t);

....

if P[3]<>NULL and Rect_overlaps_Region(L,xc,B,yc) then RegSearch(P[3],L, xc, B, yc);

Вставка в дерево.
При вставке в квадро-дерево используется та же идея, что и для бинарного дерева. В каждом узле делается проверка, выбирается соответствующее поддерево. Как только алгоритм вываливается за пределы дерева - вставляется новая запись.
procedure insert(K,R : node)

begin {вставить запись К в дерево с корнем R}

dir : integer;

dir := Compare(R, K);

while R[dir]<>NULL do

begin {с каждой итерацией на уровень глубже}

R := R[dir];

dir := Compare(R, K);

end;

if(dir = 0) then return; {узел уже существует}

R[dir] := K;

end;
Худший случай (все в линейку) - время n(n-1)/2, O(n2)

Эксперимент дает O(n log N)
Для улучшения результата можно провести балансировку дерева:


балансировка двойная балансировка

Неочевидно, как организовать удаление узла и слияние 2ух деревьев.


Примеры запросов: "Найти все города в 300-мильной зоне от Чикаго или севернее Сиэттла"

Похожие:

Использование квадро-деревьев icon«День посадки деревьев»
«День лесопосадок», «День деревьев», «День дерева» своеобразный праздник, который отмечается в ряде стран мира, и как видно из его...
Использование квадро-деревьев icon1. Кроссворд "Названия деревьев"
Исполин растительного мира, сохранился только в Калифорнии. Высота некоторых деревьев достигает 150 м
Использование квадро-деревьев iconКроссворды о растениях Кроссворд "Названия деревьев"
Исполин растительного мира, сохранился только в Калифорнии. Высота некоторых деревьев достигает 150 м
Использование квадро-деревьев iconИсследовательская работа «использование комьютерных баз данных и других информационных технологий в изучении деревьев-рекодсменов»
Представляется для участия в районной научно-практической конференции учащихся
Использование квадро-деревьев iconЧем утеплить дерево? У плодовых деревьев существует большая разница между «вершками»
У плодовых деревьев существует большая разница между «вершками» и «корешками» по устойчивости их к низким температурам. Даже у самых...
Использование квадро-деревьев iconБольшой театр
Вячеслав Горский (фортепиано) и группа «Квадро». Шедевры классической музыки в джазовой обработке Вячеслава Горского
Использование квадро-деревьев icon«Подбор и размещение пород и сортов плодовых деревьев»
Дать общие сведения о породах и сортах плодовых деревьев. И правильном их подборе и размещении
Использование квадро-деревьев iconЛекция 11: Графы и деревья
...
Использование квадро-деревьев iconТаблица умножения и деления на 9
Оборудование: рисунок солнышка, карточки с условными обозначениями, картинки деревьев, запись «шума деревьев», карточки для индивидуальной...
Использование квадро-деревьев iconИ. И. Иванов Проверил ассистент кафедры ст
В работе необходимо изучить основные свойства деревьев, рассмотреть задачу построения остовных деревьев с минимальной суммой весов...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org