Введение. к курсовому проекту по дисциплине

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

“Структуры и алгоритмы обработки данных ”

на тему

ДЕРЕВЬЯ ПОИСКА (Search trees) ROPE

 

Выполнил студент	Жуковец Павел Евгеньевич
	Ф.И.О.

 

Группы	ИВ-15

 

Работу принял		доцент к.т.н. М.Г. Курносов
	подпись

 

Защищена		Оценка

 

Новосибирск – 2012
СОДЕРЖАНИЕ

ВВЕДЕНИЕ……………………………………….………………………………….3

1 Идея…………………………………………………………………………………4

2 Индексация…………………………………………………………………………6

Разбиение…………………………………………………………………………...7 4 Удаление и вставка……………………………………………………………….10

5 Оптимизация……………………………………………………………………...11

Балансировка……………………………………………………………..11

5.2 Прямое объединение малых строк……………………………………...13

Кэширование последней позиции………………………………………13

ЗАКЛЮЧЕНИЕ…………………………………………………………………….14

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………………15

1 Исходный текст программы……………………………………….…………….16

 

Введение

Большинство из нас так или иначе работает со строками. Этого не избежать — если ты пишешь код, ты обречен каждый день складывать строки, разбивать их на составные части и обращаться к отдельным символам по индексу. Мы давно привыкли что строки — это массивы символов фиксировнной длины, а это влечет за собой соответствующие ограничения в работе с ними.
Так, мы не можем быстро объединить две строки — для этого нам потребуется сначала выделить необходимое количество памяти, а потом скопировать туда данные из конкатенируемых строк. Очевидно, что такая операция имеет сложность порядка О(n), где n — суммарная длина строк.
Именно поэтому код:

 

string s = "";

for (int i = 0; i < 100000; i++) s += "a";

 

работает так медленно.
Хочешь выполнять конкатенацию гигантских строк быстро? Не нравится, что строка требует для хранения непрерывную область памяти? Надоело использовать буферы для построения строк?
Структура данных, которая нас спасет, называется Rope string, или «веревочная строка». Принцип ее работы очень прост и до него можно догадаться буквально из интуитивных соображений.

Идея

 

Пусть нам требуется сложить две строки:

Для классических строк мы просто выделим область памяти необходимого размера, в начало её скопируем содержимое первой строки, а в конец — второй:

Как уже упоминалось выше, сложность этой операции — O(n).

Но что если мы используем информацию о том что наша результирующая строка — это конкатенация двух исходных? И действительно, создадим объект который предоставляет интерфейс строки и хранит в себе информацию о своих компонентах — исходных строках:

Такой способ объединения строк работает за О(1) — нам нужно лишь создать объект-обертку для исходных строк. Так как этот объект — тоже строка, его можно комбинировать с другими строками для получения нужных нам конкатенаций:

Уже сейчас очевидно что наша структура — это двоичное дерево поиска, в листьях которого находятся элементарные составляющие нашей строки — группы символов. Так же очевидным становится способ перечисления символов строки — это обход дерева в глубину с последовательным перечислением символов в листьях дерева.