Реализация структуры данных Rope с использованием бинарных деревьев поиска (Splay Tree)

Question

В стандартной реализации структуры данных Веревка с использованием splay-деревьев узлы будут упорядочены в соответствии со статистикой рангов, измеряющей положение каждого из них в начале строки, поэтому ключи обычно находятсяв бинарном дереве поиска не будет иметь значения, не так ли?

Я спрашиваю, потому что клавиши, показанные на рисунке ниже (спасибо Википедии!), Являются буквами, которые, вероятно, станут неуникальными, если число узлов превысит длину выбранного алфавита.Не лучше ли использовать целые числа или вообще не использовать ключи?

Отдельно, может ли кто-нибудь указать мне на хорошую реализацию логики для пересчета статистики рангов после каждой операции?

Предположительно, если индекс для разбиения попадает в подстроку, присоединенную к определенному узлу, скажем, между "Hel" и "llo_" на узле E выше, вы удалили бы подстроку из E, разделив ееи присоединить его как двоих потомков Е. Правильно?

Наконец, после определенного числа таких операций, у дерева, как я полагаю, может оказаться столько листьев, сколько букв.Каков наилучший способ отслеживать это и обрезать дерево (путем объединения подстрок) по мере необходимости?

Спасибо!

Answer 1

Для чего бы то ни было, вы можете реализовать Rope с помощью Splay Trees, прикрепив подстроку к каждому узлу двоичного дерева поиска (а не только к конечным узлам, как показано выше).

Ранг каждого узла - это его размер плюс размер его левого поддерева.Но при повторном вычислении рангов во время операций воспроизведения необходимо помнить и о переходе по ветви node.left.right.

Если каждый узел записывает ссылку на подстроку, которую он представляет (см. Саму подстроку), все работает быстрее.Таким образом, когда операция разделения попадает в существующий узел, вам просто нужно изменить атрибуты узла, чтобы отразить правую часть подстроки, которую вы хотите разделить, затем добавить другой узел, чтобы представить левую часть, и объединить его с левым поддеревом.

Сделано, как указано выше, каждый узел записывает (в дополнение к своим атрибутам left, right, parent и т. Д.) Свой ранг, размер (в символах) и местоположение первого символа, который он представляет в строке, которую вы пытаетесьмодифицировать.Таким образом, вы фактически никогда не изменяете исходную строку: вы просто выполняете свои операции над битами дерева и воспроизводите окончательную строку, когда будете готовы, пройдя ее по порядку.