Interval Tree

Posted on Edited on In

Source: Geeks for geeks-Interval Tree

考慮已有一 interval 集合，要對其進行以下操作

  • 新增 interval
  • 移除 interval
  • 查詢 interval x 是否與現存任意 interval 重疊

Interval tree

  • 滿足上述操作在 O(log(n)) 內完成
  • augment a self-balancing BST (Red Black Tree, AVL Tree)

每個節點儲存

  • interval: [low, high]
  • max: subtree + 節點自身的最大值

用 low 作為的排序依據，insert 和 delete 操作與 self-BST 一樣。

Query

假設 interval x 與 interval tree 內的一個 interval 發生重疊，重疊的 interval 只會在

  • 節點自身
  • 左子樹
  • 右子樹

最終演算法只會返回一個結果，因此多個重疊的情況也可限縮成只與一個 interval 發生重疊。

給定 interval x: [low, high]

現在 x

  • 不與節點自身發生重疊
  • 左子樹不存在或是 max < x.low

我們可以得出重疊的 interval 可能在右子樹的結論

1
2
3
4
5
*When we go to right subtree, one of the following must be true.*

a) There is an overlap in right subtree: This is fine as we need to return one overlapping interval.

b) There is no overlap in either subtree: We go to right subtree only when either left is NULL or maximum value in left is smaller than *x.low*. So the interval cannot be present in left subtree.

對應的實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Interval *overlapSearch(ITNode *root, Interval i)
{
    // Base Case, tree is empty
    if (root == NULL) return NULL;

    // If given interval overlaps with root
    if (doOVerlap(*(root->i), i))
        return root->i;

    // If left child of root is present and max of left child is
    // greater than or equal to given interval, then i may
    // overlap with an interval is left subtree
    if (root->left != NULL && root->left->max >= i.low)
        return overlapSearch(root->left, i);

    // Else interval can only overlap with right subtree
    return overlapSearch(root->right, i);
}

若以普通的 binary tree 進行實作，建立 n 個 interval 的最差時間複雜度為 O(n^2)，改用 self-balancing tree 可減至 O(n logn)

Other Operations

除了一般操作

  • Insertion: Add a new interval to the tree.
  • Deletion: Remove an interval from the tree.
  • Query: Find the interval in the tree that contains a given point.

和 BST 常見的操作

  • Traversal: Visit all intervals in the tree in a specific order, such as in-order, pre-order, or post-order.
  • Merge: Combine two or more interval trees into a single tree.
  • Split: Divide a tree into two or more smaller trees based on a given interval.
  • Balancing: Maintain the balance of the tree to ensure its performance is optimized.

interval tree 還有更多操作

  • Range query: Find all intervals that overlap with a given range.
  • Search: Find all intervals that overlap with a given interval.

Segment/Interval/Range/Binary Indexed Tree comparsion

Source: What are the differences between segment trees, interval trees, binary indexed trees and range trees?

  • Segment tree
    • stores intervals
    • optimized for “which of these intervals contains a given point“ queries.
  • Interval tree
    • stores intervals
    • optimized for “which of these intervals overlap with a given interval“ queries.
    • It can also be used for point queries - similar to segment tree.
  • Range tree
    • stores points
    • optimized for “which points fall within a given interval“ queries.
  • Binary indexed tree
    • stores items-count per index
    • optimized for “how many items are there between index m and n“ queries.

1 Dimension

k is the number of reported results

Operation Segment Interval Range Indexed
Preprocessing n logn n logn n logn n logn
Query k+logn k+logn k+logn logn
Space n logn n n n
Insert/Delete logn logn logn logn