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

Первая эффективная структура данных для динамического дерева была разработана Слейтором и Тарьяном; она известна как ST-дерево [13, 14], дерево со связыванием и отрезанием или просто динамическое дерево. Она была предназначена для представления корневых деревьев, однако пользователь может изменить корень дерева при помощи операции выворачивания (evert). Эта структура данных разбивает каждое входное дерево на пути с непересекающимися вершинами; каждый путь представляется в виде бинарного дерева поиска, в котором вершины появляются в симметричном порядке. Затем бинарные деревья соединяются в соответствии с тем, как пути соотносятся друг с другом в структуре леса. Точнее говоря, корень бинарного дерева становится средним потомком (в рамках структуры данных) родительского дерева (в лесу) самой верхней вершины соответствующего пути. В собственном бинарном дереве вершина может иметь не более двух потомков (левого и правого), однако при этом у нее может быть произвольное число средних потомков. Путь, включающий вершину (qlifcba на рисунке), должен быть открытым; он представлен в виде самого верхнего бинарного дерева. Все запросы, касающиеся путей, будут относиться к этому пути. Операция открытия (expose) может использоваться для того, чтобы сделать любую вершину частью открытого пути.

ST-дерево (согласно алгоритму из [  ]). В левой части представлено исходное дерево с корнем в вершине a, уже разбитое на пути; в правой части – текущая структура данных. Дуги, изображенные сплошными линиями, соединяют вершины одного и того же пути; изображенные пунктиром – соединяют разные пути