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,我想知道我的推测结果是否正确。
然后我想分享我的算法,听听它是否是实现它的正确方法:
- 将点列表传递给根对象
- 找到中点并将其指定给根"点"
- 使用中点拆分点列表
- 使用交换的拆分标注创建两个子对象"左"answers"右"
- 将点列表传递给两个子对象
- 对于子对象,请转到第2点(为了本算法的目的,现在成为root对象)
这是正确的方法吗?我应该换一种方式吗?我在搜索任何样本,但我只找到了类似的n维实现:
https://code.google.com/p/kd-sharp/source/browse/trunk/KDTree/KDNode.cs
这对我来说似乎过于复杂了。
您所描述的正是二维的KD树。
如果没有其他东西阻止你这样做,我只会使用这个库。