116
правок
Изменения
Нет описания правки
* Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
* Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)
=== Реализация <tex>makeset(x)</tex> ===
Тривиально:
1. Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) \leftarrow v, rank(v) \leftarrow 0</tex>
2. Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{NL_{LIST}}</tex> и <tex>\mathrm{C_{LIST}}</tex>.
3. Создадим <tex>\mathrm{DFS_{LIST}}</tex> с одним элементом - вершина <tex>v</tex>
Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>
=== Реализация <tex>union(A, B)</tex> ===
Пусть <tex> T_A, T_B </tex> - деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
Пусть размер одного из деревьев меньше 4; не умаляя общности - <tex>size(T_B)</tex> < 4</tex>. Тогда действуем следующим образом:
1. <tex>\forall v \in T_B : \: p(v) \leftarrow root(T_A), \: rank(v) \leftarrow 0</tex>
2. <tex> rank(root(T_A)) \leftarrow max \: \{ rank(root(T_A)), 1 \: \}</tex>
3. Добавим все вершины <tex>T_B </tex> в <tex>\matrm{ DFS_{LIST}} </tex> и <tex>\mathrn{C_{LIST}}</tex> корня <tex>T_A</tex>
