algorithm - kd-tree 总是平衡的吗？

Question

我使用了 kd-tree algoritham 和 make tree。

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

我们可以使用另一种算法，如 AVL 或 Red-Black 来平衡 kd 树？

我有一些样本数据，我使用了 kd-tree algoritham 但那棵树不平衡。

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

Answer 1

这是一个相当宽泛的话题，问题本身也比较笼统。希望这会为您提供一些有用的见解和 Material :

• Kd 树并不总是平衡的。
• AVL 和 Red-Black 不适用于 K-D 树，您将构建一些平衡变体(例如 K-D-B 树)或使用其他平衡技术。
• K-d 树通常用于存储地理空间数据，因为它们可以让您搜索多个键，这与让您进行一维搜索的“传统”树相反。地理空间数据当然不能用单一维度表示。

请注意，还有专门的数据库处理 GeoSpatial 数据，因此可能值得检查是否可以将开销转移给它们而不是制定自己的解决方案:虽然我对此没有太多经验，但也许值得检查 postgis。

postgis

以下是一些有用的链接，展示了如何构建平衡的 K-D 树变体以及 K-D 树与空间数据的用法:

balancing K-D-Tree

K-D-B-tree

spatial data k-d-trees