Динамические деревья: различия между версиями

Несколько исследований были посвящены эффективности различных структур данных на основе динамических деревьев; в большинстве случаев самыми быстрыми оказывались ST-деревья, реализованные на базе косых деревьев. В частности, Фредериксон обнаружил, что при выполнении операций с динамическими деревьями в алгоритме нахождения максимального потока топологическим деревьям требуется почти на 50% больше времени, чем ST-деревьям на основе косых деревьев [8]. Акар и коллеги [ ] показали, что RC-деревья оказываются существенно более медленными по сравнению с ST-деревьями на основе косых деревьев в случае, если большинство операций представляют собой связывание и отрезание (например, в алгоритмах обработки сетевых потоков), но быстрее в случаях, когда преобладают запросы и обновление значений. Причина в том, что при перекосе структура ST-деревьев меняется даже в процессе запроса, тогда как RC-деревья остаются неизменными.

Тарьян и Вернек [ ] представили экспериментальное сравнение нескольких структур данных на основе динамических деревьев. Для произвольных последовательностей операций связывания и отрезания косые ST-деревья демонстрируют максимальную скорость; за ними следуют косые ET-деревья, самонастраивающиеся верхушки деревьев, верхушки деревьев для наихудшего случая и RC-деревья. Подобные же данные об относительной эффективности были получены для более реалистичных последовательностей операций, за исключением таких, в которых число запросов существенно превышало число структурных операций; в таком случае самонастраивающиеся структуры данных оказываются более медленными по сравнению с RC-деревьями и верхушками деревьев для наихудшего случая. В этом же экспериментальном исследовании рассматривалась «очевидная» реализация ST-деревьев, явным образом представляющая лес и требующая линейного времени на операцию в наихудшем случае. В силу ее простоты она оказывается заметно более быстрой, чем структуры данных со временем O (log n), для запросов и обновлений, связанных с путями – за исключением случаев, когда длина путей измеряется сотнями вершин. В случаях, когда лес имеет очень большой диаметр или когда имеется необходимость в сборе информации по деревьям, а не только по путям, более полезными оказываются более изощренные решения.