java - 傻瓜 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。

树中的一个非叶节点包含许多条目，每个条目都有一个边界框和一个指向下一层中另一个树节点的链接。条目的边界框包含下面节点中所有条目的边界框。

叶节点类似，但每个条目都有一个边界框和一个指向数据对象的链接，它不是树的一部分。边界框包含数据对象。

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

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

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