数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 程序实现区间树
区间树是一种有序树数据结构，用于保存区间。它特别允许有效地查找与任何给定区间或点重叠的所有区间。这里有一个 C++ 程序来实现区间树。
算法
Begin function insert() is used to insert new nodes into the tree: If Tree is empty, new node becomes root. Get low value of interval at root. If root's low value is smaller, then new interval goes to left subtree. Else, new node goes to right subtree. If needed, update the max value of this ancestor. End Begin function intervalFind() searches a given interval i in a given interval Tree: If tree is empty return null. If given interval overlaps with root 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 Else interval can only overlap with right subtree. End
示例代码
#include <iostream>
using namespace std;
struct Interval//interval variables declaration {
int l, h;
};
struct ITNod//node declaration {
Interval *i;
int max;
ITNod *l, *r;
};
ITNod * newNode(Interval i)//to create new node {
ITNod *t = new ITNod;
t->i = new Interval(i);
t->max = i.h;
t->l = t->r = NULL;
};
ITNod *insert(ITNod *r, Interval i) {
if (r== NULL)
return newNode(i);
int l = r->i->l;
if (i.l< l)
r->l = insert(r->l, i);
else
r->r = insert(r->r, i);
if (r->max < i.h)
r->max = i.h;
return r;
}
bool Overlap(Interval i1, Interval i2)// check if two intervals overlap or not. {
if (i1.l <= i2.h && i2.l<= i1.h)
return true;
return false;
}
Interval *intervalFind(ITNod *root, Interval i) {
if (root == NULL)
return NULL;
if (Overlap(*(root->i), i))
return root->i;
if (root->l!= NULL && root->l->max >= i.l)
return intervalFind(root->l, i);
return intervalFind(root->r, i);
}
void inorder(ITNod *root)//perform inorder traversal {
if (root == NULL)
return;
inorder(root->l);
cout << "[" << root->i->l<< ", " << root->i->h << "]" << " max = "<< root->max << endl;
inorder(root->r);
}
int main(int argc, char **argv) {
Interval ints[] = { { 5, 20 }, { 6, 7 }, { 3, 4 }, { 67, 26 }, { 3, 4 } };
int n = sizeof(ints) / sizeof(ints[0]);
ITNod *root = NULL;
for (int i = 0; i < n; i++)
root = insert(root, ints[i]);
cout << "In-order traversal of the constructed Interval Tree is\n";
inorder(root);
Interval x = { 7, 6 };
cout << "\nSearching for interval [" << x.l << "," << x.h << "]";
Interval *res = intervalFind(root, x);
if (res == NULL)
cout << "\nNo Overlapping Interval";
else
cout << "\nOverlaps with [" << res->l << ", " << res->h << "]";
}输出
In-order traversal of the constructed Interval Tree is [3, 4] max = 4 [3, 4] max = 4 [5, 20] max = 26 [6, 7] max = 26 [67, 26] max = 26 Searching for interval [7,6] Overlaps with [5, 20]
更新日期：2019 年 7 月 30 日
690 次浏览
广告