证明正元完成或接近完成，二叉树的高度log_2（N）

Question

我有问题：

证明正元完成或接近完成，二叉树的高度log_2（N）

我在一段时间内还没有完成导入操作，即使如何开始解决问题，我也陷入了困境。我如何去解决这个问题，甚至开始这将是有益的

Answer 1

归纳证明就像递归。你必须“证明”一个基础案例，然后证明下一个最复杂的案例。

例如，对于高度一个完整平衡树的基本情况是一个项目：

A 

一个身高两个树是三个项目的情况下，在以前的水平增加一倍的项目数（前面的所有层次的（）1）加上和1：

A 
/\ 
B C 

用于高度三树的情况是七个品，在上一级项的双数（2）加上前面的所有电平的总和（3）：

_A_ 
/ \ 
    B  C 
/\ /\ 
D E F G 

由于每个级别使容量加倍并增加一个，因此高度为h的树中的项目数n（大致）为2h。

而且，因为幂的反函数是对数，所以我们可以说树h的高度因此是（大致）log2n。