Графовые машины: Вычислительная сила и применение к сбалансированным деревьям тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РГБ

29

марковский ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

\№\ Ш5

Механико-математический факультет

На правах рукописи УДК 510.52

ШВАЧКО Константин Витальевич

ГРАФОВЫЕ МАШИНЫ: ВЫЧИСЛИТЕЛЬНАЯ СИЛА И ПРИМЕНЕНИЕ К СБАЛАНСИРОВАННЫМ ДЕРЕВЬЯМ

Специальность 01.01.06 Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1995

Работа выполнена на кафедре математической логики и теории алгоритмов механико-математического ф акультета Московского государственного университета им. М.В. Ломоносова

Научный руководитель:

доктор физико-математических наук, профессор Семенов А.Л.

Официальные оппоненты:

- доктор физико-математических наук, профессор Тайцлин М.А.

- кандидат физико-математических наук Верещагин Н.К.

Ведущая организация:

Институт Системного Анализа РАН

Защита диссертации состоится " /6» ¿¿/-¿'-/-¿с/ 1995 г_ в 16 час. 05 мин. на заседании диссертационного совета Л.053.05.05 при МГУ по адресу: 119899, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 1995 г.

Ученый секретарь диссертационного совета

Д.053.05.05 при МГУ д.ф.-м.н., профессор

Общая характеристика работы

Актуальность темы. Проблема сравнения вычислительной силы двух модификаций графовых машин - машин Колмогорова - Успенского (МКУ), построенных А.Н.Колмогоровым и В.А.Успенским в 1958 году, и машин с модифицируемой памятью (БММ), предложенных А.Шенхаге в 1970, - в классе реального времени была впервые поставлена А.Шенхаге в 1980 году.

Считается, что МКУ являются более слабой моделью, чем БММ, однако доказать этого до настоящего времени не удалось.

В работе рассматриваются древесные машины, являющиеся модификациями графовых машин, которые могут считаться частными случаями МКУ, и исследуется их вычислительная сила по отношению к БММ.

Древесные машины являются весьма мощным вычислительным инструментом. Они часто используются при решении задач из области структур данных.

Классической задачей теории структур данных является задача построения динамического словаря. Под динамическим словарем понимается множество объектов, называемых ключами, вместе с тремя операциями: поиска, вставки и удаления ключей в словаре.

Стандартной структурой данных для построения динамического словаря являются сбалансированные деревья. В литературе рассматривается три основных вида сбалансированных деревьев. Это АВЛ-деревья (Г.М.Адельсон-Вельский и Е.М.Ландис, 1962), 2-3-деревья (Дж.Хопкрофт, 1970) и В-деревья (Р.Байер, 1972). Все три структуры данных гарантируют логарифмическое время выполнения трех операций для словарей в древесной вычислительной модели.

При построении таких деревьев считается, что все ключи в словаре имеют одинаковый вес (размер, длину), что может приводить к значительной потере памяти при представлении множества ключей переменной длины.

, Динамические словари с ключами переменной длины до настоящего времени систематически не рассматривались. В настоящей работе предлагается новая структура данных, обобщающая 2-3-деревья и В-деревья для случая ключей переменной длины.

Цель работы. Исследовать вычислительную силу древесных машин по отношению к БММ в классе реального времени.

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

Научная новизна. В диссертации получены следующие основные результаты.

1. Определены три модификации древесных машин: слабые древесные машины (СлДМ), сильные древесные машины (СиДМ) и древесные машины Тьюринга (ТТМ). Построен язык Ь запросного типа. Доказано, что Ь распознается в реальное время на вММ.

2. Показано, что ни одна из трех введенных моделей - СлДМ, СиДМ, ТТМ - не распознает запросный язык в реальное время.

3. Сформулировано два новых условия сбалансированности деревьев, на основании которых определены классы 5(6)-деревьев и £>5(6)-деревьев, предназначенные для представления динамических словарей с ключами переменной длины.

4. Исследована взаимосвязь между введенными классами сбалансированных деревьев. В частности показано, что 2-3-деревья и В-деревья являются частными случаями 5(0)-деревьев и 1)5(0)-деревьев, а также установлено, что 5(6)-деревья образуют сжимающуюся иерархию относительно параматра 6.

5. Определена мера емкостной сложности деревьев Д(Т), называемая заполненностью. Построена нижняя оценка заполненности 5(6)- и П5'(Ь)-деревьев, которая показывает, что новые деревья обладают оптимальной заполненностью:

Д(Т) > 1 - £ где г обратно пропорционально Ь.

6. Разработаны логарифмические по времени алгоритмы поиска, вставки и удаления ключей в словаре. Доказана корректность алгоритмов.

