Рубрики

Интервальное дерево

Рассмотрим ситуацию, когда у нас есть набор интервалов, и нам нужны следующие операции для эффективной реализации.
1) Добавить интервал
2) Удалить интервал
3) Если задан интервал x, найдите, перекрывает ли x какой-либо из существующих интервалов.

Дерево интервалов: Идея состоит в том, чтобы расширить самобалансирующееся дерево двоичного поиска (BST), такое как красное черное дерево , дерево AVL и т. Д., Чтобы поддерживать набор интервалов, чтобы все операции могли выполняться за время O (Logn).

Каждый узел дерева интервалов хранит следующую информацию.
а) я : интервал, который представляется в виде пары [низкий, высокий]
b) max : максимальное максимальное значение в поддереве, укорененном в этом узле.

Низкое значение интервала используется в качестве ключа для поддержания порядка в BST. Операции вставки и удаления такие же, как операции вставки и удаления в используемом BST с самобалансировкой.

Основная операция заключается в поиске перекрывающегося интервала. Ниже приведен алгоритм поиска перекрывающегося интервала x в дереве интервалов с корнем root .

Interval overlappingIntervalSearch(root, x)
1) If x overlaps with root's interval, return the root's interval.

2) If left child of root is not empty and the max  in left child 
is greater than x's low value, recur for left child

3) Else recur for right child.

Как работает вышеуказанный алгоритм?
Пусть интервал для поиска будет х. Нам нужно доказать это в следующих двух случаях.

Случай 1: Когда мы идем к правильному поддереву, одно из следующего должно быть верным.
а) В правом поддереве есть перекрытие: это нормально, так как нам нужно вернуть один перекрывающийся интервал.
б) Нет перекрытия ни в одном поддереве: мы переходим к правому поддереву только тогда, когда левое значение равно NULL или максимальное значение слева меньше, чем x.low . Таким образом, интервал не может присутствовать в левом поддереве.

Случай 2: Когда мы идем в левое поддерево, одно из следующего должно быть верным.
а) Левое поддерево перекрывается: это нормально, так как нам нужно вернуть один перекрывающийся интервал.
б) Нет дублирования ни в одном поддереве: это самая важная часть. Нам нужно учитывать следующие факты.
… Мы пошли в левое поддерево, потому что x.low в левом поддереве
…. max в левом поддереве — максимум одного из интервалов, скажем, [a, max] в левом поддереве.
…. Поскольку x не перекрывается ни с одним узлом в левом поддереве, x.low должно быть меньше, чем ' a '.
…. Все узлы в BST упорядочены по низкому значению, поэтому все узлы в правом поддереве должны иметь низкое значение больше, чем « a ».
…. Из вышеупомянутых двух фактов мы можем сказать, что все интервалы в правом поддереве имеют низкое значение больше, чем x.low . Таким образом, x не может перекрываться с любым интервалом в правом поддереве.

Реализация дерева интервалов:
Ниже приводится реализация Interval Tree на C ++. Реализация использует базовую операцию вставки BST для простоты. В идеале это вставка дерева AVL или вставка красно-черного дерева . Удаление из BST оставлено в качестве упражнения.

#include <iostream>

using namespace std;

  
// Структура для представления интервала

struct Interval

{

    int low, high;

};

  
// Структура для представления узла в дереве интервального поиска

struct ITNode

{

    Interval *i;  // 'i' также может быть нормальной переменной

    int max;

