2014
06-29

# 区间树

1）添加一个区间

2）删除一个区间

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

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

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

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

区间树的实现

#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]

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

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

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

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