Все основные результаты работы являются новыми, их достоверность подтверждается подробными доказательствами.

Научно-практическая ценность работы. Результаты диссертации могут найти применение в теории алгоритмов (в частности, для построения нижних оценок сложности вычислений), а также в теории структур данных.

Практическое применение сбалансированных деревьев в системах хранения и управления большими объемами данных (в частности, в системах баз данных) позволяет существенно снизить затраты на хранение и использование информации.

Апробация. Материалы диссертации докладывались на ряде семинаров и конференций, в том числе:

• на колмогоровском семинаре кафедры математической логики механико-математического факультета МГУ,

• на семинаре по теоретической информатике института программных систем РАН,

• на 16-м международном симпозиуме "Математические основания информатики" (Mathematical Foundations of Computer Science), 9-13 сентября 1991 года, Казимерш-Дольный, Польша.

• на 4-й международной конференции "Теория баз данных" (Database Theory), 14-16 октября 1992, Берлин, Германия.

• на международном конгрессе "Компьютерные системы и прикладная математика" (Computer Systems and Applied Mathematics), 19-23 июля 1993 года, Санкт-Петербург.

• на XI международной Конференции "Логика, методология и философия науки", 11-15 апреля 1995, Обнинск.

Практическое апробирование алгоритмов для 5(1)-деревьев осуществлено при реализации языка программирования STARSET, в котором проблема поддержки больших упорядоченных множеств играет ключевую роль.

Публикации. Основные результаты диссертации опубликованы в работах 1-5.

Структура диссертации. Диссертация состоит из введения, двух глав и списка литературы из 53 названий. Общий объем диссертации 167 страниц.

Во введении показана актуальность работы, дан краткий исторический обзор результатов, связанных с данной темой, сформулированы основные результаты.

В главе 1 исследуется вычислительная сила древесных машин по отношению к SMM в реальном времени.

В главе 2 определяется новый тип сбалансированных деревьев и изучаются основные свойства этой структуры данных.

Содержение диссертации.

1.1. Важную роль в теории алгоритмов играют графовые машины (pointer machines - ГМ). Известны различные модификации графовых машин. Общее у этих машин то, что их память является графом, а шаг работы машины состоит в преобразовании части этого графа, причем размер выделяемой части ограничен константой, не зависящей от длины входа машины. Приведем неформальное определение графовых машин.

Пусть фиксировано конечное множество "направлений". Граф памяти ГМ обладает тем свойством, что каждому его ребру, соединяющему данную вершину с соседней, однозначно соответствует одно из направлений. Одна вершина графа выделена и называется центральной. Остальные вершины достижимы из центра по путям, определяемым последовательностями направлений. В процессе вычисления граф (состояние памяти) модифицируется в зависимости от входа и состояния памяти по определенным правилам. А именно, на каждом шаге выделяется г-окрестность центра и заменяется на некоторый другой граф. При этом указывается "функция склейки", определяющая как надо соединять вершины вне удаленной r-окрестности с новыми вершинами графа.

Первый пример графовых машин был построен в 1958 году А.Н.Колмогоровым и В.А.Успенским. Граф памяти машин Колмогорова - Успенского (МКУ) называется Б-комплексом и является неориентированным графом с вершинами, помеченными символами алфавита Б.

Другим примером графовых машин являются машины с модифицируемой памятью (SMM), предложенные А.Шенхаге в 1970. Состояния памяти SMM представляются Д-структурами, являющимися ориентированными графами. Направления в них задаются пометками ребер. МКУ и SMM являются основными модификациями ГМ, рассматриваемыми в литературе.

Естественно, возникает вопрос о сравнении вычислительной

силы моделей как внутри класса графовых машин, так и по отношению к другим известным моделям.

Определение. Говорят, что машина М\ моделирует машину М2, если обе машины реализуют одну и ту же функцию. Пусть Mi моделирует М2. Пусть t\ < ti < ... < t, есть последовательность шагов в процессе вычисления машины Mi на входе г, в которые она либо читает входной символ, либо пишет выходной символ, либо останавливается, и пусть Ti < Тг < ... < г, аналогичная последовательность шагов вычисления машины Mi на том же входе х. Говорят, что Mi моделирует М2 в реальное время, если существует константа с, такая что для всякого входного слова х последовательности выделенных шагов (i,-) и (г,) связаны условием, что для всех г (1 < i < s)

Tt+i ~П< c(ti+i - U)

