116
правок
Изменения
→Анализ
</center>
А так как <tex>h(T_A) \leq rank(A)</tex>, утверждение доказано.
}}
{{Утверждение
|statement=
Для всякого сокращенного дерева <tex>T_A</tex> инвариант 3 выполняется
|proof=
Если <tex>h(T_A) = 0</tex> (т. е. дерево состоит только из корня), то <tex>VAL(A) = \left( \frac{3}{2} \right)^{0} = 1 </tex> и <tex> 2^{rank(A)} = 2^0 = 1 \Rightarrow VAL(A) = 2^{rank(A)} </tex>. <br/>
Если <tex>h(T_A) = 1</tex>, то <tex>VAL(A) \geq \left( \frac{3}{2} \right)^{1} + \left( \frac{3}{2} \right)^{0} = \frac{5}{2} </tex> и <tex>2^{rank(A)} = 2^1 = 2 \Rightarrow VAL(A) \geq 2^{rank(A)}</tex>
}}
