四叉树

Question

我正在实现一个四叉树。对于那些不知道这个数据结构的人，我包括以下的小描述：

四叉树是一种数据结构，在欧几里德平面上就像八叉树在三维空间中一样。四叉树的一个常见用途是空间索引。总结一下它们是如何工作的，四叉树是一个集合--比如这里的矩形--具有最大的容量和一个初始的边界框。当试图将一个元素插入到达到其最大容量的四叉树中时，该四叉树被细分为4棵四叉树(其几何表示比插入前的树小4倍)；每个元素根据其位置在子树中重新分布。处理矩形时左上角的范围。因此，一棵四叉树要么是一片叶子，它的元素比它的容量还少，要么是一棵有4棵儿童树的树(通常是西北、东北、西南、东南)。

我关心的是，如果你试图添加重复，可能是相同的元素几次或几个不同的元素与相同的位置，四叉树有一个基本的问题，处理边。

例如，如果您使用容量为1的四叉树并将单位矩形用作边框：

[(0,0),(0,1),(1,1),(1,0)]

然后尝试插入两次矩形，其左上角是原点：(或者，类似地，如果尝试将其插入N+1次，则插入容量为N>1的四叉树)。

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

第一个插入将不是一个问题：

但是，第一个插入将触发一个细分(因为容量为1)：

因此，两个矩形都放在同一个子树中。

然后，这两个元素将到达同一个四叉树，并触发子域…

以此类推，细分方法将无限期地运行，因为(0，0)总是在所创建的四个子树中的同一个子树中，这意味着出现了无限递归问题。

有没有可能有一个有重复的四叉树？(如果不是，您可以将其实现为Set)

我们如何在不完全破坏四叉树体系结构的情况下解决这个问题？

Answer 1

您正在实现一个数据结构，因此您必须做出实现决策。

除非四叉树对唯一性有明确的说明--我不知道它有--这是一个实现决定。它与四叉树的定义是正交的，您可以选择任意处理它。该四叉树告诉您如何插入和更新键，而不是它们是否必须是唯一的，或者可以附加到每个节点的内容。

做出实现决策并不是在重新创造方向盘，至少仅仅是从一开始就编写自己的实现。

作为比较，C++标准库提供了一个唯一的集合、一个非唯一的多集、一个唯一的映射(本质上是一组按键排序和比较的键值对)和一个非唯一的多个集合。它们都是使用相同的红黑树实现的，没有一个是破坏体系结构的，仅仅是因为红黑树的定义对于键的唯一性或存储在叶节点中的类型没有什么可说的。

最后，如果你认为有这方面的研究，找到它，然后我们可以讨论它。也许有一些四叉树不变量我忽略了，或者一些额外的约束，允许更好的性能。

Answer 2

我假设您正在索引大小大致相同的元素，否则生活会变得复杂、缓慢，或者两者都是……。

四叉树节点不需要有固定的容量。容量是用来

• 允许每个树节点在内存或磁盘上固定大小--如果树节点包含可变大小的元素集，并且您使用的是处理空间分配系统，则不需要树节点。(例如内存中的java/c#对象)
• 决定何时拆分节点。
  • 您只需重新定义规则，以便如果节点包含的“n”区元素多于“n”区元素，则该节点将被拆分，其中区域是根据元素的位置定义的。
  • 或者使用“复合元素”，因此，如果在同一位置存在多个元素，则需要引入一个新元素，该元素包含这些多个元素的列表。

Answer 3

我认为这里有一种误解。

据我所知，每个四叉树节点都包含一个按点索引的值。换句话说，它包含三元组(x，y，value)。

它还包含指向子节点的4个指针，可能为null。在密钥和子链接之间有一个算法关系。

你的插入件应该是这样的。

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

第一个insert创建一个(父)节点并将一个值插入其中。

第二个insert创建一个子节点，链接到该节点，并将一个值插入其中(该值可能恰好与第一个值相同)。

实例化哪个子节点取决于算法。如果算法的形式为[x]，坐标空间位于[0，1]范围内，则每个子节点将跨越范围[0,0.5)，并将该点放置在NW子节点中。

我没有看到无限递归。