Изменения

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

Фибоначчиева куча

18 байт добавлено, 19:01, 21 мая 2015
cascadingCut
* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой [[Список |список ]] и помечаем ее родителя.
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.
Анонимный участник

Навигация