tree - 如何证明堆数据结构中的 child 位于: 2*n and 2*n+1?

Question

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

Answer 1

归纳证明:

根 (1) 的 child -> child1= 2*1=2 , child2= 2*1 + 1 = 3 真

假设 第 k 个元素的 child 是 -> child1= 2k , child2=2k+1

证明 第 (k+1) 个元素的 child 是 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的第一个 child )(a)

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

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