116
правок
Изменения
→Find
Пусть для множества <tex>A</tex> '''инвариант 3''' выполняется. <br>
Операция <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.