    ITNode *left, *right;

};

  
// Вспомогательная функция для создания нового узла дерева интервального поиска
ITNode * newNode(Interval i)
{

    ITNode *temp = new ITNode;

    temp->i = new Interval(i);

    temp->max = i.high;

    temp->left = temp->right = NULL;

};

  
// Утилита для вставки нового узла дерева интервального поиска
// Это похоже на BST Insert. Здесь низкое значение интервала
// используется для поддержания свойства BST
ITNode *insert(ITNode *root, Interval i)
{

    // Базовый случай: дерево пусто, новый узел становится корнем

    if (root == NULL)

        return newNode(i);

  

    // Получить низкое значение интервала в корне

    int l = root->i->low;

  

    // Если нижнее значение root меньше, то новый интервал

    // левое поддерево

    if (i.low < l)

        root->left = insert(root->left, i);

  

    // Иначе, новый узел переходит в правое поддерево.

    else

        root->right = insert(root->right, i);

  

    // Обновляем максимальное значение этого предка, если это необходимо

    if (root->max < i.high)

        root->max = i.high;

  

    return root;

}

  
// Утилита для проверки перекрытия заданных двух интервалов

bool doOVerlap(Interval i1, Interval i2)

{

    if (i1.low <= i2.high && i2.low <= i1.high)

        return true;

    return false;

}

  
// Основная функция, которая ищет заданный интервал i в заданном
// Интервальное дерево.
Interval *overlapSearch(ITNode *root, Interval i)
{

    // Базовый случай, дерево пусто

    if (root == NULL) return NULL;

  

    // Если заданный интервал перекрывается с корнем

    if (doOVerlap(*(root->i), i))

        return root->i;

  

    // Если присутствует левый потомок root и максимум левого потомка

    // больше или равно заданному интервалу, тогда я могу

    // перекрываем с интервалом левое поддерево

    if (root->left != NULL && root->left->max >= i.low)

        return overlapSearch(root->left, i);

  

    // Остальные интервалы могут перекрываться только с правым поддеревом

    return overlapSearch(root->right, i);

}

  

void inorder(ITNode *root)

{

    if (root == NULL) return;

  

    inorder(root->left);

  

    cout << "[" << root->i->low << ", " << root->i->high << "]"

         << " max = " << root->max << endl;

  

    inorder(root->right);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим дерево интервалов, показанное на рисунке выше

    Interval ints[] = {{15, 20}, {10, 30}, {17, 19},

        {5, 20}, {12, 15}, {30, 40}

    };

    int n = sizeof(ints)/sizeof(ints[0]);

    ITNode *root = NULL;

    for (int i = 0; i < n; i++)

        root = insert(root, ints[i]);

  

    cout << "Inorder traversal of constructed Interval Tree is\n";

    inorder(root);

  

    Interval x = {6, 7};

  

    cout << "\nSearching for interval [" << x.low << "," << x.high << "]";

    Interval *res = overlapSearch(root, x);

    if (res == NULL)

        cout << "\nNo Overlapping Interval";

    else

        cout << "\nOverlaps with [" << res->low << ", " << res->high << "]";

    return 0;

}

Выход:

Inorder traversal of constructed Interval Tree is
[5, 20] max = 20
[10, 30] max = 30
[12, 15] max = 15
[15, 20] max = 40
[17, 19] max = 40
[30, 40] max = 40

Searching for interval [6,7]
Overlaps with [5, 20]

Приложения Interval Tree:
Дерево интервалов в основном представляет собой геометрическую структуру данных и часто используется для создания оконных запросов, например, для поиска всех дорог на компьютеризированной карте внутри прямоугольного видового экрана или для поиска всех видимых элементов в трехмерной сцене (Source Wiki ).

Дерево интервалов против дерева сегментов
Деревья сегментов и интервалов хранят интервалы. Дерево сегментов в основном оптимизировано для запросов для данной точки, а деревья интервалов в основном оптимизированы для перекрывающихся запросов для данного интервала.

Упражнение:
1) Реализовать операцию удаления для дерева интервалов.
2) Расширьте intervalSearch () для печати всех перекрывающихся интервалов вместо одного.

http://en.wikipedia.org/wiki/Interval_tree
http://www.cse.unr.edu/~mgunes/cs302/IntervalTrees.pptx
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест
https://www.youtube.com/watch?v=dQF0zyaym8A

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Интервальное дерево

0.00 (0%) 0 votes