Будем говорить, что машины класса Сч моделируются машинами класса Ci в реальное время, если для всякой машины Mi из Ci найдется машина Mi из Ci, моделирующая М2 в реальное время. Два класса машин эквивалентны в реальное время, если один класс моделируется другим в реальное время и наоборот. Класс машин С2 слабее, класса машин Ci, если машины Ci моделируются машинами Ci в реальное время, а машины С\ машинами Ci не моделируются.

Легко видеть, что SMM не слабее МКУ, т.е. всякое вычисление МКУ моделируется в реальное время на SMM. Обратная задача является трудной открытой проблемой. Суть ее в том, что у вершин графа памяти SMM неограничена их входная степень, а в МКУ входная степень вершин равна выходной и, следовательно, ограничена числом направлений. Гипотеза такова, что МКУ слабее SMM.

По отношению к другим вычислительным моделям силу ГМ характеризуют следующие три результата. Д.Ю.Григорьев доказал, что многоленточные машины Тьюринга (ТМ) не могут моделировать графовые машин в реальное время. Этот результат справедлив для любой пары модификаций ТМ и ГМ. С другой стороны, А.Шенхаге показал, что ТМ моделируются на SMM в реальное время. Кроме того А.Шенхаге доказал, что SMM эквивалентны наиболее слабой модификации равнодоступных адресных машин, а именно, RAM с единственной арифметической операцией - прибавлением единицы.

1.2. Мы рассматриваем две модификации графовых машин с древесной памятью. В обеих моделях память машины является ориентированным деревом, из каждой вершины которого выходит не более к ребер, помеченных натуральными числами из {0,1,..., к — 1} так, что все пометки ребер, выходящих из одной вершины, различны.

В первой модели вершины дерева не помечены. Такие деревья будем называть ¿-деревьями, а соответствующие им машины - слабыми древесными машинами (СлДМ). В другой рассматриваемой модели вершины дерева помечены буквами конечного алфавита Б. Такие деревья называются (Б, &)-деревьями, а соответствующие машины - сильными древесными машинами (СиДМ).

Отметим, что СлДМ и СиДМ являются упрощением МКУ в том смысле, что входная степень каждой вершина ориентированного дерева ограничена 1, в то время как у В-комплексов входная степень вершин ограничена мощностью алфавита Б.

Кроме того, будут рассмотрены древесные машины Тьюринга, которые снабжены обычной односторонней входной лентой, а их рабочая лента выполнена в виде дерева. Вершины дерева есть ячейки памяти, в которых машина может записывать буквы из конечного алфавита Е. Все остальное для ТТМ определяется так же, как и для обычных машин Тьюринга.

1.3. Язык Ь называется запросным, если содержащиеся в нем слова имеют вид где В и ги - слова в некотором алфавите £, а символ $ не принадлежит Интуитивно, часть В слова из Ь имеет смысл кода некоторой базы данных, а часть ш имеет смысл запроса к этой базе.

Рассмотрим следующий запросный язык:

т = и{Ьо»@ • ■ МЬ^хфуЩЪ <= {0,1}10^, X, у € {0,1}", 6Г = Ьу }

п

Последовательность В = Ьо»@.. (базовый сегмент) зада-

ет разбиение множества всех двоичных слов длины п на с1 классов эквивалентности, х и у - представители двух классов. Слово 6 Ь(с1) тогда и только тогда, когда х и у принадлежат одному классу эквивалентности. Обозначение: х ~ у.

Определение. Говорят, что язык Ь распознается машиной М в реальное время (врв), если существует константа с, что для

каждого входного слова х, машина М делает не более с шагов между любыми двумя последовательными чтениями входа х.

Известно, что язык ¿(2) распознается врв на всех из рассматриваемых графовых машинах и на ТТМ. Известно также, что £(2) не распознается врв на многоленточных ТМ. Далее будет рассмотрен язык Ь = Ь{2"/2), который тоже не распознается врв на ТМ, и который гипотетически должен разделить вычислительную силу МКУ и вММ.

Теорема 1. Существует БММ, распознающая Ь врв.

Наша задача показать, что язык Ь не распознается врв на машинах с древесной структурой памяти при некотором дополнительном ограничении на работу машин, распознающих запросные языки. Важно отметить здесь, что Б ММ с аналогичным дополнительным ограничением все равно позволяет распознавать Ь врв.

1.4. Пусть ГМ М распознает Ь. Обозначим 5д/(5ш) состояние памяти (граф) машины М, которое принимает М после прочтения части входа Вю, где \ю\ < 2п (символы # не учитываются при подсчете длины).

Определение. &(*#»#) = | ^ ~ У

Продолжим на более короткие последовательности. Пусть £в определено для всех слов длины т (т < 2га), тогда для слов ги длины = т — 1 положим

Последовательность есть набор возможных результатов

работы М на различных продолжениях входа Вт.

Лемма (Основная). Пусть ГМ М распознает язык Ь. Пусть В - базовый сегмент, и и^, т2 - слова, длины которых не превосходят 2п. Тогда

Бм{Вю 1) = Бм(Ви)2) => 1) =

Лемма (Комбинаторная). Существует такое разбиение В множества двоичных слов длины п на <1 = 2"/2 классов эквивалентности, что

1. Уи)1и)2(|и),-| <пк,ц} 1 ^ и)2 £в(ги1) Ф ^в(^г))

