Изменения

==Возможность параллельного построенияСравнение с Link-Cut Tree==Операции Для Link-Cut деревьев (основанных на [[Splay-дерево|splay-деревьях]]), как и для <tex>\mathrm{Rake-Compress}</tex> деревьев, время работы операций <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> {{---}} <tex>O(\log{n})</tex>. В реальности <tex>\mathrm{RC}</tex> деревья оказываются медленнее, чем LC деревья. <br>Отличительной особенностью <tex>\mathrm{RC}</tex> деревьев является возможность параллельного построения: операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров.<br>Кроме этого, <tex>\mathrm{Rake-Compress}</tex> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.

* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических <tex>\mathrm{Rake-Compress}</tex> деревьев в случае отсутствия ограничения на степени вершин]