188
правок
Изменения
Новая страница: «Задача, которая решается с помощью '''динамических деревьев''' (англ. ''dynamic tree''), формулируе...»
Задача, которая решается с помощью '''динамических деревьев''' (англ. ''dynamic tree''), формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* некоторый запрос относительно структуры дерева.
Примером последней операции может быть запрос "достижима ли вершина <tex>u</tex> из <tex>v</tex>?", "сколько ребер на кратчайшем пути из <tex>u</tex> в <tex>v</tex>?" или "какова сумма номеров вершин, которые находятся в поддереве вершины <tex>u</tex>?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время <tex>O(\log{n})</tex>.
__TOC__
==Описание==
'''Rake-Compress Tree''' {{---}} структура данных, которая хранит [[Дерево, эквивалентные определения|лес деревьев]] и поддерживает следующие операции:
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
==См. также==
* [[Link-Cut Tree]]
==Источники информации==
[[Категория: Алгоритмы и структуры данных]]
* добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* некоторый запрос относительно структуры дерева.
Примером последней операции может быть запрос "достижима ли вершина <tex>u</tex> из <tex>v</tex>?", "сколько ребер на кратчайшем пути из <tex>u</tex> в <tex>v</tex>?" или "какова сумма номеров вершин, которые находятся в поддереве вершины <tex>u</tex>?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время <tex>O(\log{n})</tex>.
__TOC__
==Описание==
'''Rake-Compress Tree''' {{---}} структура данных, которая хранит [[Дерево, эквивалентные определения|лес деревьев]] и поддерживает следующие операции:
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
==См. также==
* [[Link-Cut Tree]]
==Источники информации==
[[Категория: Алгоритмы и структуры данных]]
