Изменения
→Описание
Структура данных должна поддерживать следующие операции:
* <tex>\mathrm {Makeset(x)}</tex> {{---}} создать новое множество из <tex>1</tex> элемента <tex>x</tex>. Время: <tex>O(1)</tex>.
* <tex>\mathrm {Union(A, B)}</tex> {{---}} объединить множества <tex>A</tex> и <tex>B</tex> в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>\mathrm{Find}</tex>, которая используется, если множества <tex>A</tex> и <tex>B</tex> заданы своими произвольными представителями.
* <tex>\mathrm {Find(x)}</tex> {{---}} найти множество, в котором содержится элемент <tex> x </tex>. Время: <tex>O(\log {n})</tex> в худшем случае, <tex>O(\alpha(n))</tex> {{---}} в среднем (<tex>\alpha(n)</tex> {{---}} обратная функция Аккермана), где <tex> n </tex> {{---}} размер множества.
* <tex>\mathrm{Delete(x)}</tex> {{---}} удалить элемент x из содержащего его множества. Время: <tex>O(1)</tex>.
В дальнейшем мы будем использовать следующие понятия и обозначения:
* <tex>size(A)</tex> {{---}} размер множества <tex>A</tex> (количество элементов в нем).
* <tex>root(T_A)</tex> {{---}} корень дерева <tex>T_A</tex>.
* <tex>h(v)</tex> {{---}} высота вершины <tex>v</tex>: если <tex>v</tex> является листом, то <tex>h(v) = 0</tex>, иначе <tex>h(v) = \max \{ h(w) \: | \: w - \mathrm{ child \: of } \: v \} + 1</tex>.
* <tex>p(v)</tex> {{---}} родитель вершины <tex>v</tex>. Если <tex>v</tex> {{---}} корень, то считаем, что <tex>p(v) = v</tex>.
* <tex>rank(v)</tex> {{---}} ранг вершины, некоторая верхняя оценка на ее высоту.
