我一直在对二叉树和数组列表表示进行一些研究。我很难理解最坏情况下的空间复杂度是 O(2^n)。具体来说，这本书指出，空间使用量为 O(N)（N = 数组大小），在最坏的情况下为 O(2^n)。我原以为在最坏的情况下它会是 2n，因为每个节点都有两个子节点（索引）而不是 O(2^n)，其中 n = 否。的元素。
例如，如果我有一个有 7 个节点的二叉树，那么空间将是 2n = 14 而不是 2^n = 128。
问问题
2894 次
3 回答
1
这是数组上的堆实现。在哪里
A[1..n]
left_child(i) = A[2*i]
right_child(i) = A[2*i+1]
parent(i) = A[floor(i/2)]
现在，来到太空。凭直觉思考，
当您插入第一个元素 n=1，location=A[1] 时，类似地，
n=2 @A[2] left_child(1)
n=3 @A[3] right_child(1)
n=4 @A[4] left_child(2)
n=5 @A[5] right_child(2)
你看，第 n个元素将进入A[n]. 所以空间复杂度是O(n)。
当您编码时，您只需将要插入的元素插入最后说 at A[n+1]，并说它是floor((n+1)/2).
参考：http ://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
堆是一棵几乎完整的树，因此树中的元素总数将是您需要的数组长度。参考：这个2h-1 < n <= 2h+1-1
于 2012-10-29T04:42:55.193 回答
0
二叉树的最坏情况空间复杂度是 O(n) （在您的问题中不是 O(2^n)），但是如果它几乎是一棵完整的二叉树，则使用数组表示二叉树可以节省指针空间。
于 2012-10-29T04:37:35.457 回答
0
我认为这是指将任意二叉树存储在数组表示中，这通常用于完整或接近完整的二叉树，特别是在堆的实现中。
在这种表示中，根存储在0数组中的索引处，对于任何具有索引的节点n，其左右子节点分别存储在索引2n+1和处2n+2。
如果您有一个退化树，其中没有节点有任何正确的孩子（树实际上是一个链表），那么第一个项目将存储在 indices 0, 1, 3, 7, 15, 31, ...。通常，n此列表的第一项（从 开始0）将存储在索引处，因此在这种情况下，数组表示需要空间。2n-1θ(2n)
于 2012-10-29T05:21:10.273 回答