内存连续性和搜索树

Question

我正在尝试在结果之上构建一个搜索树。某种末端有 n 个叶子的 k 叉树。我正在寻找 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 叉树，因为端叶大小为

0 <= size <= |R|

。

此时我正在试验两个向量。

std::vector<size_t> layer_2;

std::vector<float> leafs;

std::size_t width, height;

在

width

和

height

的帮助下，可以通过

leafs

进行导航。但我在问自己如何优雅地连接

leafs

和

layer_2

？

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

Answer 1

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

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

考虑连续内存中具有 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

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