Представление в виде деревьев

Одна из самых популярных реализаций – Rope – предложена Hans Boehm, HP (автор одного из самых популярных консервативных сборщиков мусора для C) в 1980 годах.

• Строка представляется при помощи бинарного дерева.

· В каждой вершине ссылки на потомков или на память с символами (или на другую реализацию строк). Во внутренних вершинах вместе со ссылками хранят длины

строк, представленных левым и правым детьми (чтобы не пересчитывать).

• Структура неизменяемая, фрагменты дерева можно повторно использовать (получается направленный ациклический граф).

Можем ссылаться на одни и те же вершины.

Время от времени дерево нужно перебалансировать.

///Связка (rope) представляет неизменяемую последовательность символов. Длина (length) - это просто количество символов в последовательности. Большинство реализаций строк хранят все свои символы в памяти последовательно - друг за другом. Главное свойство связки - отсутствие этого ограничения, что позволяет фрагментам связки храниться независимо и дает возможность соединять их при помощи соединительных узлов (concatenation nodes). Подобная архитектура позволяет выполнять соединение строк гораздо быстрее, чем это делается для Java-объектов типа String. Реализация соединения для объектов String требует, чтобы строки, которые нужно объединить, были скопированы в новое место, что является операцией сложности O(n). Связка, с другой стороны, просто создает новый соединительный узел, а это операция сложности O(1). /////

Операции с этим деревом.

· Конкатенация мгновенная, создается новая вершина, указывающая на строку и добавку.

· Балансировка происходит путем вращения. Цель – не наименьшая высота, а примерно одинаковая длина строк в поддеревьях.

Конкатенация.

· При конкатенации длинной строки и короткой добавки, однако, дерево получается неоптимальным.

· Каждый раз перестраивать такое дерево невыгодно.

· Но можно, если пользуемся счетчиком ссылок (имеем право, т.к. циклов нет) и уверены, что ссылка единственная, не создать новое дерево, а перестроить, используя старые вершины. Если система программирования позволяет, конечно. Haskell, например, не позволит.

Занятно: при генерации текста высокоуровневой программы по её синтаксическому дереву полученный Rope (без балансировки) будет изоморфен дереву программы.