预测二叉树数组大小的解析解

Question

我正在为数据序列构建一个二叉树，该树存储在一个从 1 开始的数组中。所以如果 parent 节点的索引是 idx，左边 child 是 2 * idx 右边是 2 * idx + 1.

每次迭代，我根据一定的标准对当前序列进行排序，select中间元素为parent，tree[index] = sequence[median]，然后对左边做同样的操作（中位数之前的子序列）和右（中位数之后的子序列）递归。

例如，如果总共有 3 个元素，树将是：

  1
 / \
2   3

存储树的数组大小也是3

4个元素：

存储树的数组大小也是4

5 个元素：

存储树的数组大小必须为 6，因为 4 和 5 之间有一个空洞。

因此，数组大小仅由元素个数决定，我相信有解析解，只是无法证明。

如有任何建议，我们将不胜感激。谢谢

Answer 1

你真的不应该有任何漏洞。它们是由您的分区算法创建的，但该算法不正确。

对于 1-5 项，您的树应该如下所示：

  1       2       2       3       4
         / \     / \     / \     / \
        1       1   3   2   4   2   5
                       /       / \
                      1       1   3

填充树的最简单方法是按顺序遍历节点位置，按顺序填充序列中的项目。

Answer 2

我即将正式确定解决方案。凭直觉，先求2 < N的最大次方，然后判断N - 2^m是偶数还是奇数，决定leave level的哪一部分需要增长。

Answer 3

二叉树的每一层包含的节点数是上一层的两倍。如果您有 n 个节点，则所需的级别数（树的高度）为 log2(n) + 1，四舍五入为整数。所以如果你有 5 个节点，你的二叉树的高度将为 3。

一棵高度为h的满二叉树的节点数为(2^h) - 1。所以你知道 5 个项目所需的最大大小数组是 7。假设所有级别都已填充，可能除了最后一个。

树的最后一行将包含 (2^h)-1 - n 个节点。完整树的最后一层包含 2^(h-1) 个节点。假设你希望它平衡，所以一半节点在左边，一半在右边，右边是左填充，也就是你想要这样：

             1
        2         3
     4    5    6     7
    8 9      10 11

树的最后一层所需的数组 spaces 的数量要么是 1，要么是完整树所需数量的一半加上树所需节点的一半.

所以：

n = 5
height = roundUp(log2(n) + 1)
fullTreeNodes = (2^height) - 1
fullTreeLeafNodes = 2^(height-1)
nodesOnLeafLevel = fullTreeNodes - n

有趣的部分来了。如果叶子层级需要的节点数超过1个，要平衡边，需要fullTreeLeafNodes的一半，再加上nodesOnLeafLevel的一半。例如，在上面的树中，叶子层可能有 8 个节点。但是你只有 4 个叶节点。您想要其中两个在左侧，两个在右侧。因此，您需要为左侧的 4 个节点分配 space（2 个用于左侧项，2 个为空 space），再加上两个用于右侧的两个项。

if (nodesOnLeafLevel == 1)
    arraySize = n
else
    arraySize = (fullTreeNodes - fullTreeLeafNodes/2) + (nodesOnLeafLevel / 2)

Answer 4

    int32_t rup2 = roundUpPower2(nPoints);
    if (rup2 == nPoints || rup2 == nPoints + 1)
    {
        return nPoints;
    }
    int32_t leaveLevelCapacity = rup2 / 2;
    int32_t allAbove = leaveLevelCapacity - 1;
    int32_t pointsOnLeave = nPoints - allAbove;

    int32_t iteration = roundDownLog2(pointsOnLeave);
    int32_t leaveSize = 1;
    int32_t gap = leaveLevelCapacity;
    for (int32_t i = 1; i <= iteration; ++i)
    {
        leaveSize += gap / 2;
        gap /= 2;
    }
    return (allAbove + leaveSize);

预测二叉树数组大小的解析解

Analytical solution to predict array size of binary tree

algorithm

binary-tree