Попередня Змiст Наступна

3.4.2 МЕТОД БАГАТОВИМІРНОГО ДВІЙКОВОГО ДЕРЕВА
(2-D-дерева)

Назвемо (узагальненим) прямокутником таку область на площині, яка визначена декартовим добутком [x1, x2]×[y1, y2], включаючи граничні випадки, коли у будь-якій комбінації допускається: x1= -, x2 = , y1= -, y2 = .
Процес розбиття S шляхом розрізання площини краще за все ілюструвати у поєднанні з побудовою двовимірного двійкового дерева Т: "v T $(R(v),S(v) S, P(v) і "січна пряма" l(v)). Процес подрібнення завершиться, коли з'явиться прямокутник, який не містить всередині жодної точки, відповідний йому вузол є листком дерева Т.
Вузли бувають трьох різних типів і мають позначення: кружки - нелистові вузли з вертикальною лінією розрізу, квадрати - нелистові вузли з горизонтальною лінією розрізу, точки - листки. Така структура даних часто називається 2-Д-деревом.
Мал. 3.20. Ілюстрація метода пошуку за допомогою двовимірного двійкового дерева.

Алгоритм пошуку.
Алгоритмічна схема - метод "розділяй та володарюй". Будь-який вузол v завантажений такими параметрами: Р(v), R(v), S(v), l(v), D (мал. 3.20(b)).
Де Р(v) - поточна точка, R(v) - прямокутна область, S(v)- множина точок, яка належить R(v), l(v)- розрізаюча пряма, яка проходить через точку Р(v), D - запитний регіон.
Від взаємного розташування R(v), S(v), l(v), D для кожного вузла v Т залежить регіональний пошук: "v Т пряма l(v) розбиває R(v) = R1(v) R2(v), R1(v) D, R2(v) D.
  1. D R1(v) Ø і R2(v) D = Ø лівий пошук (в D R1(v));
  2. D R2(v) Ø і R1(v) D = Ø правий пошук (в D R2(v));
  3. D R1(v) Ø і R2(v) D Ø лівий (в D R1(v)) і правий (в D R2(v)); перевірка Р(v) D. Де *,(+), (-) визначають перевірку на належність точки регіону, вдалий і, відповідно, невдалий результат цієї перевірки.
Більш строго. "v Т:(Р(v), t(v ), М(v)): (t(v ), М(v)) визначають пряму l(v): t(v) визначає горизонтальність (y=M(v) (M(v)= y(Р(v))) чи вертикальність (x=M(v) (M(v)= x(Р(v))) l(v); алгоритм накопичує точки у списку U - зовнішньому до процедури і спочатку порожньому. Позначимо через D= [x1, x2]×[y1,y2] запитний регіон, тоді має місце:
procedure ПОШУК(v, D);
begin if (t(v) = вертикаль) then [l, r]:= [x1, x2] else [l, r]:= [y1, y2];
if (l M(v) r) then if (P(v) D) then U P(v);
if (v листок) then
begin if (l < M(v)) then ПОШУК(ЛСИН[v], D);
if (M(v) < l) then ПОШУК(ПСИН[v], D)
end
end.
Оцінка складності: пам'ять - O(N), побудова дерева - O(NlogN). Вертикальний розріз множини S проводиться у результаті обчислення медіани множини х-координат точок з S за час O(|S|), і шляхом формування розбиття S з такою ж оцінкою часу;аналогічно і для горизонтального розрізу; за час O(N) вихідна множина розбивається, в результаті чого отримуємо півплощини, в кожній із яких по N/2 точок; тривіально отримуємо рекурентне співвідношення для часу T(N) роботи алгоритма побудови дерева:
T(N) 2T (N/2) + O(N).
Аналіз часу запиту для найгіршого випадку. Якщо час витрачений у вузлі v не даремно, то точка Р(v) вибирається (продуктивний вузол); інакше, цей вузол є непродуктивним. Перетин запитного регіну D з R(v) можє бути віднесений до різних "типів" в залежності від числа сторін R(v), які мають непорожні перетини з D (мал. 3.21).
Мал. 3.21. Приклади різних типів перетинів D і R(v), коли D R(v) Ø.
На мал. 3.22 (а),(б) розглянуто ситуації, коли перетин типу 2 на висоті m непродуктивний і породжує перетин типу 2 і перетин типу 3 на висоті (m -1) ( обидва можна зробити непродуктивними) та, при тому самому обмежені на типи непродуктивних вузлів, коли перетин типу 3 на висоті m в Т породжує пару перетинів типу 3 на висоті (m -2), відповідно.
Мал. 3.22.Ситуації, які відповідають непродуктивним вузлам в Т.
Позначивши через Ui(m) - число пройдених непродуктивних вузлів у піддереві висотою m, корінь якого має тип i(i=2,3), одержимо рекурентні співвідношення:
U2(m)= U2(m-1)+ U3(m-1)+1
U3(m)=2U3(m-2)+3     (2.3)
Теорема 3.14 Для файлу потужністю N в найгіршому випадку час запиту становить , навіть якщо вибрана множина виявиться порожньою.
Результуюче розбиття d-вимірного простору моделюється двійковим деревом з N вузлами, яке називається багатовимірним двійковим деревом (d-D-деревом). Аналіз ефективності можна узагальнити на випадок d вимірів.
Теорема 3.15 За допомогою методу d-D-дерева регіональний пошук на d-вимірній множині (при d 2) з N точок можна провести за час O(dN1-1/d + k) з використанням O(dN) пам'яті, якщо витратити O(dN log N) часу на попередню обробку. Через це метод d-D-дерева дає (dN, dN1-1/d)-алгоритм.

Попередня Змiст Наступна