2. Уи)(|гу| = п => Уг<1«2(|и«| < "/2 к «1 ф и2 => £5(^1) ф

2)))

Доказательство основных результатов первой главы опирается на две эти леммы.

1.5. Пусть в момент времени t состояние памяти машины М характеризуется графом 5д/(0 =< V(i),E(t) >, где V(t) и E(t) множества, соответственно, вершин и ребер графа. Будем говорить, что шаг t машины М не является существенным, если выполняется следующее условие:

V(t + 1) С V(<) & E(t + 1) С E(t)

в противном случае шаг t называется существенным. Будем называть шаг t машины М движением, если на этом шаге меняется положение центральной вершины графа.

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

Будем говорить, что ГМ распознает запросный язык, если она распознает этот язык и при работе на любом входном слове выполняется следующее

Ограничение: машина не производит существенных шагов на временном интервале I, соответствующем запросной (правой) части входного слова запросного языка.

Неформально это означает, что ГМ может производить любые действия при построении базы данных - левой части В слова запросного языка, но при обработке запроса w ничего достраивать нельзя. Для СлДМ на временном интервале I разрешается производить только движения, а СиДМ могут менять пометки вершин и двигаться.

1.8. Теорема. СлДМ, распознающая L и удовлетворяющая Ограничению, не может работать врв.

Из доказательства теоремы 1, следует, что можно построить SMM, распознающую L врв, которая делает единственный существенный шаг на временном интервале I, соответствующем части входа Этот единственный шаг состоит в построении ровно

одной новой вершины в графе Sm(B)-

Для СлДМ мы можем показать, что даже если им разрешить совершать константное число существенных шагов, то этого не будет достаточно для распознавания L.

Ослабленное ограничение: на временном интервале I, соответствующем запросной части входного слова запросного языка,

все шаги машины, за исключением быть может конечного их числа, не являются существенными.

Следствие теоремы. СлДМ, распознающая Ь и удовлетворяющая Ослабленному ограничению, не может работать врв.

1.7. Вообще говоря, СлДМ и СиДМ являются эквивалентными по вычислительной силе моделями. Однако при введенном выше ограничении СиДМ наделены большими возможностями при обработке запросной части входа, поэтому доказательство основного результата для СиДМ требует дополнительных усилий.

Пусть Б - алфавит пометок вершин графа памяти, к - степень ветвления вершин, а г - показатель локальности СиДМ.

Пусть некоторая СиДМ М распознает Ь и удовлетворяет Ограничению. Пусть также по прочтении входа Вт машина М обозревает окрестность О (Б,к)-дерева Зм{Вш). Рассмотрим множество С {0,1}*, состоящее из слов и, по прочтении

которых М делает движение.

Нам удобно представлять множество ]¥(го) в виде бинарного дерева, в котором число листьев равно Саг(1(1¥(и})), ребра помечены 0, 1, и каждый путь из корня в лист соответствует некоторому и £ \У(ю). Число внутренних вершин (не листьев) дерева \У(ги) назовем его площадью.

Лемма. Пусть М распознает Ь и удовлетворяет Ограничению, базовый сегмент В таков, существование которого гарантирует КЛ, слово ш имеет длину |гу| < |п— |Б|. Тогда

1. Высота дерева не превосходит |Б|.

2. Ветвление каждой вершины ^(ги) либо 0, либо 2.

3. Площадь дерева И^м) не превосходит |Б|.

