如何证明堆数据结构中的子节点位于：2*n 和 2*n+1？

Question

这不是作业问题，我今天学习了堆数据结构，我不知道如何证明关系是真的。谢谢。

Answer 1

归纳证明：

1. 根 (1) 的孩子 -> child1= 2*1=2 , child2= 2*1 + 1 = 3 true
2. 假设第 k 个元素的孩子是 -> child1= 2k ， child2=2k+1
3. 证明第 (k+1) 个元素的孩子是 child1= 2*(k+1), child2=2(k+1) + 1 （证明这个）

证明 3：由于第 k 个元素的子元素在 2k 和 2k+1（基于假设），那么接下来的两个元素是 2k+2 和 2k+3。

2k+2 = 2(k+1)（证明了k+1的第一个孩子）(a)

2k+3 = 2k + 2 + 1 = 2(k+1) + 1 (证明了k+1的第二个孩子)(b)

from (a) & (b) --> 因此 3 是有效的，因此元素 n 的子元素是 2n 和 2n+1