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

Question

我正在为一系列数据构建一个二叉树，并且该树存储在一个基于 1 的数组中。因此，如果父节点的索引是 idx，则左子节点为 2 * idx，右子节点为 2 * idx + 1。

每次迭代，我根据一定的条件对当前序列进行排序，选择中间元素作为父元素，tree[index] = sequence[median]，然后对左边（中间值之前的子序列）和右边（中间值之后的子序列）做同样的操作递归地。

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

  1
 / \
2   3   

存储树的数组大小也是 3

4个要素：

    1 
   / \
  2   3  
 /
4       

存储树的数组大小也是 4

5个要素：

      1 
   /     \
  2       3  
 / \     /
4 null  5    

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

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

任何建议将不胜感激。谢谢。

标签： algorithmbinary-tree

Answer 1

    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);