kd树总是平衡吗？ [英] Is kd-tree always balanced?

问题描述

我使用kd-tree算法和树。

但是我发现树不平衡，所以我的问题是如果我们使用kd-tree算法，那么树总是平衡的，那么如何才能平衡？ 。

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

我有一些样本数据，我使用kd-tree算法，但是树不平衡。

<$ p $（$）$（$）$（$ code）（14,31），（15,32），（17,42），（16,44），（18,52） code>

解决方案

这是一个相当广泛的话题，问题本身就是一般的。
希望这将为您提供一些有用的见解和材料：

• Kd树并不总是平衡。 >
  
• AVL和Red-Black将无法使用KD树，您将构建一些平衡的变体，如KDB树或使用其他平衡技术。


• Kd Tree通常用于存储GeoSpatial数据，因为它们允许您搜索超过一个键，与传统树相反，可以让您进行单维搜索。 GeoSpatial数据肯定不能以单一维度表示。

请注意，还有专门的数据库使用GeoSpatial数据，因此可能值得检查如果开销可以转移到他们而不是自己的解决方案：虽然我没有太多的经验，也许值得检查postgis。

< a href =http://postgis.net/ =noreferrer> postgis

以下是一些有用的链接，显示如何构建平衡KD树变体和使用具有空间数据的KD树：

平衡KD-Tree

KDB-tree

空间数据kd-trees

I have used kd-tree algoritham and make tree.

But i found that tree is not balanced so my question is if we used kd-tree algoritham then that tree is always balanced if not then how can we make it balance ?.

We can use another algoritham likes AVL or Red-Black for balancing kd tree ?

I have some sample data for that i used kd-tree algoritham but that tree is not balanced.

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

解决方案

This is a fairly broad topic and the questions themselves are kind of general. Hopefully this will give you some useful insights and material to work with:

• Kd tree is not always balanced.
• AVL and Red-Black will not work with K-D Trees, you will have either construct some balanced variant such as K-D-B-tree or use other balancing techniques.
• K-d Tree are commonly used to store GeoSpatial data because they let you search over more then one key, contrary to 'traditional' tree which lets you do single dimensional search. GeoSpatial data certainly cannot be represented in single dimension.

Note that there are also specialized databases working with GeoSpatial data so it might be worth checking if the overhead could be shifted to them instead of making your own solution: Although i don't have much experience with this, maybe it is worth checking the postgis.

postgis

Here are some useful links showing how to build balanced K-D tree variant and usage of K-D trees with Spatial data:

balancing K-D-Tree

K-D-B-tree

spatial data k-d-trees

这篇关于kd树总是平衡吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！