116
правок
Изменения
→Анализ
|id=def_value_tree
|definition='''Значение множества''' <tex>A</tex> {{---}} <tex>VAL(A)</tex> {{---}} сумма значений вершин <tex>T_A</tex>: <br/><br/> <tex>VAL(A) = \sum\limits_{v \in T_A} {val(v)} </tex>
}}
Нам необходимо доказать, что все определенные нами операции {{---}} <tex>\mathrm{Makeset}</tex>, <tex>\mathrm{Union}</tex>, <tex>\mathrm{Find}</tex> и <tex>\mathrm{Delete}</tex> {{---}} поддерживают следующий инвариант:
; Инвариант 3:
: <tex>VAL(A) \geq 2^{rank(A)} </tex>
{{Утверждение
|statement=
При выполнении инварианта 3 высота дерева не превышает <tex>O(\log {n})</tex>
|proof=
Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <tex>val(v) \leq \left(\frac{3}{2} \right)^{rank(A)}</tex>, то: <br/>
<center>
<tex>
2^{rank(A)} \leq VAL(A) \leq |A| \left(\frac{3}{2} \right)^{rank(A)}
\newline
\newline
|A| \geq \frac {2^{rank(A)}} {\left(\frac{3}{2} \right)^{rank(A)}} = \left( \frac {4} {3} \right)^{rank(A)}
\newline
\newline
rank(A) \leq \log_{ \frac{4}{3} } { (|A|) } = O(\log {|A|}) = O(\log{n})
</tex>
</center>
А так как <tex>h(T_A) \leq rank(A)</tex>, утверждение доказано.
}}