4. Число листьев \¥(го) есть Саг(1(Ш(т)) и не превосходит к.

5. Если площадь дерева Иг(и>) равна в, а число листьев равно д, то д = в + 1. Для площади я выполнено неравенство в < тг'гс(|Б|, к — 1).

Рассмотрим дерево входов Т(2п) машины М на временном интервале I, т.е. полное бинарное дерево высоты 2га. Всякий путь в этом дереве соответствует некоторому запросу для М на интервале I.

Вычисление М на различных входах можно представлять себе следующим образом. Отождествим изначально дерево с поддеревом Т(2п) так, чтобы корни И^(А) и Т(2п) совпали, а отождествляемые ребра имели одинаковые пометки. Вершины Т(2п), отождествившиеся с листьями отметим крестиком.

Далее каждая вершина, отмеченная крестиком, должна стать корнем поддерева, отождествляемого с соответствующим Ш{и), для и £ У/(\). Вершины полученного поддерева, отождествленные с листьями IV(и), также помечаются крестиками, которые в свою очередь должны стать корнями ... и т.д. В результате мы получим покрытие Т(2п) деревьями вида IV(ти). Вершины, помеченные крестиками, будут соответствовать моментам движения машины. Поскольку нас интересует общее число различных движений машины, то мы стремимся оценить снизу число крестиков в дереве Т(2тг) или, иначе, мощность покрытия Т(2п).

Лемма (о Покрытии). Дано конечное множество деревьев Ж' (1 < г < р) таких, что каждая вершина дерева \\т{ имеет ветвление либо 0, либо 2, а площадь каждого Wi не превосходит е. Тогда мощность всякого покрытия полного бинарного дерева Т(К) высоты Н деревьями вида не меньше (2Л+1 — 1)/в.

Из этого следует

Теорема. Никакая СиДМ, распознающая Ь и удовлетворяющая Ограничению, не может работать врв.

1.8. Каждый шаг ТТМ, связанный с рабочей памятью, является либо движением, т.е. переходом к соседней ячейке памяти, либо записью нового символа в текущую ячейку, либо переменой состояния машины. Будем говорить, что на временном интервале <7 совершался существенный шаг, если машина за время 3 побывала в одной из ячеек дважды.

Ограничение. ТТМ, распознающая не должна совершать существенных шагов на временном интервале I, соответствующем части входа

Ограничение для ТТМ означает, что ей запрещается двигаться в направлении корня дерева памяти - той ячейки, находясь в которой машина начинает работу на интервале I.

ТТМ обладает способностью "запоминать" с помощью состояний С} некоторую конечную информацию о предыдущих вычислениях и "хранить" ее в течение длительного времени. Это расширяет возможности ТТМ по сравнению с СлДМ и СиДМ при работе на запросной части входа.

Пусть некоторая ТТМ М распознает Ь и удовлетворяет Ограничению. Под Зм{Вю) мы понимаем далее следующее дерево. Его вершинами являются ячейки памяти, составляющие поддерево дерева памяти с корнем в ячейке, в которой находится М после прочтения входа Вьи. Отметим, что ячейки памяти, ни разу не посещавшиеся М в процессе вычисления, пусты. Будем считать, что они не входят в Зм{Вю). Ребра в Бм(Вю) связывают соседние ячейки памяти М. Вершины Зм(Вги) помечены теми символами, которые записаны в соответствующих ячейках.

Пусть по прочтении входа В го машина М, находясь в состоянии д 6 Я, обозревает ячейку р , в которой записан символ а € Е. Тройку К =< (х, а,д > назовем конфигурацией машины. Основная лемма для ТТМ формулируется следующим образом.

Лемма (Основная). Пусть ТТМ М распознает Ь и удовлетворяет Ограничению. Пусть по прочтении входов Вхих и Вхи2 конфигурации М, соответственно, К\ =< ^1,01,91 > и К2 =< /¿2,02, ?2 >■

Тогда Зм(Вьи 1) = & Я1 = Чг =>■ 1) 7 £в(и>2)-'

Используя О Л и К Л, мы хотим оценить число различных движений, совершаемых машиной на разных входах. Трудность состоит в том, что ТТМ на разных входах ги 1 и ги2 может совершать одинаковое движение, находясь при этом в несовпадающих состояниях q\ ф

