Лекция: Представление в виде деревьев.
Одна из самых популярных реализаций – Rope – предложена Hans Boehm, HP (автор одного из самых популярных консервативных сборщиков мусора для C) в 1980 годах.
- Строка представляется при помощи бинарного дерева.
· В каждой вершине ссылки на потомков или на память с символами (или на другую реализацию строк). Во внутренних вершинах вместе со ссылками хранят длины
строк, представленных левым и правым детьми (чтобы не пересчитывать).
- Структура неизменяемая, фрагменты дерева можно повторно использовать (получается направленный ациклический граф).
Можем ссылаться на одни и те же вершины.
Время от времени дерево нужно перебалансировать.
///Связка (rope) представляет неизменяемую последовательность символов. Длина (length) — это просто количество символов в последовательности. Большинство реализаций строк хранят все свои символы в памяти последовательно — друг за другом. Главное свойство связки — отсутствие этого ограничения, что позволяет фрагментам связки храниться независимо и дает возможность соединять их при помощи соединительных узлов (concatenation nodes). Подобная архитектура позволяет выполнять соединение строк гораздо быстрее, чем это делается для Java-объектов типа String. Реализация соединения для объектов String требует, чтобы строки, которые нужно объединить, были скопированы в новое место, что является операцией сложности O(n). Связка, с другой стороны, просто создает новый соединительный узел, а это операция сложности O(1)./////
Операции с этим деревом.
· Конкатенация мгновенная, создается новая вершина, указывающая на строку и добавку.
· Балансировка происходит путем вращения. Цель – не наименьшая высота, а примерно одинаковая длина строк в поддеревьях.
Конкатенация.
· При конкатенации длинной строки и короткой добавки, однако, дерево получается неоптимальным.
· Каждый раз перестраивать такое дерево невыгодно.
· Но можно, если пользуемся счетчиком ссылок (имеем право, т.к. циклов нет) и уверены, что ссылка единственная, не создать новое дерево, а перестроить, используя старые вершины. Если система программирования позволяет, конечно. Haskell, например, не позволит.
Занятно: при генерации текста высокоуровневой программы по её синтаксическому дереву полученный Rope (без балансировки) будет изоморфен дереву программы.