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

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

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

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

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

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

${\displaystyle (-\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, що перемежаються з закритими інтервалами, що складаються з однієї точки. Одна точка розглядається як інтервал, оскільки відповідь на запит не обов'язково однакова всередині елементарного інтервалу і на його границях.^[2]

Для заданої множини інтервалів або відрізків 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 зберігає відрізки, що покривають цей інтервал, але не покривають інтервал батьківського вузла.^[3]

• 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.