2014
06-29

考虑这样一个情况,我们有一个区间的集合,我们需有效地实现以下的操作。

1)添加一个区间

2)删除一个区间

3)给定一个区间x,查询x 是否和已存在的区间存在重合。

区间树

区间树是在红黑树基础上进行扩展得到的支持以区间为元素的动态集合的操作,其中每个节点的关键值是区间的左端点。通过建立这种特定的结构,可是使区间的元素的查找和插入都可以在O(lgn)的时间内完成。相比于基础的数据结构,增加了一个max[x],即以x为根的子树中所有区间的断点的最大值。区间树如下图所示:

IntervalSearcTree

区间树的每个节点存储以下信息:

1) 一个表示为 [low, high] 的区间

2) 当前节点的子树的最大值。

区间查找

这里的区间查找的并不是精确查找,而是查找和给定区间重叠的元素,重叠的定义如下图所示:

实现INTERVAL-SEARCH(T, i),返回一个和区间i重叠的区间,若无,则返回nil[T]。基本思想是我们通过左子树的max进行划分:如果左子树的max值小于low[i],则左子树不存在这样的区间和i重叠,转到右子树;否则,转到右子树,因为左子树的端点小于右子树,若左子树无可能,右子树也必然不可能。

INTERVAL-SEARCH(T, i)整个过程如下:

INTERVAL-SEARCH(T, i)
x ← root[T]
while x≠nil[T] and i does not overlap x
   do if left[x]≠nil[T] and max[left[x]]≥low[i]
         then x ← left[x]
         else x ← right[x]
return x

 区间树的实现

下面是C++的实现,为了简单,使用的是普通二分查找树的算法,实际上应该用AVL树或红黑树来实现。但是基本原理是一样的,只是性能有所差别。

#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;
};

// 插入区间
ITNode *insert(ITNode *root, Interval i)
{
    if (root == NULL)
        return newNode(i);
    // 获得当前节点的low
    int l = root->i->low;
    if (i.low < l)
        root->left = insert(root->left, i);
    else
        root->right = insert(root->right, i);
    // 重要:更新max
    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;
}

// 找一个重叠区间(可能有多个,只找到一个,优先找左子树的)
Interval *intervalSearch(ITNode *root, Interval i)
{
    // 基本情况,树是空的
    if (root == NULL) return NULL;

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

    //左子树会有一个重叠区间
    if (root->left != NULL && root->left->max >= i.low)
        return intervalSearch(root->left, i);

    // 否则,只可能出现在又子树
    return intervalSearch(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 = intervalSearch(root, x);
    if (res == NULL)
        cout << "\nNo Overlapping Interval";
    else
        cout << "\nOverlaps with [" << res->low << ", " << res->high << "]";
}

输出:

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]

区间树主要是用于几何数据结构和常用窗口查询,例如,电脑地图上找到在一个矩形窗口中的所有道路,或找到一个三维场景中的所有可见的元素。

区间树与线段树

点击这里线段树简介。两种树都存储区间,只是另外附加的信息不同。线段树主要是查询优化对于给定的点,和区间树主要是优化查询区间的重叠对于一个给定的区间。

参考:http://www.geeksforgeeks.org/interval-tree/


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。