关于N个元素需要4N的空间，为什么不是2N？

按照满二叉树计算（最大值的计算），N个元素的最后一层（拆到最小粒度）应该是 N个叶子节点，又因为N层（最后一层）的节点个数相当于前（N-1）层的节点个数总和，所以 S(n-1) 也是N，加上最后一层的N，应该是2N的空间啊。

xiaobai00000 2021-05-11

源自：线段树，Trie 和并查集 1-2 线段树基础表示

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-05-11 14:10:40

关键是由于我们使用数组表示这棵二叉树，所以，这棵二叉树必须是完全二叉树。最后一层没有元素的地方会浪费空间。

以 6 个节点为例（1， 2， 3， 4， 5，6）。得到的二叉树是这个样子的。

            O
       /        \
     O            O
   /   \        /   \
  O     3      O     6
 / \   / \    / \
1   2 X   X  4   5

注意两个 X 的地方，他们是占空间的，虽然我们的算法不会访问这里，但是，为了访问 4, 5 两个节点，X 所在的空间只能浪费。因此，这棵有 6 个叶子节点的树，使用 12 个节点是不够的。

==========

但这里要说明的是，因为这个代码使用了递归的方式，自顶向下构造这棵树，所以在这里会产生根节点的左右子树分别覆盖三个节点的情况。

如果是自底向上构造，可以避免这个空间的耗费。此时，使用 2n 的空间就够了。（类似于归并排序自底向上构造）。

自底向上构造平衡树的方式课程中没有介绍，如果感兴趣可以自己实现一下，是一个很好的练习：）

继续加油！：）

收起回答

xiaobai00000 提问者 #1

恩，我大概明白了，我总结了一下，老师看下这么理解对不？ <br/>

1. 首先，真实的叶子节点个数是N没错，但是并不一定都在同一层，所以按照最差的情况，使用4N的空间存储。<br/>

2. 当节点个数为2^k 的时候，因为区间拆分和二分法一样每次都是从中间去拆，所以将是一个满二叉树，这种情况
就可以使用2N的空间去存放。 <br/>

3. 因为区间拆分和二分法一样每次都是从中间去拆，所以必定是一颗平衡二叉树。<br/>

4. 老师上面列举的6个节点的例子，‘3’有双X占用空间,‘6’没X 是因为：‘6’之后没有节点了，而‘3’有，
如果‘3’没双X占空间的话， 后面的节点，按照之前 父子节点的计算公式，会产生数组越界的问题。<br/> 

5. 针对数据而言，只要是2^N 个数的 都可以使用 2N 的数组存放，否则使用 4N。

2021-05-11 18:20:57