内存连续性和搜索树

Question

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

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

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

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

我提到的重要警告是每个节点必须始终在向量、数组等中包含三个 child space。如果一个节点只有 2 children，只需用 null_child 值填充那个额外的 space 来保存 space。（这是浪费space的来源）

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

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

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

内存连续性和搜索树

Memory continuity and search tree

c++

tree

contiguous