Пусть по прочтении слов и>1,..., гср конфигурации машины М отличаются только состояниями К =< ц, а, >, д,- ф qj при { ф 3, где г',У=

Для каждого рассмотрим множество Иг(и){) С {0,1}*, состоящее из слов, по прочтении которых машина М совершает движение.

Положим К(/х, а) = и»{?«} * У(/л, а) будем представлять

себе в виде куста, состоящего из деревьев УУ(го{), корни которых помечены состояниями д,-.

Лемма.

1. Высота куста У((х,а), равная максимуму высот составляющих его деревьев, не превосходит |£|.

2. Площадь а), равная сумме площадей составляющих его деревьев, не превосходит |Е||ф|.

Кусты У(ц, а) покрывают дерево Т(2п) входов для М на временном интервале / так же, как деревья Ж(и') покрывали дерево

входов при работе СиДМ.

Лемма (о Покрытии). Мощность покрытия Т(Л) кустами площади, не превосходящей в, больше или равна (2Л+1 — 1)/«.

Теорема. ТТМ М, распознающая Ь и удовлетворяющая Ограничению, не может работать врв.

2. Древесные машины широко применяются в теории структур данных, одной из классических задач которой является проблема построения динамического словаря.

Под динамическим словарем понимается структура данных, предназначенная для хранения линейно упорядоченных множеств объектов, называемых ключами, вместе с алгоритмами, обеспечивающими поиск ключей, их вставку и удаление. Основным подходом к решению этой задачи является построение сбалансированных деревьев таких, как АВЛ-деревья, 2-3-деревья и наиболее общие В-деревья. В работе представлена новая структура данных, основанная на эффективном принципе балансировки деревьев по весу, обобщающая понятие В-дерева, являющаяся почти оптимальной по памяти и логарифмической по времени выполнения основных операций.

2.1. Пусть - упорядоченное множество ключей с ве-

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

Рассматриваются деревья следующего вида:

1. объект Л, называемый пустым деревом, есть дерево;

2. если ¿1,..., кт € К и То,...,Тт - деревья, то последовательность < То,кх,Т1,... ,кт,Тт > является деревом.

Для каждой вершины 5 =< £о, 51,..., &т,5т > дерева Т пусть ¿(5) = {к\,..., кт} обозначает множество ключей, содержащихся в вершине 5, а К(Т) - множество ключей, содержащихся во всех вершинах дерева Т.

Степенью ветвления вершины называется количество ее непосредственных потомков. Порядком вершины 5 называется число |&(5)| ключей в 5.

Натуральное число q называется порядком дерева Т, если порядок каждой его вершины, отличной от корня, больше или равен Ч-

Дерево Т называется структурированным, если

1. каждая вершина Т является либо внутренней (т.е. ее степень ветвления на единицу больше ее порядка), либо листом;

2. все пути в Г из корня в листья имеют одинаковую длину;

3. для каждой вершины S =< So, Si,..., km, Sm > дерева T

¡i¿... L¡m and

Vi(l < i < m

(Vfc € K(Si-i))(W e K(Si))(k¿¡i¿k'))

Определение. Пусть (К, ¿) - упорядоченное множество ключей. Структурированное дерево Т порядка q называется В-деревом порядка q, если порядок каждой его вершины не превосходит 2 q.

2.1. Весом вершины S называется число fi(S) = fi(k(S)). Полным весом дерева Т называется число М(Т) = р(К(Т)).

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

Обозначим ßmaх(К) = max{/x(fc)|& € К}. Рассмотрим структу-рированое дерево Т. Пусть вершины L и R, находятся на одном уровне в Т. Рассмотрим множество I = K(L) U K(R) ключей дерева Т. Тогда L называется левым соседом R, a R - правым соседом L, если среди ключей множества К(Т) \ I существует единственный ключ к, обладающий свойством

(V/ € K(L))(Mr е K{R)){Uk¿r)

Будем говорить, что такой ключ к разделяет соседние вершины L и R.

Неформально, вершины L и R, находящиеся на одном уровне в Т, являются соседними, если никакая другая вершина этого уровня не лежит между L и R. Отметим, что разделяющий ключ всякой пары соседних вершин принадлежит ближайшему общему предку этих вершин.

Сегментом вершин структурированного дерева Т называется последовательность So, ki, Si,. ■ ■, km, Sm вершин и ключей дерева Т такая, что всякая пара вершин Si-1, S¡ (i = 1,... ,m) последовательности является парой соседних вершин дерева Т, разделенных ключом к{. Длиной сегмента называется число m разделяющих ключей в последовательности.

Сегмент So, ki, Si,..., кт, Sm длины m вершин структурированного дерева Т ранга р называется плотным, если

/i(5o) + Hih) + KSl) + ■■■+ KSm-l) + Mfcm) + KSm) > Шр

Структурированное дерево T ранга р называется Ь-локально плотным, если каждый сегмент So,ki,Si, ■. ■ ,kb,Sb вершин этого дерева длины Ъ плотен. Параметр b в этом случае называется показателем локальности дерева.

Определение. Пусть (/<", Z, /л) - упорядоченное множество ключей с весом. £)5(6)-деревом ранга р порядка q называется структурированное Ь-локально плотное дерево Т ранга р порядка q, параметры 6, q и р которого связаны следующими соотношениями

Ь > 0, q > Ь, р > 2g/wW

Класс £)5(Ь)-деревьев ранга р порядка q обозначим через DS{b,q,p).

2.3. Пусть дан набор деревьев So,Si, ■.. ,Sm и набор ключей ki,...,km. Согласно определению дерева мы можем построить по этим двум наборам новое дерево S =< So, к\, Si,..., km, Sm >. Далее нам потребуется еще один "конструктор" деревьев. Новое дерево, обозначаемое [So, Ai, Si,... ,km, Sm], строится следующим образом. Если S,- =< Siю, 1ц, S,ц, ...> (i = 0,..., то), то

[So, ki,Si,..., km,Sm] = ( Soo, /oi,Soi,...

ku

Sio, 'n, Su,...

km i

SmOt 'ml i Smi, . . .)

Например, [(L0, h, Li), k, (R0,ri,Ri)] = {L0,h,Li,k, До,гь Ri)

Последовательность So, ki, Si,... ,km,Sm, состоящая из вершин и ключей, называется (m -f 1)-разбиением вершины S, если

S = [So, fei,Si,...,km,Sm]

Всякое (m + 1)-разбиение вершины S задается набором из то ключей этой вершины и определяет соответствующий набор из ш +1 вершин.

(m -f 1)-разбиение So, fei, Si,..., km,Sm вершины S называется правильным относительно параметров р и q (или (р, д)-правильным), если для каждого i = 0,1,..., m выполнено свойство

riSi)<P&\HSi)\>Q

