116
правок
Изменения
→Анализ
= Анализ =
Докажем верхнюю оценку стоимости операции <tex>\mathrm{Find}</tex> в <tex>O(\log {n})</tex>.
{{Определение
|id=def_value_node
|definition=Определим '''значение''' вершины <tex>v</tex> {{---}} <tex>val(v)</tex> {{---}} следующим образом: <br/><br/> <tex>val(v) = \left(\frac{3}{2} \right)^{rank(p(v))} </tex>
}}
{{Определение
|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>
}}
= Примечания =
