인터벌 트리를 구현하는 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]