Изменения

Перейти к: навигация, поиск

СНМ с операцией удаления за О(1)

Нет изменений в размере, 20:47, 31 мая 2014
→‎Реализация makeset(x)
* Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)
=== Реализация <tex>makeset(x)</tex> операции Makeset ===
Тривиально:
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>
Flyingleafe
116
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/37446»

Навигация