Дерево відрізків

У інформатиці, дерево відрізків це деревоподібна структура даних яка застосовується для зберігання даних у відрізках, згрупованих так, що відомо, які з них містять дану точку.

Дерево відрізків для множини $S$ з $n$ відрізків використовує $O(n\log n)$ пам'яті і його можна побудувати за $O(n\log n)$ часу. Дерево забезпечує виконання операції зі знаходження усіх відрізків, що містять задану точку за час $O(\log n+k)$ де $k$ — кількість отриманих відрізків.

Вікнування відрізків на площині

Звернімо увагу, що для відповіді на запит про належність точки інтервалам із використанням дерева інтервалів потрібно так само $O(\log n+k)$ часу за умови лінійної кількості пам'яті, отже для цього завдання краще обирати дерево інтервалів. Коли ж ми бажаємо отримати відповідь на складніші запитання як-от вікнування відрізків тоді дерево відрізків потужніша структура. Причиною цього є те, що множина інтервалів, що включають запитану точку, є саме об'єднанням канонічних підмножин які ми вибираємо під час пошуку у дереві. У дереві інтервалів ми повинні додатково пройти декілька елементів з початку відсортованих списків, що зберігаються у вузлах дерева. Отже, для дерева відрізків, ми маємо можливість збереження канонічних підмножин у асоціативній структурі, що дає можливість виконання додаткових запитів уже у цій структурі.

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

Цей розділ описує структуру дерева відрізків в одновимірному просторі.

Нехай S буде набором інтервалів або відрізків. Нехай p₁, p₂, ..., p_m буде списком відмінних кінців інтервалів, відсортованих зліва направо. Розглянемо розбиття дійсної лінії цими точками. Регіони такого розбиття називають елементарними інтервалами. Отже, елементарними інтервалами є, зліва направо:

$(-\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 )$

Це є список елементарних інтервалів між послідовними кінцевими точками p_i і p_i+1, що перемежаються з закритими інтервалами, що складаються з однієї точки. Одна точка розглядається як інтервал, оскільки відповідь на запит не обов'язково однакова всередині елементарного інтервалу і на його границях.

Зображення структури дерева відрізків. Цей примірник побудовано для відрізків показаних під ним. Зауважте, кожен інтервал зберігається не більше двох разів на кожному рівні.

Для заданої множини інтервалів або відрізків I, дерево відрізківT структуровано так:

• T — двійкове дерево.
• Його листові вузли відповідають елементарним інтервалам утвореним в I, впорядкованим способом: найлівіший лист відповідає найлівішому інтервалу і так далі. Елементарний інтервал, що відповідає листу v позначають Int(v).
• Внутрішній вузол T відповідає інтервалу який є об'єднанням елементарних інтервалів: інтервал Int(N) відповідний вузлу N є об'єднанням інтервалів відповідних листям дерева з коренем у N. Тобто, Int(N) є об'єднанням інтервалів своїх двох дочірніх вузлів.
• Кожен вузол або лист v у T зберігає інтервал Int(v) і множину інтервалів, у деякій структурі даних. Ця канонічна підмножина вузла v містить інтервали [x, x′] з I такі, що [x, x′] містить Int(v) і не містить Int(parent(v)). Тобто, кожен відрізок у I зберігає відрізки, що покривають цей інтервал, але не покривають інтервал батьківського вузла.

Джерела

• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). More Geometric Data Structures. Computational Geometry: algorithms and applications (вид. 2nd). Springer-Verlag Berlin Heidelberg New York. doi:10.1007/978-3-540-77974-2. ISBN 3-540-65620-0.