Andrés Bustamante Andrés Bustamante - 23 days ago 7
Java Question

RTrees for dummies

I want to complety understand two dimension RTrees on Java but i get lost in explanations, and I hope someone can tell me how they really work.

What i get about them is this:

You start with a list of nodes with a maximum number of entrys M, when you try to get one more value you have to split this node, I have to keep a root node with two leaves. I don't want to discuss about the best split method, we are thinking in a trully simple RTree.

Now Im going to write a basic code of how i think it works:

class RTree<E> {

//I need a root which is a list of nodes.
public NodeList root;

//From data we create rectangles that contain values
class Rectangle {
public double x;
public double y;
}

class Node {
public E valor;
public Rectangle rect;
}

class ListNodo {
public Node node;
public NodeList next;
}
}


What I don't get (Sorry if this is so basic):

Do I have to ask the user to entry values in coordinates?

How will work the insertion method for a basic case, which parameters will i ask?

Am I getting all wrong?

Answer

The rectangles in a 2-D R-tree are bounding boxes. They need four coordinates, for example left, right, top, and bottom as OleV says, not just x and y.

A non-leaf node in the tree contains a number of entries, each having a bounding box and a link to another tree node in the next level down. The bounding box of the entry contains the bounding boxes of all entries in the node below.

A leaf node is similar, but each entry has a bounding box and a link to a data object, which is not part of the tree. The bounding box contains the data object.

We have to have a way to find the bounding box of an object. To insert an object, figure out its bounding box and make up a leaf entry. Then, start at the root and go down toward the leaves. At each level above the leaves, choose a subtree for the new object by comparing its bounding box with the bounding boxes of the entries. Pick a subtree whose data items are close to the new object.

When you reach the leaf level, add the new entry to that node. You might have to split the node if there are too many entries.

On the way down, you might need to enlarge bounding boxes in non-leaf entries to contain the new entry.