Implement interval tree
The problem at hand is the implementation of an interval tree, a data structure that efficiently stores and handles intervals (ranges) on a number line. Interval trees are primarily used to perform range queries efficiently, such as finding overlapping intervals or intervals that contain a given point. They find applications in various fields including computational geometry, scheduling, and database systems.
Problem Statement
Given a set of intervals, the goal is to construct an interval tree that supports efficient insertion of intervals and interval search queries. A search query involves finding intervals that overlap with a given interval.
Description with Example
Imagine a scenario where you are managing appointments at a clinic. Each appointment is represented by a time interval, where the start time and end time are recorded. To efficiently manage these appointments, you can use an interval tree. Let's consider a few appointment intervals:
- Appointment 1: 22:00 - 22:30
- Appointment 2: 03:00 - 07:00
- Appointment 3: 16:00 - 28:00
- ... and so on.
The interval tree will help you manage these appointments effectively, allowing for quick insertion and retrieval of overlapping intervals.
Idea to Solve
For Example interval :
[
[22, 46],
[3, 7],
[33, 52],
[23, 45],
[16, 28],
[12, 38],
[24, 35],
[2, 26],
[35, 46]
]
The key idea in constructing an interval tree is to use a binary search tree (BST) where each node represents an interval. Additionally, each node stores the maximum endpoint value of all the intervals in its subtree. This "max" value is essential to efficiently find overlapping intervals during search operations.
Pseudocode
Structure IntervalNode:
low
high
max
left
right
Structure IntervalTree:
root
Function newNode(intervalInfo):
Create a new node
Set node's low, high, and max
Set left and right as NULL
Return the node
Function addNode(tree, intervalInfo):
Create a new node using newNode(intervalInfo)
If tree.root is NULL:
Set tree.root as the new node
Return
Initialize auxiliary as tree.root
While auxiliary is not NULL:
Update auxiliary's max if new node's max is greater
If new node's low is less than auxiliary's low:
If auxiliary's left is NULL:
Set auxiliary's left as the new node
Return
Else:
Move to auxiliary's left
Else:
If auxiliary's right is NULL:
Set auxiliary's right as the new node
Return
Else:
Move to auxiliary's right
Function preorder(node):
If node is not NULL:
Print node's interval and max
Recursively call preorder(node's left)
Recursively call preorder(node's right)
Function overlapSearch(node, low, high):
If node is NULL:
Return NULL
If node's interval overlaps with [low, high]:
Return node
If node's left is not NULL and node's left's max is greater than or equal to low:
Recursively call overlapSearch on node's left
Else:
Recursively call overlapSearch on node's right
Main:
Initialize an empty interval tree using newTree()
Create a list of interval values
For each interval in the list:
Add the interval to the interval tree using addNode
Print "Preorder" and call preorder(tree.root)
Search for overlapping intervals using overlapSearch and print the resultAlgorithm Explanation
The pseudocode provided explains the implementation of interval tree, including functions to create nodes, add nodes to the tree, perform a preorder traversal, and search for overlapping intervals.
Code Solution
// C Program
// Construct interval tree
#include <stdio.h>
#include <stdlib.h>
struct IntervalNode
{
// Interval keys
int low;
int high;
int max;
struct IntervalNode *left, *right;
};
struct IntervalTree
{
struct IntervalNode * root;
};
// Create new tree
struct IntervalTree *newTree()
{
// Create dynamic tree
struct IntervalTree *tree =
(struct IntervalTree *) malloc(sizeof(struct IntervalTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// This is creates and returns the new Interval tree Node node
struct IntervalNode *getNode(int intervalInfo[])
{
// Create dynamic node
struct IntervalNode *node =
(struct IntervalNode *) malloc(sizeof(struct IntervalNode));
if (node != NULL)
{
node->low = intervalInfo[0];
node->high = intervalInfo[1];
node->max = intervalInfo[1];
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
return node;
}
// This is creates and returns the new Interval tree Node node
void addNode(struct IntervalTree *tree, int intervalInfo[])
{
struct IntervalNode*node = getNode(intervalInfo);
if(tree->root==NULL)
{
// First node
tree->root = node;
return;
}
struct IntervalNode*auxilary = tree->root;
// Add a Interval node into tree
while(auxilary!=NULL)
{
if(auxilary->max < node->max)
{
// Change ancestor with new max value
auxilary->max = node->max;
}
if(node->low < auxilary->low)
{
if(auxilary->left==NULL)
{
// Add new node
auxilary->left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary->left;
}
}
else
{
if(auxilary->right==NULL)
{
// Add new node
auxilary->right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary->right;
}
}
}
}
// Display preorder of interval tree
void preorder(struct IntervalNode *node)
{
if (node != NULL)
{
printf("\n Interval : (%d %d) , max %d",
node->low,node->high,node->max);
// Visit left and right subtree using recursively
preorder(node->left);
preorder(node->right);
}
}
struct IntervalNode *overlapSearch(
struct IntervalNode *node, int low, int high)
{
if (node == NULL)
{
return NULL;
}
if(node->low <= high && low <= node->high )
{
// When resultant node found
return node;
}
if (node->left != NULL && node->left->max >= low)
{
return overlapSearch(node->left, low, high);
}
else
{
return overlapSearch(node->right, low, high);
}
}
int main()
{
struct IntervalTree*tree = newTree();
// Given intervals
// Note intervals pairs are sorted order
int intervalValue[][2] = {
{22, 46}, {3, 7} , {33, 52},
{23, 45}, {16,28}, {12, 38},
{24,35} , {2,26} , {35,46}
};
// Get number of nodes
int n = sizeof(intervalValue)/sizeof(intervalValue[0]);
// Add tree element
for (int i = 0; i < n; ++i)
{
addNode(tree,intervalValue[i]);
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
printf("\n \n Preorder");
preorder(tree->root);
// Search interval
int low = 10;
int high = 21;
struct IntervalNode *ans = overlapSearch(tree->root,low,high);
if(ans!=NULL)
{
printf("\n Search Interval (%d,%d) at (%d,%d)",
low,high,ans->low,ans->high);
}
else
{
printf("\n Search Interval (%d,%d) : None", low,high);
}
return 0;
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)/*
Java Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode {
// Interval keys
public int low;
public int high;
// Max of child
public int max;
public IntervalNode left;
public IntervalNode right;
public IntervalNode(int[] intervalInfo)
{
this.low = intervalInfo[0];
this.high = intervalInfo[1];
this.max = intervalInfo[1];
this.left = null;
this.right = null;
}
}
public class IntervalTree
{
public IntervalNode root;
public IntervalTree()
{
this.root = null;
}
// This is creates and returns the new Interval tree Node node
public void addNode(int[] intervalInfo)
{
IntervalNode node = new IntervalNode(intervalInfo);
if (this.root == null)
{
// First node
this.root = node;
return;
}
IntervalNode auxilary = this.root;
// Add a Interval node into tree
while (auxilary != null)
{
if (auxilary.max < node.max)
{
// Change ancestor with new max value
auxilary.max = node.max;
}
if (node.low < auxilary.low)
{
if (auxilary.left == null)
{
// Add new node
auxilary.left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary.left;
}
}
else
{
if (auxilary.right == null)
{
// Add new node
auxilary.right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary.right;
}
}
}
}
// Display preorder of interval tree
public void preorder(IntervalNode node)
{
if (node != null)
{
System.out.print("\n Interval : (" +
node.low + " " + node.high + ") , max " + node.max);
// Visit left and right subtree using recursively
preorder(node.left);
preorder(node.right);
}
}
public IntervalNode overlapSearch(IntervalNode node, int low, int high)
{
if (node == null)
{
return null;
}
if (node.low <= high && low <= node.high)
{
// When resultant node found
return node;
}
if (node.left != null && node.left.max >= low)
{
return overlapSearch(node.left, low, high);
}
else
{
return overlapSearch(node.right, low, high);
}
}
public static void main(String[] args)
{
IntervalTree tree = new IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
int[][] intervalValue = {
{
22 , 46
},{
3 , 7
},{
33 , 52
},{
23 , 45
},{
16 , 28
},{
12 , 38
},{
24 , 35
},{
2 , 26
},{
35 , 46
}
};
// Get number of nodes
int n = intervalValue.length;
// Add tree element
for (int i = 0; i < n; ++i)
{
tree.addNode(intervalValue[i]);
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
System.out.print("\n \n Preorder");
tree.preorder(tree.root);
// Search interval
int low = 10;
int high = 21;
IntervalNode ans = tree.overlapSearch(tree.root, low, high);
if (ans != null)
{
System.out.print("\n Search Interval (" + low + "," +
high + ") at (" + ans.low + "," + ans.high + ")");
}
else
{
System.out.print("\n Search Interval ("
+ low + "," + high + ") : None");
}
}
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
public:
// Interval keys
int low;
int high;
// Max of child
int max;
IntervalNode *left;
IntervalNode *right;
IntervalNode(int intervalInfo[])
{
this->low = intervalInfo[0];
this->high = intervalInfo[1];
this->max = intervalInfo[1];
this->left = NULL;
this->right = NULL;
}
};
class IntervalTree
{
public: IntervalNode *root;
IntervalTree()
{
this->root = NULL;
}
// This is creates and returns the new Interval tree Node node
void addNode(int intervalInfo[])
{
IntervalNode *node = new IntervalNode(intervalInfo);
if (this->root == NULL)
{
// First node
this->root = node;
return;
}
IntervalNode *auxilary = this->root;
// Add a Interval node into tree
while (auxilary != NULL)
{
if (auxilary->max < node->max)
{
// Change ancestor with new max value
auxilary->max = node->max;
}
if (node->low < auxilary->low)
{
if (auxilary->left == NULL)
{
// Add new node
auxilary->left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary->left;
}
}
else
{
if (auxilary->right == NULL)
{
// Add new node
auxilary->right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary->right;
}
}
}
}
// Display preorder of interval tree
void preorder(IntervalNode *node)
{
if (node != NULL)
{
cout << "\n Interval : ("
<< node->low << " "
<< node->high << ") , max "
<< node->max;
// Visit left and right subtree using recursively
this->preorder(node->left);
this->preorder(node->right);
}
}
IntervalNode *overlapSearch(IntervalNode *node, int low, int high)
{
if (node == NULL)
{
return NULL;
}
if (node->low <= high && low <= node->high)
{
// When resultant node found
return node;
}
if (node->left != NULL && node->left->max >= low)
{
return this->overlapSearch(node->left, low, high);
}
else
{
return this->overlapSearch(node->right, low, high);
}
}
};
int main()
{
IntervalTree *tree = new IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
int intervalValue[][2] = {
{
22 , 46
} , {
3 , 7
} , {
33 , 52
} , {
23 , 45
} , {
16 , 28
} , {
12 , 38
} , {
24 , 35
} , {
2 , 26
} , {
35 , 46
}
};
// Get number of nodes
int n = sizeof(intervalValue) / sizeof(intervalValue[0]);
// Add tree element
for (int i = 0; i < n; ++i)
{
tree->addNode(intervalValue[i]);
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
cout << "\n \n Preorder";
tree->preorder(tree->root);
// Search interval
int low = 10;
int high = 21;
IntervalNode *ans = tree->overlapSearch(tree->root, low, high);
if (ans != NULL)
{
cout << "\n Search Interval ("
<< low << "," << high
<< ") at ("
<< ans->low << ","
<< ans->high << ")";
}
else
{
cout << "\n Search Interval ("
<< low << ","
<< high << ") : None";
}
return 0;
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)package main
import "fmt"
/*
Go Program
Construct interval tree
*/
// Interval Tree node
type IntervalNode struct {
// Interval keys
low int
high int
// Max of child
max int
left * IntervalNode
right * IntervalNode
}
func getIntervalNode(intervalInfo [] int ) * IntervalNode {
var me *IntervalNode = &IntervalNode {}
me.low = intervalInfo[0]
me.high = intervalInfo[1]
me.max = intervalInfo[1]
me.left = nil
me.right = nil
return me
}
type IntervalTree struct {
root * IntervalNode
}
func getIntervalTree() * IntervalTree {
var me *IntervalTree = &IntervalTree {}
me.root = nil
return me
}
// This is creates and returns the new Interval tree Node node
func(this *IntervalTree) addNode(intervalInfo[] int) {
var node * IntervalNode = getIntervalNode(intervalInfo)
if this.root == nil {
// First node
this.root = node
return
}
var auxilary * IntervalNode = this.root
// Add a Interval node into tree
for (auxilary != nil) {
if auxilary.max < node.max {
// Change ancestor with new max value
auxilary.max = node.max
}
if node.low < auxilary.low {
if auxilary.left == nil {
// Add new node
auxilary.left = node
return
} else {
// Visit left subtree
auxilary = auxilary.left
}
} else {
if auxilary.right == nil {
// Add new node
auxilary.right = node
return
} else {
// Visit right subtree
auxilary = auxilary.right
}
}
}
}
// Display preorder of interval tree
func(this IntervalTree) preorder(node * IntervalNode) {
if node != nil {
fmt.Print("\n Interval : (",
node.low, " ", node.high,
") , max ", node.max)
// Visit left and right subtree using recursively
this.preorder(node.left)
this.preorder(node.right)
}
}
func(this IntervalTree) overlapSearch(node * IntervalNode, low int, high int) * IntervalNode {
if node == nil {
return nil
}
if node.low <= high && low <= node.high {
// When resultant node found
return node
}
if node.left != nil && node.left.max >= low {
return this.overlapSearch(node.left, low, high)
} else {
return this.overlapSearch(node.right, low, high)
}
}
func main() {
var tree * IntervalTree = getIntervalTree()
// Given intervals
// Note intervals pairs are sorted order
var intervalValue = [][] int {
{
22,
46,
}, {
3,
7,
}, {
33,
52,
}, {
23,
45,
}, {
16,
28,
}, {
12,
38,
}, {
24,
35,
}, {
2,
26,
}, {
35,
46,
},
}
// Get number of nodes
var n int = len(intervalValue)
// Add tree element
for i := 0 ; i < n ; i++ {
tree.addNode(intervalValue[i])
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
fmt.Print("\n \n Preorder")
tree.preorder(tree.root)
// Search interval
var low int = 10
var high int = 21
var ans * IntervalNode = tree.overlapSearch(tree.root, low, high)
if ans != nil {
fmt.Print("\n Search Interval (", low, ",", high, ") at (",
ans.low, ",", ans.high, ")")
} else {
fmt.Print("\n Search Interval (",
low, ",", high, ") : None")
}
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)// Include namespace system
using System;
/*
Csharp Program
Construct interval tree
*/
// Interval Tree node
public class IntervalNode
{
// Interval keys
public int low;
public int high;
// Max of child
public int max;
public IntervalNode left;
public IntervalNode right;
public IntervalNode(int low, int high)
{
this.low = low;
this.high = high;
this.max = high;
this.left = null;
this.right = null;
}
}
public class IntervalTree
{
public IntervalNode root;
public IntervalTree()
{
this.root = null;
}
// This is creates and returns the new Interval tree Node node
public void addNode(int low, int high)
{
IntervalNode node = new IntervalNode(low, high);
if (this.root == null)
{
// First node
this.root = node;
return;
}
IntervalNode auxilary = this.root;
// Add a Interval node into tree
while (auxilary != null)
{
if (auxilary.max < node.max)
{
// Change ancestor with new max value
auxilary.max = node.max;
}
if (node.low < auxilary.low)
{
if (auxilary.left == null)
{
// Add new node
auxilary.left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary.left;
}
}
else
{
if (auxilary.right == null)
{
// Add new node
auxilary.right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary.right;
}
}
}
}
// Display preorder of interval tree
public void preorder(IntervalNode node)
{
if (node != null)
{
Console.Write("\n Interval : (" + node.low + " " + node.high + ") , max " + node.max);
// Visit left and right subtree using recursively
this.preorder(node.left);
this.preorder(node.right);
}
}
public IntervalNode overlapSearch(IntervalNode node, int low, int high)
{
if (node == null)
{
return null;
}
if (node.low <= high && low <= node.high)
{
// When resultant node found
return node;
}
if (node.left != null && node.left.max >= low)
{
return this.overlapSearch(node.left, low, high);
}
else
{
return this.overlapSearch(node.right, low, high);
}
}
public static void Main(String[] args)
{
IntervalTree tree = new IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
int[,] intervalValue = {
{
22 , 46
},
{
3 , 7
},
{
33 , 52
},
{
23 , 45
},
{
16 , 28
},
{
12 , 38
},
{
24 , 35
},
{
2 , 26
},
{
35 , 46
}
};
// Get number of nodes
int n = intervalValue.GetLength(0);
// Add tree element
for (int i = 0; i < n; ++i)
{
tree.addNode(intervalValue[i,0],intervalValue[i,1]);
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
Console.Write("\n \n Preorder");
tree.preorder(tree.root);
// Search interval
int low = 10;
int high = 21;
IntervalNode ans = tree.overlapSearch(tree.root, low, high);
if (ans != null)
{
Console.Write("\n Search Interval (" + low + "," + high + ") at (" + ans.low + "," + ans.high + ")");
}
else
{
Console.Write("\n Search Interval (" + low + "," + high + ") : None");
}
}
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)<?php
/*
Php Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
// Interval keys
public $low;
public $high;
// Max of child
public $max;
public $left;
public $right;
public function __construct($intervalInfo)
{
$this->low = $intervalInfo[0];
$this->high = $intervalInfo[1];
$this->max = $intervalInfo[1];
$this->left = NULL;
$this->right = NULL;
}
}
class IntervalTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
// This is creates and returns the new Interval tree Node node
public function addNode($intervalInfo)
{
$node = new IntervalNode($intervalInfo);
if ($this->root == NULL)
{
// First node
$this->root = $node;
return;
}
$auxilary = $this->root;
// Add a Interval node into tree
while ($auxilary != NULL)
{
if ($auxilary->max < $node->max)
{
// Change ancestor with new max value
$auxilary->max = $node->max;
}
if ($node->low < $auxilary->low)
{
if ($auxilary->left == NULL)
{
// Add new node
$auxilary->left = $node;
return;
}
else
{
// Visit left subtree
$auxilary = $auxilary->left;
}
}
else
{
if ($auxilary->right == NULL)
{
// Add new node
$auxilary->right = $node;
return;
}
else
{
// Visit right subtree
$auxilary = $auxilary->right;
}
}
}
}
// Display preorder of interval tree
public function preorder($node)
{
if ($node != NULL)
{
echo("\n Interval : (".$node->low.
" ".$node->high.
") , max ".$node->max);
// Visit left and right subtree using recursively
$this->preorder($node->left);
$this->preorder($node->right);
}
}
public function overlapSearch($node, $low, $high)
{
if ($node == NULL)
{
return NULL;
}
if ($node->low <= $high && $low <= $node->high)
{
// When resultant node found
return $node;
}
if ($node->left != NULL && $node->left->max >= $low)
{
return $this->overlapSearch($node->left, $low, $high);
}
else
{
return $this->overlapSearch($node->right, $low, $high);
}
}
}
function main()
{
$tree = new IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
$intervalValue = array(
array(22, 46), array(3, 7),
array(33, 52), array(23, 45),
array(16, 28), array(12, 38),
array(24, 35), array(2, 26),
array(35, 46)
);
// Get number of nodes
$n = count($intervalValue);
// Add tree element
for ($i = 0; $i < $n; ++$i)
{
$tree->addNode($intervalValue[$i]);
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
echo("\n \n Preorder");
$tree->preorder($tree->root);
// Search interval
$low = 10;
$high = 21;
$ans = $tree->overlapSearch($tree->root, $low, $high);
if ($ans != NULL)
{
echo("\n Search Interval (".$low.
",".$high.
") at (".$ans->low.
",".$ans->high.
")");
}
else
{
echo("\n Search Interval (".$low.
",".$high.
") : None");
}
}
main();input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)/*
Node JS Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
constructor(intervalInfo)
{
this.low = intervalInfo[0];
this.high = intervalInfo[1];
this.max = intervalInfo[1];
this.left = null;
this.right = null;
}
}
class IntervalTree
{
constructor()
{
this.root = null;
}
// This is creates and returns the new Interval tree Node node
addNode(intervalInfo)
{
var node = new IntervalNode(intervalInfo);
if (this.root == null)
{
// First node
this.root = node;
return;
}
var auxilary = this.root;
// Add a Interval node into tree
while (auxilary != null)
{
if (auxilary.max < node.max)
{
// Change ancestor with new max value
auxilary.max = node.max;
}
if (node.low < auxilary.low)
{
if (auxilary.left == null)
{
// Add new node
auxilary.left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary.left;
}
}
else
{
if (auxilary.right == null)
{
// Add new node
auxilary.right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary.right;
}
}
}
}
// Display preorder of interval tree
preorder(node)
{
if (node != null)
{
process.stdout.write("\n Interval : (" +
node.low + " " + node.high + ") , max " +
node.max);
// Visit left and right subtree using recursively
this.preorder(node.left);
this.preorder(node.right);
}
}
overlapSearch(node, low, high)
{
if (node == null)
{
return null;
}
if (node.low <= high && low <= node.high)
{
// When resultant node found
return node;
}
if (node.left != null && node.left.max >= low)
{
return this.overlapSearch(node.left, low, high);
}
else
{
return this.overlapSearch(node.right, low, high);
}
}
}
function main()
{
var tree = new IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
var intervalValue = [
[22, 46],
[3, 7],
[33, 52],
[23, 45],
[16, 28],
[12, 38],
[24, 35],
[2, 26],
[35, 46]
];
// Get number of nodes
var n = intervalValue.length;
// Add tree element
for (var i = 0; i < n; ++i)
{
tree.addNode(intervalValue[i]);
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
process.stdout.write("\n \n Preorder");
tree.preorder(tree.root);
// Search interval
var low = 10;
var high = 21;
var ans = tree.overlapSearch(tree.root, low, high);
if (ans != null)
{
process.stdout.write("\n Search Interval (" +
low + "," + high + ") at (" + ans.low + "," + ans.high + ")");
}
else
{
process.stdout.write("\n Search Interval (" +
low + "," + high + ") : None");
}
}
main();input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)# Python 3 Program
# Construct interval tree
# Interval Tree node
class IntervalNode :
# Interval keys
# Max of child
def __init__(self, intervalInfo) :
self.low = intervalInfo[0]
self.high = intervalInfo[1]
self.max = intervalInfo[1]
self.left = None
self.right = None
class IntervalTree :
def __init__(self) :
self.root = None
# This is creates and returns the new Interval tree Node node
def addNode(self, intervalInfo) :
node = IntervalNode(intervalInfo)
if (self.root == None) :
# First node
self.root = node
return
auxilary = self.root
# Add a Interval node into tree
while (auxilary != None) :
if (auxilary.max < node.max) :
# Change ancestor with new max value
auxilary.max = node.max
if (node.low < auxilary.low) :
if (auxilary.left == None) :
# Add new node
auxilary.left = node
return
else :
# Visit left subtree
auxilary = auxilary.left
else :
if (auxilary.right == None) :
# Add new node
auxilary.right = node
return
else :
# Visit right subtree
auxilary = auxilary.right
# Display preorder of interval tree
def preorder(self, node) :
if (node != None) :
print("\n Interval : (",
node.low ," ", node.high ,") , max ",
node.max, end = "")
# Visit left and right subtree using recursively
self.preorder(node.left)
self.preorder(node.right)
def overlapSearch(self, node, low, high) :
if (node == None) :
return None
if (node.low <= high and low <= node.high) :
# When resultant node found
return node
if (node.left != None and node.left.max >= low) :
return self.overlapSearch(node.left, low, high)
else :
return self.overlapSearch(node.right, low, high)
def main() :
tree = IntervalTree()
# Given intervals
# Note intervals pairs are sorted order
intervalValue = [
[22, 46],
[3, 7],
[33, 52],
[23, 45],
[16, 28],
[12, 38],
[24, 35],
[2, 26],
[35, 46]
]
# Get number of nodes
n = len(intervalValue)
i = 0
# Add tree element
while (i < n) :
tree.addNode(intervalValue[i])
i += 1
# Max = 52
# (22, 46)
# / \
# (38)/ \ (52)
# (3, 7) (33, 52)
# / \ / \
# (26)/ \(38) /(45) \(46)
# (2,26) (16,28)(23, 45) (35,46)
# / \
# (38)/ \ (35)
# (12 38) (24,35)
# --------------------------------
# Construct Interval tree
# -------------------------------
# Preorder
# Interval : (22 46) , max 52
# Interval : (3 7) , max 38
# Interval : (2 26) , max 26
# Interval : (16 28) , max 38
# Interval : (12 38) , max 38
# Interval : (33 52) , max 52
# Interval : (23 45) , max 45
# Interval : (24 35) , max 35
# Interval : (35 46) , max 46
# -------------------------------
# Display tree elements
print("\n \n Preorder", end = "")
tree.preorder(tree.root)
# Search interval
low = 10
high = 21
ans = tree.overlapSearch(tree.root, low, high)
if (ans != None) :
print("\n Search Interval (",
low ,",", high ,") at (",
ans.low ,",", ans.high ,")", end = "")
else :
print("\n Search Interval (",
low ,",", high ,") : None", end = "")
if __name__ == "__main__": main()input
Preorder
Interval : ( 22 46 ) , max 52
Interval : ( 3 7 ) , max 38
Interval : ( 2 26 ) , max 26
Interval : ( 16 28 ) , max 38
Interval : ( 12 38 ) , max 38
Interval : ( 33 52 ) , max 52
Interval : ( 23 45 ) , max 45
Interval : ( 24 35 ) , max 35
Interval : ( 35 46 ) , max 46
Search Interval ( 10 , 21 ) at ( 2 , 26 )# Ruby Program
# Construct interval tree
# Interval Tree node
class IntervalNode
# Define the accessor and reader of class IntervalNode
attr_reader :low, :high, :max, :left, :right
attr_accessor :low, :high, :max, :left, :right
# Interval keys
# Max of child
def initialize(intervalInfo)
self.low = intervalInfo[0]
self.high = intervalInfo[1]
self.max = intervalInfo[1]
self.left = nil
self.right = nil
end
end
class IntervalTree
# Define the accessor and reader of class IntervalTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# This is creates and returns the new Interval tree Node node
def addNode(intervalInfo)
node = IntervalNode.new(intervalInfo)
if (self.root == nil)
# First node
self.root = node
return
end
auxilary = self.root
# Add a Interval node into tree
while (auxilary != nil)
if (auxilary.max < node.max)
# Change ancestor with new max value
auxilary.max = node.max
end
if (node.low < auxilary.low)
if (auxilary.left == nil)
# Add new node
auxilary.left = node
return
else
# Visit left subtree
auxilary = auxilary.left
end
else
if (auxilary.right == nil)
# Add new node
auxilary.right = node
return
else
# Visit right subtree
auxilary = auxilary.right
end
end
end
end
# Display preorder of interval tree
def preorder(node)
if (node != nil)
print("\n Interval : (",
node.low ," ", node.high ,") , max ", node.max)
# Visit left and right subtree using recursively
self.preorder(node.left)
self.preorder(node.right)
end
end
def overlapSearch(node, low, high)
if (node == nil)
return nil
end
if (node.low <= high && low <= node.high)
# When resultant node found
return node
end
if (node.left != nil && node.left.max >= low)
return self.overlapSearch(node.left, low, high)
else
return self.overlapSearch(node.right, low, high)
end
end
end
def main()
tree = IntervalTree.new()
# Given intervals
# Note intervals pairs are sorted order
intervalValue = [
[22, 46],
[3, 7],
[33, 52],
[23, 45],
[16, 28],
[12, 38],
[24, 35],
[2, 26],
[35, 46]
]
# Get number of nodes
n = intervalValue.length
i = 0
# Add tree element
while (i < n)
tree.addNode(intervalValue[i])
i += 1
end
# Max = 52
# (22, 46)
# / \
# (38)/ \ (52)
# (3, 7) (33, 52)
# / \ / \
# (26)/ \(38) /(45) \(46)
# (2,26) (16,28)(23, 45) (35,46)
# / \
# (38)/ \ (35)
# (12 38) (24,35)
# --------------------------------
# Construct Interval tree
# -------------------------------
# Preorder
# Interval : (22 46) , max 52
# Interval : (3 7) , max 38
# Interval : (2 26) , max 26
# Interval : (16 28) , max 38
# Interval : (12 38) , max 38
# Interval : (33 52) , max 52
# Interval : (23 45) , max 45
# Interval : (24 35) , max 35
# Interval : (35 46) , max 46
# -------------------------------
# Display tree elements
print("\n \n Preorder")
tree.preorder(tree.root)
# Search interval
low = 10
high = 21
ans = tree.overlapSearch(tree.root, low, high)
if (ans != nil)
print("\n Search Interval (",
low ,",", high ,") at (", ans.low ,",", ans.high ,")")
else
print("\n Search Interval (",
low ,",", high ,") : None")
end
end
main()input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)/*
Scala Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode(
// Interval keys
var low: Int,
var high: Int,
// Max of child
var max: Int,
var left: IntervalNode,
var right: IntervalNode)
{
def this(intervalInfo: Array[Int])
{
this(intervalInfo(0),intervalInfo(1),intervalInfo(1), null,null);
}
}
class IntervalTree(var root: IntervalNode)
{
def this()
{
this(null);
}
// This is creates and returns the new Interval tree Node node
def addNode(intervalInfo: Array[Int]): Unit = {
var node: IntervalNode = new IntervalNode(intervalInfo);
if (this.root == null)
{
// First node
this.root = node;
return;
}
var auxilary: IntervalNode = this.root;
// Add a Interval node into tree
while (auxilary != null)
{
if (auxilary.max < node.max)
{
// Change ancestor with new max value
auxilary.max = node.max;
}
if (node.low < auxilary.low)
{
if (auxilary.left == null)
{
// Add new node
auxilary.left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary.left;
}
}
else
{
if (auxilary.right == null)
{
// Add new node
auxilary.right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary.right;
}
}
}
}
// Display preorder of interval tree
def preorder(node: IntervalNode): Unit = {
if (node != null)
{
print("\n Interval : (" +
node.low + " " + node.high + ") , max " + node.max);
// Visit left and right subtree using recursively
preorder(node.left);
preorder(node.right);
}
}
def overlapSearch(node: IntervalNode,
low: Int,
high: Int): IntervalNode = {
if (node == null)
{
return null;
}
if (node.low <= high && low <= node.high)
{
// When resultant node found
return node;
}
if (node.left != null && node.left.max >= low)
{
return overlapSearch(node.left, low, high);
}
else
{
return overlapSearch(node.right, low, high);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: IntervalTree = new IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
var intervalValue: Array[Array[Int]] =
Array(
Array(22, 46),
Array(3, 7),
Array(33, 52),
Array(23, 45),
Array(16, 28),
Array(12, 38),
Array(24, 35),
Array(2, 26),
Array(35, 46)
);
// Get number of nodes
var n: Int = intervalValue.length;
var i: Int = 0;
// Add tree element
while (i < n)
{
tree.addNode(intervalValue(i));
i += 1;
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
print("\n \n Preorder");
tree.preorder(tree.root);
// Search interval
var low: Int = 10;
var high: Int = 21;
var ans: IntervalNode = tree.overlapSearch(tree.root, low, high);
if (ans != null)
{
print("\n Search Interval (" + low + "," + high + ") at (" + ans.low + "," + ans.high + ")");
}
else
{
print("\n Search Interval (" + low + "," + high + ") : None");
}
}
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)import Foundation;
/*
Swift 4 Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
// Interval keys
var low: Int;
var high: Int;
// Max of child
var max: Int;
var left: IntervalNode? ;
var right: IntervalNode? ;
init(_ intervalInfo: [Int])
{
self.low = intervalInfo[0];
self.high = intervalInfo[1];
self.max = intervalInfo[1];
self.left = nil;
self.right = nil;
}
}
class IntervalTree
{
var root: IntervalNode? ;
init()
{
self.root = nil;
}
// This is creates and returns the new Interval tree Node node
func addNode(_ intervalInfo: [Int])
{
let node = IntervalNode(intervalInfo);
if (self.root == nil)
{
// First node
self.root = node;
return;
}
var auxilary = self.root;
// Add a Interval node into tree
while (auxilary != nil)
{
if (auxilary!.max < node.max)
{
// Change ancestor with new max value
auxilary!.max = node.max;
}
if (node.low < auxilary!.low)
{
if (auxilary!.left == nil)
{
// Add new node
auxilary!.left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary!.left;
}
}
else
{
if (auxilary!.right == nil)
{
// Add new node
auxilary!.right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary!.right;
}
}
}
}
// Display preorder of interval tree
func preorder(_ node: IntervalNode? )
{
if (node != nil)
{
print("\n Interval : (",
node!.low ," ", node!.high ,") , max ",
node!.max, terminator: "");
// Visit left and right subtree using recursively
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func overlapSearch(_ node: IntervalNode? ,
_ low : Int, _ high: Int) -> IntervalNode?
{
if (node == nil)
{
return nil;
}
if (node!.low <= high && low <= node!.high)
{
// When resultant node found
return node;
}
if (node!.left != nil && node!.left!.max >= low)
{
return self.overlapSearch(node!.left, low, high);
}
else
{
return self.overlapSearch(node!.right, low, high);
}
}
}
func main()
{
let tree = IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
let intervalValue = [
[22, 46],
[3, 7],
[33, 52],
[23, 45],
[16, 28],
[12, 38],
[24, 35],
[2, 26],
[35, 46]
];
// Get number of nodes
let n = intervalValue.count;
var i = 0;
// Add tree element
while (i < n)
{
tree.addNode(intervalValue[i]);
i += 1;
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
print("\n \n Preorder", terminator: "");
tree.preorder(tree.root);
// Search interval
let low = 10;
let high = 21;
let ans = tree.overlapSearch(tree.root, low, high);
if (ans != nil)
{
print("\n Search Interval (",
low ,",", high ,") at (",
ans!.low ,",", ans!.high ,")",
terminator: "");
}
else
{
print("\n Search Interval (",
low ,",", high ,") : None",
terminator: "");
}
}
main();input
Preorder
Interval : ( 22 46 ) , max 52
Interval : ( 3 7 ) , max 38
Interval : ( 2 26 ) , max 26
Interval : ( 16 28 ) , max 38
Interval : ( 12 38 ) , max 38
Interval : ( 33 52 ) , max 52
Interval : ( 23 45 ) , max 45
Interval : ( 24 35 ) , max 35
Interval : ( 35 46 ) , max 46
Search Interval ( 10 , 21 ) at ( 2 , 26 )/*
Kotlin Program
Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
// Interval keys
var low: Int;
var high: Int;
// Max of child
var max: Int;
var left: IntervalNode ? ;
var right: IntervalNode ? ;
constructor(intervalInfo: Array < Int > )
{
this.low = intervalInfo[0];
this.high = intervalInfo[1];
this.max = intervalInfo[1];
this.left = null;
this.right = null;
}
}
class IntervalTree
{
var root: IntervalNode ? ;
constructor()
{
this.root = null;
}
// This is creates and returns the new Interval tree Node node
fun addNode(intervalInfo: Array < Int > ): Unit
{
val node: IntervalNode = IntervalNode(intervalInfo);
if (this.root == null)
{
// First node
this.root = node;
return;
}
var auxilary: IntervalNode ? = this.root;
// Add a Interval node into tree
while (auxilary != null)
{
if (auxilary.max < node.max)
{
// Change ancestor with new max value
auxilary.max = node.max;
}
if (node.low < auxilary.low)
{
if (auxilary.left == null)
{
// Add new node
auxilary.left = node;
return;
}
else
{
// Visit left subtree
auxilary = auxilary.left;
}
}
else
{
if (auxilary.right == null)
{
// Add new node
auxilary.right = node;
return;
}
else
{
// Visit right subtree
auxilary = auxilary.right;
}
}
}
}
// Display preorder of interval tree
fun preorder(node: IntervalNode ? ): Unit
{
if (node != null)
{
print("\n Interval : (" +
node.low + " " + node.high + ") , max " + node.max);
// Visit left and right subtree using recursively
this.preorder(node.left);
this.preorder(node.right);
}
}
fun overlapSearch(node: IntervalNode ? , low : Int, high: Int): IntervalNode ?
{
if (node == null)
{
return null;
}
if (node.low <= high && low <= node.high)
{
// When resultant node found
return node;
}
if (node.left != null && node.left!!.max >= low)
{
return this.overlapSearch(node.left, low, high);
}
else
{
return this.overlapSearch(node.right, low, high);
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: IntervalTree = IntervalTree();
// Given intervals
// Note intervals pairs are sorted order
val intervalValue: Array < Array < Int >> =
arrayOf(
arrayOf(22, 46),
arrayOf(3, 7),
arrayOf(33, 52),
arrayOf(23, 45),
arrayOf(16, 28),
arrayOf(12, 38),
arrayOf(24, 35),
arrayOf(2, 26),
arrayOf(35, 46)
);
// Get number of nodes
val n: Int = intervalValue.count();
var i: Int = 0;
// Add tree element
while (i < n)
{
tree.addNode(intervalValue[i]);
i += 1;
}
/*
Max = 52
(22, 46)
/ \
(38)/ \ (52)
(3, 7) (33, 52)
/ \ / \
(26)/ \(38) /(45) \(46)
(2,26) (16,28)(23, 45) (35,46)
/ \
(38)/ \ (35)
(12 38) (24,35)
--------------------------------
Construct Interval tree
-------------------------------
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
-------------------------------
*/
// Display tree elements
print("\n \n Preorder");
tree.preorder(tree.root);
// Search interval
val low: Int = 10;
val high: Int = 21;
val ans: IntervalNode? = tree.overlapSearch(tree.root, low, high);
if (ans != null)
{
print("\n Search Interval (" +
low + "," + high + ") at (" +
ans.low + "," + ans.high + ")");
}
else
{
print("\n Search Interval (" + low + "," + high + ") : None");
}
}input
Preorder
Interval : (22 46) , max 52
Interval : (3 7) , max 38
Interval : (2 26) , max 26
Interval : (16 28) , max 38
Interval : (12 38) , max 38
Interval : (33 52) , max 52
Interval : (23 45) , max 45
Interval : (24 35) , max 35
Interval : (35 46) , max 46
Search Interval (10,21) at (2,26)Time Complexity
- Insertion of a node takes O(log n) time on average, where n is the number of nodes in the tree.
- Search for overlapping intervals takes O(log n) time on average, with a worst-case time complexity of O(n) if the tree is highly unbalanced.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment