四叉树等价于 AVL 树
Quadtree equivalent of AVL tree
我正在寻找一棵 quadtree/octree/2^n 树，当它接受新的观察时会自我平衡，而无需了解其他所有点，iow，它不能依赖中位数，因为我正在写 'streaming'上下文。 AVL树通过旋转来平衡，是否有另一种类似的数据结构用于更高维度的数据？
AVL树，returns只有一个结果，要查找的元素。
但特别是基于 ebucket 的四叉树 return 查询位置附近的对象列表。调用程序最终必须检查结果中的所有对象，以确定是否满足应用程序任务。
从这个角度来看，平衡毫无意义。更密集的区域（例如城市）具有更详细的结构，因此具有更深的四叉树。
这还不错。我认为不需要四边形平衡。
进一步对于所有四叉树类型（点、线、对象四叉树）一个四边形节点在分裂时，它总是分裂成4个大小相等的子矩形或二次子节点。这些类型称为受限四叉树。我在平衡四叉树上发现的文献中只有一个提示（M.Bern、D-Eppstein 和 J.Gilbert：可能生成良好的网格，引用自 Hanan Samet：多维空间数据结构基础）。如果您有学术兴趣，您可能会阅读这篇论文，否则我怀疑它对您是否有价值。
否则就不是普通的（即受限的）四叉树。阅读有关 R-Trees 的更多信息，了解如何在单个矩形中细分 space。 （R-trees 是四叉树的竞争对手）
与四叉树对应的唯一四叉类型平衡可能是动态桶大小。但是我看不出有什么优势。
关于保证：
最终构建的静态四叉树的最大深度给出了一个上限。 （随意测量平均深度）。最大桶大小也给出了上限。 （再次测量平均桶大小）。
平衡：
四叉树的结构取决于插入值的顺序。
插入到四叉树中的值通常是静态的，因此可以提前排序。有特定的 pre-orderings 可以提供（稍微）更好的平衡。
请注意，四叉树是一种空间索引，对于删除不是很有用。
我正在寻找一棵 quadtree/octree/2^n 树，当它接受新的观察时会自我平衡，而无需了解其他所有点，iow，它不能依赖中位数，因为我正在写 'streaming'上下文。 AVL树通过旋转来平衡，是否有另一种类似的数据结构用于更高维度的数据？
AVL树，returns只有一个结果，要查找的元素。 但特别是基于 ebucket 的四叉树 return 查询位置附近的对象列表。调用程序最终必须检查结果中的所有对象，以确定是否满足应用程序任务。
从这个角度来看，平衡毫无意义。更密集的区域（例如城市）具有更详细的结构，因此具有更深的四叉树。 这还不错。我认为不需要四边形平衡。
进一步对于所有四叉树类型（点、线、对象四叉树）一个四边形节点在分裂时，它总是分裂成4个大小相等的子矩形或二次子节点。这些类型称为受限四叉树。我在平衡四叉树上发现的文献中只有一个提示（M.Bern、D-Eppstein 和 J.Gilbert：可能生成良好的网格，引用自 Hanan Samet：多维空间数据结构基础）。如果您有学术兴趣，您可能会阅读这篇论文，否则我怀疑它对您是否有价值。
否则就不是普通的（即受限的）四叉树。阅读有关 R-Trees 的更多信息，了解如何在单个矩形中细分 space。 （R-trees 是四叉树的竞争对手） 与四叉树对应的唯一四叉类型平衡可能是动态桶大小。但是我看不出有什么优势。
关于保证： 最终构建的静态四叉树的最大深度给出了一个上限。 （随意测量平均深度）。最大桶大小也给出了上限。 （再次测量平均桶大小）。
平衡： 四叉树的结构取决于插入值的顺序。 插入到四叉树中的值通常是静态的，因此可以提前排序。有特定的 pre-orderings 可以提供（稍微）更好的平衡。
请注意，四叉树是一种空间索引，对于删除不是很有用。