Rake-Compress деревья — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Задача, которая решается с помощью '''динамических деревьев''' (англ. ''dynamic tree''), формулируе...»)
 
Строка 10: Строка 10:
 
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
 
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
 
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
 
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
 +
<table align="center"><tr>
 +
<td>[[Файл:Rctree-rake.png|x180px|thumb|Операция <tex>\mathrm{Rake}</tex>]]</td>
 +
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
 +
</tr></table>
 +
Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Вернеком.
  
 
==См. также==
 
==См. также==
Строка 15: Строка 20:
  
 
==Источники информации==
 
==Источники информации==
 
+
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
 +
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
 +
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction
 +
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Версия 14:39, 10 апреля 2016

Задача, которая решается с помощью динамических деревьев (англ. dynamic tree), формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:

  • добавить ребро [math](u, v)[/math]. Вершина [math]u[/math] должна быть корнем некоторого дерева. Вершины [math]u[/math] и [math]v[/math] должны находиться в разных деревьях,
  • удалить ребро [math](u, v)[/math]. Ребро [math](u, v)[/math] должно присутствовать в графе,
  • некоторый запрос относительно структуры дерева.

Примером последней операции может быть запрос "достижима ли вершина [math]u[/math] из [math]v[/math]?", "сколько ребер на кратчайшем пути из [math]u[/math] в [math]v[/math]?" или "какова сумма номеров вершин, которые находятся в поддереве вершины [math]u[/math]?". Можно легко реализовать структуру данных, которая будет выполнять данные операции за время [math]O(n)[/math], где [math]n[/math] — количество вершин в графе. Динамические деревья нужны для того, чтобы обрабатывать запросы более эффективно. В частности, все предложенные операции возможно выполнять за время [math]O(\log{n})[/math].

Описание

Rake-Compress Tree — структура данных, которая хранит лес деревьев и поддерживает следующие операции:

  • [math]\mathrm{Rake}[/math] — все листья дерева сжимаются к своим родителям,
  • [math]\mathrm{Compress}[/math] — выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
Операция [math]\mathrm{Rake}[/math]
Операция [math]\mathrm{Compress}[/math]

Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Вернеком.

См. также

Источники информации