В случае, когда из контекста ясно о каких параметрах р тл q идет речь, будем называть такие разбиения просто правильными.

Сегмент So, fei, Si, • • •, fem, Sm длины m вершин структурированного дерева Т ранга р порядка q несжимаем (относительно параметров р и q), если никакое ш-разбиение вершины [So, fei, Si,..., km, Sm] не является (р, д)-правильным.

Структурированное дерево Т ранга р порядка q называется 6-локально несжимаемым, если каждый его сегмент длины b несжимаем.

Определение. Пусть {К, ¿,ц) - упорядоченное множество ключей с весом. 5(6)-деревом ранга р порядка q называется структурированное ¿»-локально несжимаемое дерево Т ранга р порядка q, параметры b, q и р которого связаны следующими соотношениями

Ь> 0, q>b, р> 29/imax(if)

Класс 5(6)-деревьев ранга р порядка q обозначим через S(b,q,p).

2.4. Сравним введенные древесные структуры для различных значений параметров b, q и р. Сначала рассмотрим простейшие классы DS(b)- и 5(6)-деревьев, ассоциированные с параметром локальности 6 = 0.

Утверэвдение. DS(0,q, р) = S(0,q,p).

Классы DS(0)- и 5(0)-деревьев совпадают, поскольку свойства плотности и несжимаемости для сегментов длины 0 являются вырожденными. Это приводит к тому, что всякое структурированное дерево Т ранга р является как DS(0)-, так и 5(0)-деревом ранга р.

Утверядение. Класс всех структурированных деревьев совпадает с объединением

U U

?>0р>2{

В-деревья являются одним из подклассов этого класса.

Утверждение. Пусть (К, ¿,ро) - упорядоченное множество ключей с функцией веса ¡io, тождественно равной 1 на К. Тогда класс В-деревьев порядка q совпадает с классом 5(0, q, 2g).

В литературе часто выделяют один частный случай В-дере-вьев. Это 2-3-деревья. Всякое 2-3-дерево является В-деревом порядка з = 1. Поэтому класс 2-3-деревьев совпадает с классом 5(0,1,2).

Для наиболее важного с практической точки зрения случая деревьев с показателем локальности Ь = 1 имеем

Утверяедение. 5(1, д,р) = Х>5(1,д, р).

Различие понятий плотности и несжимаемости проявляется, когда показатель локальности 6 больше 1. Сравнительный анализ введенных деревьев показывает, что класс 5(6)-деревьев строго содержится в классе £>5(6)-деревьев для всех 6 > 1.

Лемма. Пусть 6 > 1 и вершина 5 структурированного дерева такова, что |5| > Ь(д + 1) — 1 и р(5) < Ьр. Тогда найдется (р, д)-правильное 6-разбиение вершины 5.

Лемма. Если 6 > 1, то существует £>5(6)-дерево Т ранга р порядка д, не являющееся 5(6)-деревом.

На основании приведенных лемм доказывается

Утвераедение. 5(6, ц, р) с р) для всех 6 > 1.

Существенное различие 5(6)-дереьев и £)5(6)-деревьев подчеркивает

Лемма. Пусть сегмент сг длины 6 несжимаем, тогда и всякий его подсегмент длины 6' < 6 несжимаем.

Прямым следствием леммы является

Утверэадение. Пусть Ь' < Ь < д < р/2ртъх(К). Тогда

