116
правок
Изменения
→Основные положения
{{Определение
|id=def_value_node
|definition=Определим '''значение''' вершины <tex>v</tex> {{---}} <tex>val(v)</tex> {{---}} следующим образом: <br/><br/> <texdpi='160'>val(v) = \left(\frac{3}{2} \right)^{rank(p(v))} </tex>
}}
{{Определение
При выполнении '''инварианта 3''' высота дерева не превышает <tex>O(\log {n})</tex>
|proof=
Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <texdpi='140'>val(v) \leqslant \left(\frac{3}{2} \right)^{rank(A)}</tex>, то: <br/>
<center>
<texdpi='160'>
2^{rank(A)} \leqslant VAL(A) \leqslant |A| \left(\frac{3}{2} \right)^{rank(A)}
\newline
Для всякого сокращенного дерева <tex>T_A</tex> '''инвариант 3''' выполняется
|proof=
Если <tex>h(T_A) = 0</tex> (т. е. дерево состоит только из корня), то <texdpi='140'>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>, то <texdpi='140'>VAL(A) \geqslant \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) \geqslant 2^{rank(A)}</tex>
}}
