kd树总是平衡的吗？

Question

我用过kd-tree algoritham并制作树.

但是我发现树不平衡所以我的问题是如果我们使用kd-tree algoritham那么树总是平衡的,如果没有那么我们怎样才能使它平衡？

我们可以使用另一个algoritham喜欢AVL或Red-Black来平衡kd树吗？

我有一些示例数据,我使用kd-tree algoritham,但树不平衡.

 (14,31), (15,32), (17,42), (16,44), (18,52), (16,62)

Answer 1

这是一个相当广泛的主题,问题本身就是一般性的.希望这将为您提供一些有用的见解和材料:

• Kd树并不总是平衡的.
• AVL和Red-Black不能与KD树一起使用,您可以构建一些平衡变量,例如KDB树或使用其他平衡技术.
• Kd Tree通常用于存储地理空间数据,因为它们允许您搜索多个密钥,这与允许您进行单维搜索的"传统"树相反.地理空间数据肯定无法用单维表示.

请注意,还有专门的数据库使用GeoSpatial数据,所以可能值得检查是否可以将开销转移到他们而不是自己的解决方案:虽然我没有太多的经验,可能值得检查postgis .

PostGIS的

以下是一些有用的链接,展示了如何使用Spatial数据构建平衡的KD树变体和KD树的使用:

平衡KD树

KDB树

空间数据kd-trees

Answer 2

这取决于您如何构建树。

如果按照最初发布的方式构建，树将是平衡的，即仅在叶级别它最多具有 1 的高度差。如果您的数据集有 2^n-1 个元素，则树将是完全平衡的。

当用中位数构造时，一半的对象必须在树的任一分支上，因此它具有最小的高度并且是平衡的。

然而，这棵树不能改变。我不知道会保留此属性的插入或删除算法，但 YMMV。我敢打赌，有两打 kd-tree 扩展旨在重新平衡并使插入/删除更有效。

kd-tree 不是为变化而设计的，很快就会失去效率。它依赖于中位数，因此对树的任何更改在最坏的情况下都会传播到整个树。因此，您需要在树质量中允许一些容差以支持更改。跟踪插入/删除并最终重建树似乎是一种常见的方法。您不能将其与红黑树或 AVL 树结合使用，因为超过 1 维的数据没有排序；这些树仅适用于有序数据。树旋转时，分裂轴发生变化；并且可能有一半的元素突然需要移动到另一个分支。这不会发生在 AVL 或红黑树中。

但是你可以想象，人们已经发布了几个保持平衡的索引。例如kdb-trees和R-trees。这些对于需要存储在磁盘上的大数据也更有效。