5(6, я,р) С 5(6', д,р)

Аналогичное утверждение для £>5(6)-деревьев неверно. Можно показать, что классы £)5(6)-деревьев при различных значениях 6 находятся в общем положении по отношению друг к другу.

Утверждение. Пусть Ь < д' < д < р/2(1т&х{К). Тогда

Я5(6,?,р)с£>5(6,<Др) 5(6,9,р)с5(6,д',р)

Итак, 5(6)-деревья образуют сжимающуюся иерархию относительно параметра локальности 6, а при фиксированном Ь 5(6)-деревья порядка д образуют сжимающуюся иерархию относительно порядка д. Самым обширным классом иерархии 5(6)-деревьев является класс Ц,>2 5(0,1 ,р). Это класс всех структурированных деревьев.

Для Ь равного 0 и 1 классы S(b)- и DS(b)-деревьев совпадают. Для больших значений параметра локальности класс S(b,q,p) является собственным подклассом DS(b, q,p).

Классы DS(b)-деревьев не образуют иерархию по параметру локальности Ь. Однако, они образуют сжимающуюся иерархию по порядку q для каждого фиксированного Ь.

В силу отмеченной выше вырожденности свойств плотности и несжимаемости для случая 6 = 0, мы будем рассматривать далее лишь те деревья, для которых показатель локальности b > 0.

2.5. Заполненностью дерева Т ранга р называется отношение

Д(Г) = М(Т)/пр

которое характеризует эффективность использования памяти деревом Т.

Известно, что В-деревья эффективны по памяти только когда веса ключей из К почти одинаковы. В этом случае нижняя оценка заполненности В-деревьев близка к 1/2. В противном случае заполненность может быть сколь угодно малой. £)5(6)-деревья снимают это ограничение.

Далее будут построены нижние оценки заполненности для класса DS(b)-деревьев, которые в силу выше сказанного справедливы также и для 5"(&)-деревьев.

Сначала рассмотрим деревья высоты 1.

Лемма. Пусть d > b есть степень ветвления корня DS(b)-дерева Т ранга р высоты 1. Тогда

А(Г) > db~k ^ (6+l)(d+l) ^ bqd+l

где к = —d mod (b -f 1).

Подставляя максимальное значение к = b в правую часть доказанного неравенства, получаем

Следствие. Пусть d > b есть степень ветвления корня DS(b)-дерева Т ранга р, имеющего высоту 1. Тогда

На основании этого следствия доказыватся нижняя оценка заполненности £)5(6)-деревьев произвольной высоты.

Теорема. Пусть дерево Т € DS(b, q,p) имеет п вершин. Тогда при п > b(q + 1)р

дт > J.— К ' b+lq+2

Следствием данной теоремы является основной результат второй главы.

Утверждение. Пусть (К, ¿,ц) - упорядоченное множество ключей с весом. Тогда для всякого е > 0 найдутся три параметра b > 0, q >Ь и р> 2 qi*max(K) такие, что для всякого дерева Т G DS(b, q,p), имеющего п > b(q + 1)р вершин, его заполненность

Д(Г) > 1 - е

2.6. Анализ алгоритмов, реализующих три базовые операции поиска, вставки и удаления ключей для 5(4>)-деревьев, является весьма громоздкой и технически сложной частью исследования приведенной структуры данных. Резюме их анализа дает

Утверждение. Пусть число вершин дерева Т 6 S(b,q,p) равно п. Тогда время выполнения операций поиска, вставки и удаления в Т не превосходит O(logn).

В заключение мне хотелось бы поблагодарить моего научного руководителя профессора А.Л.Семенова за постоянное внимание и помощь в работе.

Литература.

1. K.V.Shvachko, Different Modifications of Pointer Machines and Their Computational Power. In Proceedings of MFCS'91, Warsaw. Lecture Notes in Computer Science, vol.520, pp. 426-435, 1991.

2. A.P. Pinchuk, K.Y. Shvachko, Maintaining Dictionaries: Space-Saving Modifications of B-Trees. In Proceedings of ICDT'92, Berlin. Lecture Notes in Computer Science, vol.646, pp.421-435, 1992. 1

3. K.V. Shvachko, Space-Saving Modifications of B-Trees. In Proceedings of Symposium on Computer Systems and Applied Mathematics, St.Petersburg, 1993, p.214

4. К.В.Швачко, Оптимальное представление динамических словарей с помощью сбалансированных деревьев. Материалы XI Международной Конференции "Логика, методология и философия науки", т.2, 1995, 181-186.

совместной работе [2] А.П.Пинчуку принадлежат результаты разделов 7—9; автору принадлежат результаты разделов 1-6.