0

我正在尝试在我的结果之上构建一个搜索树。某种末端有 n 个叶子的 k-ary 树。我正在寻找 C++ 解决方案并进行试验，std::vector但由于我需要内存一致性而无法完成。它可以通过嵌套向量来完成，但我不能这样做。

让我通过例子来解释细节：

未排序的结果可能是

Result R = { 4, 7, 8, 3, 1, 9, 0, 2, 2, 9, 6 }

最重要的是，我需要一棵树，其节点在我的特定问题中是质心。但为了简单起见，我将在这里使用人工值。

我将搜索树维度定义为

Height H = 2
Branch B = 3

最初的树

4 7 8 3 1 9 0 2 2 9 6

第二步

layer_0          1.6    5      8.2
                   |    |        |
         +-+-+-+-+-+  +-+  +-+-+-+
         | | | | | |  | |  | | | |
layer_1  3 1 0 2 2 3  4 6  7 8 9 9

最后一步

layer_0                 1.6          5           8.2
                          |          |             |
                  +---+---+    +-+---+    +---+----+
layer_1         0.8 1.6 2.4  4.2 5 5.8  6.4 8.2  8.4
                  |       |    |     |    |   |    |
                +-+   +-+-+    |     |    |   |  +-+
layer_2         1 0   2 2 3    4     6    7   8  9 9

这最后一棵树不是 k-ary 树，因为端叶大小为0 <= size <= |R|.

目前我正在试验两个向量。

std::vector<size_t> layer_2;

std::vector<float> leafs;

std::size_t width, height;

在 的帮助下width，height可以浏览leafs. 但我在质疑自己如何优雅地连接leafs和layer_2？

一个好的解决方案应该是什么样子的？

4

1 回答 1

0

注意：这个解决方案是连续的，因为它使用连续的数据结构（向量或数组）而不是节点指针样式树，但根据应用程序，数据结构中可能存在未使用的空间。

这种方法浪费大量空间的情况：每个节点的最大分支数量很大，但大多数节点实际上有更少的子节点。不过，这不会影响找到叶子所需的时间。事实上，让它变得相当快是一种权衡。

考虑连续内存中具有 4 级的 3 分支树： R,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,aba,abb,abc,baa....其中节点子节点的索引范围从 (parent_index*3)+1 到 (parent_index*3)+3

我提到的重要警告是，每个节点必须始终在向量、数组等中具有它的三个子空间。如果一个节点说只有 2 个孩子，只需用 null_child 值填充该额外空间以保存空间。（这就是浪费空间的来源）

优点是现在很容易找到所有的叶子。

first_leaf_index = 0
for(i=0;i<(4-1);i++)//in this example 4 is the depth
    first_leaf_index += 3^(i) //three is max branches per node

此时只需迭代到数据结构的末尾

于 2017-03-17T19:47:23.697 回答