c - 求和，数组构造和寻址的简洁二叉树

Question

使用“sum”作为捷径进行任意计算。我有一个通过递归求和值对来从值列表中计算单个和的过程。未配对的值将被不变地提升到树上，直到可以配对为止。

在进行了这种计算之后，我正在寻找平衡计算的最佳方法(即访问数组元素/节点所需的操作数)以及一维数组中所有节点的最简洁的编码(即无间隙，零值) (或重复值)，并且最好没有额外的索引数组，该数组不能从简洁编码中轻松得出，因此必须将其与数组一起保存。

尽管以下是简单的示例，但实际上，初始列表中的值数量可能非常大(2 ^ 47或更多)。

例如，给定列表[1、2、3、4]，该数组是微不足道的:[10、3、7、1、2、3、4]，并很好地拆分为易于按节点寻址的行，或作为对整个行的引用。

但是对于5项列表，树看起来像这样:

树1

         15
        /  \
       /    \
      /      \
     /        \
    10          5
  /   \       /   \
 3     7     5     -
/ \   / \   / \   / \
1  2  3  4 5   - -   -

标准映射 left = i*2+1， right = i*2+2为我们提供了以下数组:

阵列1

[ 15, 10,  5,  3,   7,   5,  nil,   1,   2,   3,   4,   5,   nil,   nil, nil]

该数组具有4个nil值，列表“5”中的最后一个元素重复2次。

为了改善这一点，我们可以暗示重复5，并删除nil值:

阵列2

[15, 10, 3, 7, 1, 2, 3, 4, 5]

这更紧凑。这棵树是相同的，但从概念上看有点像:

树2

       15
      / \
     /   \
    10    \
  /   \    \
 3     7    \
/ \   / \    \
1  2  3  4    5

在 数组2 编码中，我有4行:

1. [1, 2, 3, 4]
2. [3, 7]
3. [10, 5]
4. [15]

行1，行2和行4可以简单地引用到 数组2 中，这使我可以“就地”计算结果，而无需分配或复制。非常快。但是，第3行包含两个不连续单元格中的值。我必须打破用于其他行的简单逻辑，并可能为 map 添加副本，索引或存储。

我可以构造完整/平衡的子树(例如索引1-7、1、2、3、4的树)，但是当奇数个项目出现在不同的行时，它们似乎并不会总是很好地对齐取决于输入长度。例如，考虑具有6个元素的初始列表的树。

Answer 1

假设您的树在最后(最多)行上具有N节点。

如果确实存储仅向上传播的节点，则树的总数在2*N-1和2*N-1+log2(N)节点之间。节点的确切总数由OEIS A120511给出。其中，最多floor(2 + log2(N-1))是复制/传播的节点。

树上有floor(2 + log2(N-1))行。作为N的函数的行数(最后一行的元素数)是OEIS A070941。

这样的树中的行数非常低。例如，如果最后一行有240≈1,000,000,000,000个节点，则树中只有42行。对于264个节点，您只有66个。因此，如果您需要每行进行一些操作，则开销不会很高。

给定最后一行N中的节点数，一个简单的对数时间函数可以计算行数和节点总数。

# Account for the root node
rows = 1
total = 1

curr_left = N
While (curr_left > 1):
    rows = rows + 1
    total = total + curr_left
    curr_left = (curr_left + 1) / 2
End While

其中 /表示整数除法，即任何小数部分都被丢弃/截断/舍入为零。同样，对于最后一行中的264个节点，以上仅循环65次。

当我们知道树中的节点总数和行数时，我们可以使用另一个对数时间循环来计算树的每一行上第一个元素的偏移量以及该行上的节点数:

first_offset = []
nodes = []

curr_row = rows - 1
curr_offset = total - N
curr_left = N

While (curr_left > 1):
    nodes[curr_row] = curr_left
    first_offset[curr_row] = curr_offset
    curr_row = curr_row - 1
    curr_left = (curr_left + 1) / 2
    curr_offset = curr_offset - curr_left
}

first_offset[0] = 0
nodes[0] = 1

与之前一样，对于最后一行中的264个节点，以上仅循环65次。

行中的所有元素在内存中都是连续的，如果我们使用从零开始的索引，并且 N是最后一行中的节点数，则应用上面的内容，然后

rows是树

中的行数

total是树

中的节点总数

如果nodes[r]和r

，则在 r >= 0行上有 r < rows节点

行r上的节点的数组索引，列c是first_offset[r] + c

行r上的节点，列c上，带有r > 0，在行r-1上，列c/2上有一个父节点，数组索引为first_offset[r-1] + c/2

行r(列c)上的节点(带有r < rows - 1)，在行r+1(列2*c)上具有左子节点，数组索引为first_offset[r+1] + 2*c

第r行，第c列上的节点(带有r < rows - 1和c < nodes[r] - 1)在第r+1行，第2*c+1列上有一个正确的子节点，在数组索引first_offset[r+1] + 2*c + 1上

行r，列c上的节点(带有r < rows - 1和c < nodes[r] - 1)具有左右两个子

该阵列非常紧凑，除了向上传播的节点(对于一个TB级的数据集，可能只有几十个节点)之外，它不会浪费存储空间。

如果最后一行中的节点数与数组一起存储(例如，作为数组数据后的额外 uint64_t)，则所有阅读器都可以恢复 total， rows， first_offset[]和 nodes[]，并轻松导航树。 (但是，请注意，您不仅可以使用数组索引，还可以使用“column”和“row”，并使用它们来派生数组索引。)

由于 first_offset[]和 nodes[]数组最多具有几十个条目，因此它们应在高速缓存中保持高温，并且使用它们不应损害性能。

请注意，并非所有树大小都适用于以上第二段所述的规则。例如，具有两个节点的树没有意义:为什么要复制根节点？

如果您确实知道树的大小( total)有效，则可以使用二进制搜索以 N时间复杂度为基础，根据 total查找 O(log2(total)*log2log2(total))，如果使用简单循环，则可以以 O((log2(total))²)为基础。请记住， total在 2*N-1和 2*N-1+log2(N)之间。相反， N不能大于 (N + 1)/2或小于 (N + 1)/2 - log2(total)，因为 total大于 N，因此 log2(N)小于 log2(total)。因此，二进制搜索可以实现为

Function Find_N(total):
    Nmax = (total + 1) / 2
    Nmin = Nmax - log2(total)

    t = Total(Nmin)
    If t == total:
        Return Nmin
    Else if t < total:
        Return "Bug!"
    End if

    t = Total(Nmax)
    if t == total:
        Return Nmax
    Else if t > total:
        Return "Bug!"
    End if

    Loop:

        N = (Nmin + Nmax) / 2
        If N == Nmin:
            Return "Invalid tree size!"
        End If

        t = Total(N)
        If t > total:
            Nmax = N
        Else if t < total:
            Nmin = N
        Else:
            return N
        End If            
    End Loop
End Function

请记住，即使树中有264个节点，上述函数也最多对 1 + log2(64)进行 Total = 6调用，该函数实现了此答案中的第一个伪代码段。由于通常每个程序调用仅需要一次，因此开销实际上是不相关的。

自C99起，您就可以使用 log2(x)来计算 log(x)/log(2)，并使用 log2()中的 <math.h>函数(但是由于 double的精度不及 uint64_t，我会在结果中添加 +1，或者使用 ceil()将其四舍五入为正无穷大)，甚至使用一个简单的循环:

Function ulog2(value):
    result = 0
    While (value > 0):
        result = result + 1
        value = value / 2
    End While
    Return result
End Function

其中 /再次表示整数除法。