Интервальная Деревья
Я написал программу JAVA для интервальных деревьев в одном измерении. Но отладчик показывает ошибку. Не могу понять это. Пожалуйста помоги!
Я создал 3 класса. Первый класс SegmentNode содержит данные, которые должны храниться в каждом узле дерева. Второй класс SegmentTree выполняет различные функции, такие как создание, поиск запросов, обновление. Третий класс SegmentTreeHandler читает текстовый файл и вызывает различные функции второго класса. Текстовый файл содержит числа, которые представляют сегменты на оси X. Согласно программе файл должен содержать числа, разделенные одним пробелом и заканчивающийся переводом строки.
// The class SegmentNode contains the various properties of the nodes of a tree
class SegmentNode
{
protected int nodeValue;// member variable to store the data contained in the node
// Default constructor to initialize the member variables with default values
SegmentNode()
{
setNodeValue(0);
}
// public function to assign value to the node
protected void setValue(int Value)
{
setNodeValue(Value);
}
/**
* @return the nodeValue
*/
int getNodeValue() {
return nodeValue;
}
/**
* @param nodeValue the nodeValue to set
*/
public void setNodeValue(int Value) {
nodeValue = Value;
}
}
class SegmentTree
{
//function get the mid value from the corner indexes
private static int getMid(int start, int end)
{
return (start+(end-start)/2);
}
// A recursive function to get the sum of values in given query range
private static int getSum(SegmentNode arr[],int segmentStart, int segmentEnd, int queryStart, int queryEnd, int index)
{
// If segment of this node is a part of given range, then return the sum of the segment
if(queryStart<=segmentStart&&queryEnd>=segmentEnd)
return (int)arr[index].getNodeValue();
// If segment of this node is outside the given range then return zero
if(segmentEnd<queryStart|| segmentStart>queryEnd)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(segmentStart,segmentEnd);
return getSum(arr,segmentStart,mid,queryStart,queryEnd,(2*index+1)) + getSum(arr,(mid+1),segmentEnd,queryStart,queryEnd,(2*index+2));
}
//A recursive function to update the nodes which have the given index in their range
private static void updateValue(SegmentNode arr[], int segmentStart, int segmentEnd, int i, int diff, int index)
{
// Base Case: If the input index lies outside the range of this segment
if (i < segmentStart || i > segmentEnd)
return;
// If the input index is in range of this node, then update the value of the node and its children
arr[index].setNodeValue(arr[index].getNodeValue() + diff);
if (segmentEnd != segmentStart)
{
int mid = getMid(segmentStart, segmentEnd);
updateValue(arr, segmentStart, mid, i, diff, 2*index + 1);
updateValue(arr, mid+1, segmentEnd, i, diff, 2*index + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValue() to update the value in segment tree
protected static void updateSegmentValue(int segArray[], SegmentNode arr[], int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n-1)
{
System.out.println("\nInvalid Input");
return;
}
// Get the difference between new value and old value
int diff = new_val - segArray[i];
// Update the value in array
segArray[i] = new_val;
// Update the values of nodes in segment tree
updateValue(arr, 0, n-1, i, diff, 0);
}
// Return sum of elements in range from index queryStart to queryEnd. It mainly uses getSum()
protected static int getSegmentSum(SegmentNode arr[], int n, int queryStart, int queryEnd)
{
// Check for erroneous input values
if (queryStart < 0 || queryEnd > n-1 || queryStart > queryEnd)
{
System.out.println("\nInvalid Input");
return -1;
}
return getSum(arr, 0, n-1, queryStart, queryEnd, 0);
}
// A recursive function that constructs Segment Tree for array[segmentStart..segmentEnd].
// segmentIndex is index of current node in segment tree segArray
private static int constructSegmentTree(int segArray[], int segmentStart, int segmentEnd, SegmentNode arr[], int segmentIndex)
{
// If there is one element in array, store it in current node of segment tree and return
if(segmentStart==segmentEnd)
{
**arr[segmentIndex].setValue(segArray[segmentStart]);**
return segArray[segmentStart];
}
else
{
// If there are more than one elements, then recur for left and right subtrees and store the sum of values in this node
int mid = getMid(segmentStart, segmentEnd);
**arr[segmentIndex].setNodeValue(constructSegmentTree(segArray, segmentStart, mid, arr, segmentIndex*2+1) + constructSegmentTree(segArray, mid+1, segmentEnd, arr, segmentIndex*2+2));**
return arr[segmentIndex].getNodeValue();
}
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSegmentTree() to
fill the allocated memory */
protected static void constructST(SegmentNode tree[],int segtreeArray[], int n)
{
// Fill the allocated memory arr
**constructSegmentTree(segtreeArray, 0, n-1, tree, 0);**
return;
}
}
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class SegmentTreeHandler
{
public static void main(String args[])throws IOException
{
// To accept filename
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// To input the segments from the file
BufferedReader reader = null;
// to store the numbers in an integer array
int segmentArray[];
String line= null,filename="";
System.out.print("\n Enter filename with path : ");
filename= br.readLine();
// try catch block to handle FileNotFound exceptions
try
{
reader= new BufferedReader(new FileReader(filename));
}
catch(FileNotFoundException e)
{
System.out.println("\n File Not Found");
System.exit(0);
}
// try catch block to handle NullPointerExceptions
try
{
line=reader.readLine();
}
catch(IOException e)
{
System.out.println("\n Empty File");
System.exit(0);
}
String[] parts = line.split(" ");// splitting the string read from the file into parts divided by spaces
segmentArray=new int[parts.length];// creating an segment array based on the number of parts
for(int i=0;i<parts.length;segmentArray[i]=Integer.parseInt(parts[i]),i++);
// storing the numbers read from the file in the segment array as integers
int sizeOfArray = parts.length;
int x = (int)(Math.ceil(Math.log10(sizeOfArray*1.0)/Math.log10(2.0))); //Height of segment tree
int max_size = 2*(int)Math.pow(2, x) - 1; //Maximum size of segment tree
SegmentNode segmentTree[]= new SegmentNode[max_size];
**SegmentTree.constructST(segmentTree,segmentArray,sizeOfArray);**
for(int i =0; i< parts.length;i++)
{
System.out.print(segmentTree[i].getNodeValue()+ " ");
}
System.out.println("\n -----Query Search-----");
// taking the window for query as input
System.out.print("\n Enter query start index : ");
int qStart = Integer.parseInt(br.readLine());
System.out.print("\n Enter query end index : ");
int qEnd = Integer.parseInt(br.readLine());
System.out.print("\n Sum of the values in the given query window : " + SegmentTree.getSegmentSum(segmentTree, parts.length, qStart, qEnd));
System.out.println("\n -----Update Value-----");
// updating an interval value
System.out.print("\n Enter the update position : ");
int updatePos = Integer.parseInt(br.readLine());
System.out.print("\n Enter the new value : ");
int newValue = Integer.parseInt(br.readLine());
SegmentTree.updateSegmentValue(segmentArray, segmentTree, parts.length, updatePos, newValue);
System.out.println("\n Specified value updated");
System.out.println("\n -----Query Search-----");
// taking the window for query as input
System.out.print("\n Enter query start index : ");
qStart = Integer.parseInt(br.readLine());
System.out.print("\n Enter query end index : ");
qEnd = Integer.parseInt(br.readLine());
System.out.print("\n Sum of the values in the given query window : " + SegmentTree.getSegmentSum(segmentTree, parts.length, qStart, qEnd));
// try catch block to handle exceptions generated during closing of file stream
try
{
reader.close();
}
catch (IOException e)
{
System.out.println("\n File stream closing failed ");
System.exit(0);
}
finally
{
System.out.println("\n Thank you! have a nice day :)");
}
}
}
Отладчик показывает: Thread [main] (Suspended)
SegmentTree.constructSegmentTree(int[], int, int, SegmentNode[], int) line: 83
SegmentTree.constructSegmentTree(int[], int, int, SegmentNode[], int) line: 93
SegmentTree.constructSegmentTree(int[], int, int, SegmentNode[], int) line: 93
SegmentTree.constructSegmentTree(int[], int, int, SegmentNode[], int) line: 93
SegmentTree.constructST(SegmentNode[], int[], int) line: 107
SegmentTreeHandler.main(String[]) line: 54
Я не могу понять, что это за ошибки.