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

Question

我正在为数据序列构建一个二叉树，该树存储在一个从 1 开始的数组中。所以如果父节点的索引是idx，左边的 child 是 2 * idx，右边的 child 是 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 之间有一个空洞。

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

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

Answer 1

二叉树的每一层包含的节点数是上一层的两倍。如果您有 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

树的最后一层所需的数组空间数要么是 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 个节点分配空间(左侧项目 2 个，空白区域 2 个)，再加上两个右侧项目的空间。

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