Сегментно стабло

У информатици, сегментно стабло је дата структура за чување интервала или сегмената. Дозвољава упитивање који од сачуваних сегмената садржи задату тачку. То је у принципу статичка структура; њен садржај не може бити модификован када је структура направљена.

Сегментно дрво за I од н интервала користи О(н лог н) меморије и може бити направљено за О(н лог н) времена.Сегментна дрва подржавају претраживање за све интервале који садрже упитну тачку у О(лог н + к), к број примљених интервала или сегмената.

Опис структуре

Овај одељак описује структуру сегментног дрвета у једнодиментионалном простору

Нека С буде сет интервала или сегмената. Нека п₁, п₂, ..., п_м буде листа различитих интервала крајњих тачака, сортираних од лева на десно. Регије овог партиционисања се зову елементарни интервали. Елементарни интервали са лева на десно су:

$(-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],...,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )$

Графички приказ структуре сегментног дрвета. Ова инстанца је прављена за сегменте приказане на дну.

Дато је I од интервала или сегмената, сегментног дрвета Т за I је:

• Т је бинарно дрво.
• Његове гране одговарају елементарним интервалима индуковани крајњум тачкама у I, у поретку: лева грана одговара левом интервалу, и тако даље.
• Унутрашњи чворови Т одговарају интервалима који су унуја унутрашњих интервала: интервал Инт(Н) одговара чвору Н је унија интервала која одговара гранама дрвета корена Н. То имплицира да је Инт(Н) унија интервала своје двоје деце.
• Сваки чвор гране в у Т чува интервал Инт(в) и сет интервала, у неким дата структурама.

Захтеви меморје

Ова секција анализира меморијске захтеве сегментног девета у једнодимензионалном простору.

Сегментно дрво Т на I од н интервала користи О(нлогн) меморије.

Доказ:

Лема: Било који интервал [x, x′] од I се чува у канонском склопу највише за два чвора исте дубине.

I има највише 4н + 1 елементарних интервала. Зато што је Т бинарно балансирано дрво са највише 4н + 1 грана, висине О(логн). Синце анy интервал ис сторед ат мост тwице ат а гивен дептх оф тхе трее, тхат тхе тотал амоунт оф стораге ис О(нлогн).

Конструкција

Ова секција описује конструкцију сегментног дрвета у једнодимензионалном простору.

Сегментно дрво од сета сегмената I, може бити направљено на следећи начин:Прво, крајње тачке интервала у I су сортиране. Елементарни интервали су преузети одатле. Онда, балансирано бинарно дрво се прави на елементарним интервалима и за сваки чвор в детерминисан је интервал Инт(в) који представља. Преостаје да се израчунају канонске субстанце за чворове. Да бисмо постигли ово, интервали у I су убачени један по један у сегментно дрво. Интервал X = [x, x′] може бити убачен у под дрво са кореном Т, користећи следећу процедуру:

• Ако Инт(Т) постоји у X онда сачувати X у Т и крај.
• Иначе:
• Ако X се пресеца са канонским субсетом левог детета од Т, онда убаци X у то дете, рекурзивно.
• Ако X се пресеца са канонским субсетом десног детета од Т, онда убаци X у то дете, рекурзивно.

Комплетна конструкција операција узима О(нлогн) времена, н број сегмената у I.

Упит

Ова секција описује упитне операције сегментног дрвета у једнодимензионалном простору.

Упит за сегментно дрво, прима тачку q_x, и прима листу свих сегмената сачуваних који садрже тачку q_x.

Формално речено; дат је чвор (субтрее) в и упитна тачка q_x, упит може бити изведе користећи следећи алгоритам:

• Пријавити све интервале у I(в).
• Ако в није грана:
  • Ако q_x је у Инт(лево дете од в) онда
    • Извршити упит левог детета од в.
  • Иначе
    • Извршити упинт десног детета од в.

У сегментном дрвету које садржи н интервала, који садрже дати упит, тачка може бити репортована за О(логн + к) времена, где је к број пријављених интервала.

Генерализација за више димензије

Сегментно дрво може бити генерализовано за више димензионе просторе у форми сегментних дрвета са више нивоа. У верзијама више димензије, сегмента дрва чувају колекцију аxис-паралелних хиперуглова, и враћају углове који садрже дату упитну тачку. Структура користи О(нлог^д-1н) простора, I одговара за О(лог^дн).

Литература

• де Берг, Марк; ван Кревелд, Марц; Овермарс, Марк; Сцхwарзкопф, Отфриед (2000), Цомпутатионал Геометрy: алгоритхмс анд апплицатионс (2нд изд.), Спрингер-Верлаг Берлин Хеиделберг Неw Yорк, 3-540-65620-0