C#中的平衡二维树实现

本文关键字:二维 实现 平衡 | 更新日期: 2023-09-27 18:24:10

我想征求一个关于以平衡方式实现二维树结构保持点的建议。

我有(一个例子):{0,2},{2,3},{5,3},{6,4}

我需要什么(如果我对平衡树是正确的):

     {5, 3}
       |
{6, 4} - {2, 3}
           |
    {0, 2} - null

首先,考虑到节点的分裂维度为0,我想知道我的推测结果是否正确。

然后我想分享我的算法,听听它是否是实现它的正确方法:

  1. 将点列表传递给根对象
  2. 找到中点并将其指定给根"点"
  3. 使用中点拆分点列表
  4. 使用交换的拆分标注创建两个子对象"左"answers"右"
  5. 将点列表传递给两个子对象
  6. 对于子对象,请转到第2点(为了本算法的目的,现在成为root对象)

这是正确的方法吗?我应该换一种方式吗?我在搜索任何样本,但我只找到了类似的n维实现:

https://code.google.com/p/kd-sharp/source/browse/trunk/KDTree/KDNode.cs

这对我来说似乎过于复杂了。

C#中的平衡二维树实现

您所描述的正是二维的KD树。

如果没有其他东西阻止你这样做,我只会使用这个库。