我正在为数据序列构建一个二叉树,该树存储在一个从 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 之间有一个空洞。
因此,数组大小仅由元素的数量决定,我相信对此有解析解,只是无法证明。
任何建议将不胜感激。 谢谢。
最佳答案
二叉树的每一层包含的节点数是上一层的两倍。如果您有 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)
关于algorithm - 预测二叉树数组大小的解析解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54226557/