傻瓜 RTrees

Question

我想完全理解 Java 上的二维 RTree，但我在解释中迷路了，我希望有人能告诉我它们是如何工作的。

我对他们的了解是这样的：

你从一个最大条目数为 M 的节点列表开始，当你试图获得更多的值时你必须拆分这个节点，我必须保留一个有两个叶子的根节点。我不想讨论最好的拆分方法，我们正在考虑一个非常简单的 RTree。

现在我要编写我认为它如何工作的基本代码：

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;
     }
}

我不明白的（对不起，如果这太基础了）：

我是否必须要求用户输入坐标值？

基本案例的插入方法如何工作，我会问哪些参数？

我是不是都错了？

Answer 1

二维 R 树中的矩形是边界框。他们需要四个坐标，例如 OleV 所说的左、右、上和下，而不仅仅是 x 和 y。

树中的一个非叶节点包含许多条目，每个条目都有一个边界框和一个 link 到下一级中的另一个树节点。条目的边界框包含下面节点中所有条目的边界框。

叶节点类似，但每个条目都有一个边界框和一个 link 到数据对象，这不是树的一部分。边界框包含数据对象。

我们必须有办法找到对象的边界框。要插入一个对象，找出它的边界框并组成一个叶条目。然后，从根部开始，向下延伸至叶子。在叶子上方的每个级别，通过将其边界框与条目的边界框进行比较，为新对象选择一个子树。选择一棵数据项接近新对象的子树。

到达叶级时，将新条目添加到该节点。如果条目太多，您可能需要拆分节点。

在下降的过程中，您可能需要扩大非叶条目中的边界框以包含新条目。

傻瓜 RTrees

RTrees for dummies

java

algorithm

r-tree