Изменения

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

Rake-Compress деревья

845 байт добавлено, 14:48, 10 апреля 2016
Нет описания правки
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
</tr></table>
Входными данными для алгоритма Rake-Compress является лес корневых деревьев. К нему поочередно применяются операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> до тех пор, пока существует хотя бы одна живая вершина.<br>Во время каждой из этих операций выбирается некоторое множество попарно несмежных вершин, которое сжимается к своим родителям. После каждой операции лес сохраняется в специальном виде, что в дальнейшем дает возможность отвечать на запросы о структуре леса.<br>Современная реализация Rake-Compress деревьев была предложена Р. А. Тарьяном и Р. Ф. Вернеком.
==См. также==
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction
 
[[Категория: Алгоритмы и структуры данных]]
188
правок

Навигация