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

При использовании стандартных сбалансированных бинарных деревьев поиска (например, красно-черных деревьев) ST-деревья поддерживают операции динамического дерева с амортизированным временем исполнения <math>O(log^2 n)</math>. Это значение может быть улучшено до амортизированного времени O(log n) при помощи локально смещенных бинарных деревьев поиска, и до O(log n) в наихудшем случае – при помощи глобально смещенных бинарных деревьев поиска. Однако смещенные деревья поиска [5] сами по себе достаточно сложны. Более практичная реализация ST-деревьев использует [[косые деревья]] – самонастраивающиеся бинарные деревья поиска, поддерживающие все операции динамического дерева с амортизированным временем исполнения O(log n) [14].

Недостаток топологических деревьев и RC-деревьев заключается в том, что лес, на основе которого они строятся, должен иметь вершины с ограниченными (константными) степенями, чтобы гарантировать время O(log n) на исполнение операции. И хотя ST-деревья не имеют подобного ограничения при сборе информации по путям, им необходимы ограниченные степени для сбора информации по деревьям. Ограничения по степени могут быть обойдены при помощи «растроения» исходного леса (замены вершины с высокой степенью серией вершин с низкими степенями [9]), но при таком подходе возникают несколько специальных случаев.