116
правок
Изменения
→Анализ
}}
{{Утверждение Лемма|id=lemma_1
|statement=
Для всякого сокращенного дерева <tex>T_A</tex> инвариант 3 выполняется
Если <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>
}}
Докажем теперь, что каждая из операций сохраняет инвариант 3.
== Makeset ==
Т. к. операция <tex>\mathrm{Makeset}</tex> создает сокращенное дерево, то по лемме 1 <tex>\mathrm{Makeset}</tex> сохраняет инвариант 3
== Union ==
Пусть для множеств <tex>A</tex> и <tex>B</tex> инвариант 3 выполняется. <br/>
Пусть <tex>C = \mathrm{Union(A, B)}</tex>. Пусть, не умаляя общности, <tex>rank(A) > rank(B)</tex>. Тогда мы подвесим <tex>T_B</tex> к корню <tex>T_A</tex>, и <tex>rank(C)</tex> будет равным <tex>rank(A)</tex>, и следовательно, <br/><br/><center><tex>VAL(C) > VAL(A) \geq 2^{rank(A)} = 2^{rank(C)}</tex></center><br/>
Пусть теперь <tex>rank(A) = rank(B)</tex>, тогда <tex>rank(C) = rank(A) + 1</tex> и имеем:
<br/><center><tex>VAL(C) > VAL(A) + VAL(B) \geq 2^{rank(A)} + 2^{rank(B)} = 2^{1 + rank(A)} = 2^{rank(C)} </tex></center><br/>
Следовательно, операция <tex>\mathrm{Union}</tex> сохраняет инвариант 3.
== Find ==
Пусть для множества <tex>A</tex> инвариант 3 выполняется.
Операция <tex>\mathrm{Find}</tex> изменяет дерево <tex>T_A</tex>. Если после выполнения <tex>\mathrm{Find} \; T_A</tex> стало сокращенным, то инвариант 3 сохранен по лемме 1. <br/>
Осталось рассмотреть другой случай - когда до и после выполнения <tex>\mathrm{Find} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Find}</tex> как <tex>A'</tex>
<br/> Так как <tex>\mathrm{Find}</tex> изменяет <tex>T_A</tex> только посредством операции <tex>\mathrm{Relink}</tex>, достаточно доказать, что <tex>\mathrm{Relink}</tex> сохраняет инвариант 3.
=== Анализ операции Relink ===
= Примечания =
