Главная | Обратная связь | Поможем написать вашу работу!

Задача динамического поиска

Описанные структуры данных хорошо подходят для случая, когда операция поиска применяется к неизменной структуре данных. Довольно часто АТД кроме операции НАЙТИ включают в себя набор операций, которые могут изменить состав данных исходного множества. К таким операциям могут быть отнесены операции вставки и удаления элементов. Для обеспечения эффективной реализации операции поиска эти операции должны уметь за приемлемое время поддерживать структуру представления множества в приемлемом для поиска виде. К сожалению, для упорядоченных массивов размерности вставка и удаление элемента, как в худшем, так и в среднем случае требует времени. Как уже упоминалось ранее, для реализации этих операций лучше подходит списочная структура. Но при использовании списочной структуры хотелось бы сохранить прямой доступ к элементу на соответствующих шагах алгоритма. Структурируем упорядоченную последовательность элементов множества , относительно некоторого элемента , расставляя скобки . Рекурсивно повторяя этот процесс до тех пор, пока не получатся одноэлементные последовательности, получим структурированное представление последовательности . Например, для последовательности 8,10,11,12,13,16,18,23,25,30, разбиение ее относительно медианы , получим

1-ый шаг (8,10,11,12),(13),(16,18,23,25,30)

2-ой шаг ((8),(10),(11,12)),(13),((16,18),(23),(25,30))

3-ий шаг (((8),(10)),(11),((12))),(13),(((16),(18)),(23),((25),(30)))

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

Под бинарным деревом поиска(BST – binary search tree)[6] для множества понимается двоичное дерево, каждый узел которого помечен ключом некоторого элемента из так, что выполняется:

1. для любого узла из левого поддерева узла ;

2. для любого узла из правого поддерева узла ;

3. для каждого элемента , существует единственный узел дерева, для которого .

Дерево двоичного поиска для нашего примера приведено ниже:

Инфиксный обход дерева в глубину задает линейный порядок на вершинах дерева, который совпадает с исходной последовательностью. Несложно заметить, дерево поиска можно интерпретировать как надстройку над упорядоченной последовательностью, в которой каждый элемент последовательности занимает некоторую позицию в структуре дерева. Приведенный пример представляет собой лишь один из возможных вариантов построения бинарного дерева поиска. Другой пример дерева для этой же последовательности приводится ниже.

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

На рисунке выделен путь поиска элемента с ключом 13

Ниже приведена процедура поиска в бинарном дереве

function Tree_Search (v: Tree_Item, k:DataItem):Tree_Item;

var found: boolean;

begin

found:=false;

while v <> NIL and not(found) do

begin

if k = key[v] then found:=true

if key[v]<k then

v left_sun(v)

else

v right_sun(v);

end;

Tree_Search:=v

end; { конец поиска }

Замечание. Процедуру поиска можно несколько упростить [23], используя определенные программистские приемы. С этой целью для каждого листа необходимо добавить ссылку на дополнительную вершину , к которой существует прямой доступ, и которая перед выполнением поисковой процедуры заполняется значением ключа k (барьера)[7], по которому ведется поиск.

function Tree_Search_b (v: Tree_Item, k:DataItem):Tree_Item;

begin

key[s]=k;

while key[v] <> k do

if key[v]<k then

v left_sun(v)

else

v right_sun(v);

return v

end; { конец поиска }

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

Рекурсивный вариант процедуры поиска с использованием BST выглядит следующим образом:

function RTree_Search (v: Tree_Item, key:DataItem):Tree_Item;

begin

if v = NIL then return NIL;

if key[v]=key return v;

if key < key[v] then

return RTree_Search(left_sun(v),key)

else

return RTree_Search(right_sun(v),key);

end; { конец поиска }

Как отмечалось, для оптимизации времени поиска необходимо, чтобы время поиска во множествах и , разбиваемых некоторой вершиной различались не более чем на 1. Время поиска для структуры данных дерево поиска определяется высотой соответствующего дерева. Поэтому, выбирая на каждом шаге разбиение относительно медианы, всегда можно построить дерево поиска, для которого это условие выполнено. В этом случае высота дерева поиска для множества из элементов равна .

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

· такая вершина не существует;

· вершина существует и уже занята, т.е. содержит другой ключ .

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

При исключении элемента из дерева также выполняется поиск ключа. Если ключ обнаруживается, то возможны следующие случаи:

· ключ содержится в листовой вершине, у вершины-отца имеются два сына;

· ключ содержится в листовой вершине, являющей единственным сыном своего отца;

· ключ содержится во внутренней вершине, имеющей только левого или только правого сына;

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

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

Вообще-то дерево всегда может быть перестроено так, чтобы вставляемый ключ попал в определенное место. Операции перестройки называются вращениями и заключаются в изменении связей между вершинами. Вращения делятся на левые и правые. Проиллюстрируем перестройку дерева поиска примерами из [3]:

Пример вращения вправо (узел становится правым сыном узла ): узел становится правым сыном узла , узел становится левым сыном

Пример вращения влево (узел становится левым сыном узла , узел - правым становится его левым сыном).

Вращение представляет локальное изменение в структуре дерева, затрагивающее два узла и три связи, и сохраняющее свойство порядка. Нижний пример показывает процесс перемещение узла в корень:

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

В этом случае дерево поиска не отличается от последовательного списка, а его высота составляет . Как отмечено в [3], худший случай довольно часто встречается на практике, поскольку поиск может применяться к изначально упорядоченным структурам. Для поддержки эффективности поиска применяются различные приемы перестройки дерева, поддерживающие его высоту на уровне . Такие приемы называются балансировкой деревьев. Поскольку балансировка требует дополнительных временных затрат, важно, чтобы время, затрачиваемое на балансировку, также оценивалось функцией .

Построение эффективных алгоритмов балансировки связано с рекурсивностью определения структуры «дерево» [23]: Все алгоритмы поддержки определенных свойств (в число которых входит баланс) в дереве используют его рекурсивное строение. Если условие баланса после операции вставки или удаления элемента нарушено в некотором поддереве с корнем , то необходимо устранить это нарушение, а далее проверить нарушается ли это свойство для всех деревьев, включающих в качестве поддерева. Это означает, что алгоритм должен проверить и при необходимости внести коррективы в структуру поддеревьев, корни которых лежат на пути, ведущем от вершины к корню всего дерева, а таких - не более . Если операция корректировки одного поддерева занимает константное время, то получаем алгоритм сложности . В зависимости от определения понятия баланса, задача его поддержки при операциях вставки и удаления элементов приводит к различным структурам, построенным над линейно упорядоченным множеством. Далее рассматриваются несколько вариантов определения баланса. Все варианты приводят к алгоритмам, в которых время выполнения операций поиска, вставки и удаления определяются высотой дерева и занимают шагов. Усиление или ослабление требований на условия балансировки лишь меняют константу перед логарифмом.

В качестве первого примера рассмотрим идеально сбалансированное двоичное дерево[23]. Двоичное дерево называется идеально сбалансированным, если для каждой его вершины, число вершин в его левом и правом поддереве отличается не более чем на 1 (нетрудно показать, что при соблюдении этого условия длины пути от корня до любой листовой вершины дерева отличаются не больше, чем на 1). Понятно, что такое дерево является оптимальным с точки зрения времени поиска. Однако поддержка дерева поиска в идеально сбалансированном состоянии требует усложнения операций включения и исключения ключей с существенным (неприемлемым) увеличением накладных расходов. Кроме того, Н.Виртом показано, что при равномерном распределении значений включаемых и исключаемых ключей использование идеально сбалансированных деревьев поиска дает в среднем выигрыш не более 39% (имеется в виду среднее число сравнений, требующихся при поиске). Поэтому на практике идеально сбалансированные деревья поиска используются крайне редко.

Условие идеальной сбалансированности является чрезмерно жестким. На самом деле для задачи поиска требуется сохранение баланса между высотами левого и правого поддеревьев[24]. Бинарное дерево называется сбалансированным (или АВЛ деревом) в том и только в том случае, когда высоты двух поддеревьев каждой из вершин дерева отличаются не более чем на единицу. При использовании таких деревьев, как в среднем, так и в худшем случае, время выполнения операций поиска, вставки и удаления элемента составляет O(log n). Оно практически не отличается от времени поиска в идеально сбалансированных деревьях, но при этом обеспечивается более простая процедура балансировки с затратами в тех же пределах O(log n).

Рассмотрим в общих чертах процедуру вставки элемента в АВЛ дерево. Наиболее интересными являются случаи, когда добавление нового узла приводит к нарушению баланса в одном из поддеревьев АВЛ дерева. С учетом симметричности, ситуации, возникающие при нарушении баланса (при включении элемента в левое поддерево), разбиваются на два случая:

Прямоугольники обозначают поддеревья, нарушение балансировки обозначено перечеркнутыми квадратиками. Восстановление баланса происходит за счет вращений деревьев вокруг некоторых своих вершин. Результаты таких вращений для случаев 1 и 2 приведены на рисунке ниже

Для случая 1 имеем однократное вращение вокруг вершины А, а в случае 2 имеем два вращения относительно вершины В. Случай нарушения баланса в правом поддереве рассматривается аналогично.

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

1. поиске места элемента в дереве;

2. определении свойства сбалансированности всех поддеревьев, корни которых расположены на пути от отца нового элемента до корня всего дерева.

3. перестройке соответствующего поддерева с использованием операций вращения при нарушении баланса в некотором поддереве.

Рассмотрим некоторые шаги алгоритма на примере 13, 12, 6, 9, 10, 11, 7, 18, 30, 15, 23, 21. Несложно заметить, что нарушение баланса проявляется в случае, когда последовательность включаемых элементов содержит длинные монотонные подцепочки. В самом деле, после включения элемента 6 имеем дерево-цепочку, которое однократным вращением преобразуем в сбалансированное дерево

Следующее нарушение баланса наступает при включении элемента 10

Добавление элемента 11 вновь приводит к нарушению баланса. Здесь мы имеем случай 2 и после двойного вращения получим

Окончательно, дерево поиска имеет вид:

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

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

Более подробная информация о работе с АВЛ деревьями содержится в [23].

Несколько другую разновидность сбалансированных деревьев поиска с небольшим ослаблением условий баланса составляют красно-черные деревья:

Красно-черное дерево - это двоичное дерево поиска, обладающее следующими свойствами (будем называть их RB свойствами):

Каждый узел дерева покрашен либо в черный, либо в красный цвет.
Листьями объявляются NIL-узлы ("виртуальные" узлы, являющиеся сыновьями узлов, которые в двоичном дереве поиска являлись листьями). Листья покрашены в черный цвет.
Если узел красный, то оба его сына являются черными.
На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

Предыдущий пример в виде красно-черного дерева может быть представлен в следующем виде:

Количество черных узлов на ветви от корня до листа называется черной высотой дерева (по определению не зависит от выбранного листа). Перечисленные свойства гарантируют, что самая длинная ветвь, ведущая от корня к листу, не более чем в два раза длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой . Кратчайшее возможное расстояние от корня до листа равно - когда все узлы черные. Самое длинное расстояние от корня до листа равно , узлы при этом покрашены таким образом, что цвета чередуются (от корня к листу) так: красный, черный, красный, черный, …, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоению длины пути, проходящего только через черные узлы. Поэтому можно считать, что красно-черное дерево поддерживает следующий критерий баланса: глубина любых двух листьев в дереве отличаются не более чем в два раза. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, эти свойства должны сохраняться при вставке и удалении. При соблюдении RB свойств, имеет место

Лемма[4]. Красно-черное дерево с внутренними вершинами (не считая NIL листьев) имеет высоту не более )

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

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

Каждая операция вращения требует времени. Операции левого и правого вращения являются обратными друг другу. При добавлении нового узла сначала ведется поиск места этого узла в дереве. Узел красится в красный цвет, его сыновья (NIL-узлы) окрашены в черные цвета. При вставке может быть нарушено RB-свойство 3, поскольку отец вставленной вершины также может быть окрашен в красный цвет. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево. Рассмотрим ситуацию, когда отец нового узла - красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:

1. Красный отец, красный "дядя": Ситуацию красный-красный иллюстрирует следующий рисунок.

У нового узла X отец А и "дядя" С оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел B), поскольку он может оказаться красным. Далее рекурсивно проверяется RB свойство для всех деревьев корни которых лежат на пути от узла В до корня всего дерева. В самом конце корень красится в черный цвет. Если он был красным, то при этом увеличивается черная высота дерева

2. Красный отец, черный "дядя": На рисунке ниже представлен другой вариант красно-красного нарушения - "дядя" нового узла оказался черным.

Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в черный цвет. Если узел X был в начале правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком.

Рассмотрим наш пример: пусть вставляется элемент 5. Красно-черное дерево после вставки узла 5 выглядит следующим образом:

В этом дереве нарушено RB свойство 3(вершины 5,6). Используя первое преобразование, получим

Поскольку для вершины 7 отец(10) и дядя(18) окрашены в красный цвет, то вновь используем преобразование 1. Получим

Последующее добавление 3 приведет к дереву

Однако ситуация с вершинами 3 и 5 несколько другая. Дядя вершины 3 имеет черный цвет. Применяя второе преобразование, получим

Метод удаления рассматривается аналогично [4].

Из-за сложности реализации операций балансировки считается, что сбалансированные деревья следует использовать лишь в том случае, когда операция поиска производится значительно чаще, чем операции включения и удаления. Каждая рассмотренная выше структура данных, реализующая бинарное дерево поиска предполагала некоторую надстройку над упорядоченной последовательностью, удовлетворяющую определенным отношениям. При этом элементы основного множества были сопоставлены как листьям дерева, так и его внутренним вершинам (время доступа к элементам множества было неодинаковым). С другой стороны, минимизация длины худшего по времени поиска требовало определенных затрат, связанных с перестройкой дерева. Здесь уместно задать следующий вопрос: Если вместо двоичного поиска использовать -ичные деревья (), можно ли получить существенный выигрыш по сравнению с двоичным случаем? Несложно видеть, что ответ на этот вопрос отрицательный, изменяя число ветвлений вершин, нельзя выйти за класс логарифмических по времени алгоритмов, но при определенной организации структуры дерева, можно отказаться от операций вращения, заменив их более простыми операциями.

Рассмотрим другую модель кодирования словаря, в которой все листья дерева расположены на одинаковом уровне, а степень ветвления вершин может быть более двух. Баланс в таких деревьях поддерживается за счет изменений степеней вершин. Наиболее простым примером такой структуры данных являются 2-3 деревья[2].

2-3 деревом называется дерево, в котором каждый внутренний узел имеет двух или трех сыновей, а длины всех путей от корня в листья совпадают между собой. Поскольку в процессе поиска необходимо делать выбор между тремя сыновьями, в 2-3 дереве каждый нутренний узел дерева хранит не один, а два ключа.

Линейно упорядоченное множество можно представить 2-3 деревом, приписав его элементы листьям дерева с использованием заданного порядка. Каждый внутренний узел содержит две метки и , где - набольший элемент, приписанный листьям самого левого сына вершины , - набольший элемент, приписанный листьям второго сына этой вершины. Используя эти метки для поиска, легко решить задачу НАЙТИ за время пропорциональное высоте дерева ().

2-3 деревья служат хорошей структурой данных для АТД со следующим набором операций:

1. ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ

2. ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ ЗНАЧЕНИЕМ КЛЮЧА

3. ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ, НАЙТИ С МИНИМАЛЬНЫМ ЗНАЧЕНИЕМ КЛЮЧА

4. ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ, СЦЕПИТЬ, РАСЦЕПИТЬ

Как уже упоминалось выше, АТД с набором операций из множества 1 называется Словарем, из множества 2 – Очередью с приоритетами, 3 – Сливаемым деревом, 4 – Сцепляемой очередью.

2-3 деревья позволяют эффективно выполнять последовательности операций из любого набора перечисленных операций. Единственная несовместимость состоит в том, что операция ОБЪЕДИНИТЬ приводит к неупорядоченному множеству, а операции СЦЕПИТЬ, РАСЦЕПИТЬ предполагают наличие порядка.

Словари и очереди с приоритетами. Рассмотрим реализацию операции ВСТАВИТЬ. Сначала поиском по дереву определяется место нового элемента в последовательности меток листьев дерева. Для этого ищут узел дерева, имеющего двух или трех сыновей, к листьям которого необходимо приписать .

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

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

Процесс удаления вершины из дерева является обратным к операции вставки. Пусть удаляемый элемент принадлежит листу . Рассмотрим три случая:

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

a) - корень, удаляем и , корнем дерева становится .

b) - не корень. Если имеет слева от себя брата [8], то подсчитывается число сыновей вершины . Если у два сына, делаем узел самым правым сыном вершины , удаляем и рекурсивно вызываем процедуру удаления узла . Если у три сына, то самого правого сына делаем левым сыном узла , и удаляем . Далее проводится корректировка меток вершин, лежащих на пути от (возможно ) до корня дерева.

Показано [2], что операция удалить элемент из множества, содержащего элементов, также занимает времени. Таким образом, для словаря 2-3 дерево представляет структуру, позволяющую обеспечить выполнение последовательности из операций ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ за шагов.

Рассмотрим одно из возможных представлений в виде 2-3 дерева уже знакомого нам множества чисел

Проиллюстрируем вставку и удаление элемента на следующих примерах. Добавляя элемент 5, получим

Вершина (6:7) содержит 4 сына и должна быть расщеплена на две вершины (5:6) и (7:9), каждая из которых имеет отцом вершину (9:11). Далее поднимаясь на один уровень вверх, исследуем вершину (9:11). Поскольку эта вершина содержит 4 сына, она также расщепляется на две вершины. Исследование вершины более верхнего уровня (15:30) показывает, что она удовлетворяет условиям определения 2-3 дерева. И хотя на данном шаге процесс корректировки структуры дерева может быть прерван, процесс корректировки меток продолжается до корня дерева. Результат построения показан на рисунке ниже:

Из получившейся структуры удалим вершину 11. Поскольку после удаления вершина (10:11) имеет единственного сына, то второго сына заимствуем от вершины (12:13) с корректировкой соответствующих меток. Далее необходимо откорректировать метки верши, находящихся на пути от отца вершин (10:11) и (12:13) до корня дерева[9].

Что касается очередей с приоритетами, то выполнение операции МИНИМУМ требует шагов (минимальный элемент является крайним слева в упорядоченном списке листьев). Следовательно, 2-3 деревья служат для реализации АТД Очередь с приоритетами с производительностью , где общее число запросов.

Сливаемые деревья. Для решения задач, связанных с объединением, рассмотрим другую настройку 2-3 дерева. Мы не будем требовать выполнения отношения линейного порядка на листьях дерева, внутренние вершины должны содержать информацию о минимальном элементе, для поддерева, корнем которого они являются. Тогда очевидно минимальный элемент на такой структуре определяется за шагов. Для выполнения операций ВСТАВКА и УДАЛЕНИЕ можно ввести дополнительное 2-3 дерево, листья которого содержат указатели на листья исходного дерева. Рассмотрим подробнее операцию ОБЪЕДИНЕНИЕ[10]. Пусть имеются два дерева и , листья которых соответственно представляют множества и . Если высоты деревьев и совпадают (), то строится дерево с новым корнем , сыновьями которого являются корни деревьев и .

Пусть [11]. Найдем в дереве узел , высота которого совпадает с высотой дерева . Пусть отец узла . Сделаем корень дерева сыном узла . Если узел имеет четырех сыновей, то расщепляем вершину на две с дальнейшим проходом до корня дерева.

Сцепляемые очереди. Рассмотрим реализацию операций СЦЕПИТЬ, РАСЦЕПИТЬ на 2-3 деревьях. Операция СЦЕПИТЬ() является конкатенацией двух отсортированных последовательностей и , причем каждый элемент последовательности меньше каждого элемента из . При условии, что последовательности и представлены 2-3 деревьями и , можно применить операцию объединения деревьев и , как это описано для сливаемых деревьев.

Операция РАСЦЕПИТЬ() разбивает на два множества и . Поскольку множество листьев 2-3 дерева упорядочено, необходимо найти в 2-3 дереве лист и построить путь, ведущий из корня дерева в . Этот путь разбивает дерево на множество поддеревьев, лежащих по разные стороны от пути и лист . Деревья, лежащие слева от пути, включая лист , объединяются используя операцию СЦЕПЛЕНИЕ в дерево , а деревья, лежащие по правую сторону от пути объединяются в дерево . Ниже на рисунке показана схема расщепления 2-3 дерева на два дерева по элементу . Более подробную информацию о процедуре расщепления 2-3 дерева можно почерпнуть в [2]

Б-деревья — это один из видов сбалансированных деревьев, обеспечивающих эффективное хранение информации на магнитных дисках и других внешних устройствах с прямым доступом. Б-деревья похожи на 2-3 деревья, разница в том, что в Б-дереве каждый внутренний узел может иметь много детей, на практике до тысячи, в зависимости от характеристик используемого диска. Благодаря этому можно значительно уменьшить высоту дерева и понизить константу в оценке времени поиска элемента. В основном Б-деревья служат для реализации доступа к данным файла по ключу поиска. Для этого создается (и поддерживается) индексный файл, который фактически является реализацией АТД словарь.

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

Дадим более строгое определение. Б-деревом[3,4] называется корневое дерево, устроенное следующим образом:

Каждая вершина содержит следующую информацию:

количество ключей, хранящихся в ней;
упорядоченный список ключей
метку, отмечающую, что - лист

Каждая внутренняя вершина содержит список из указателей на детей этой вершины. У листьев, которые не имеют детей, указатели не определены (равны Null).
Ключи служат границами, разделяющими значения ключей в поддеревьях: , где - значение любого ключа в поддереве, определяемым -м указателем вершины
Все листья имеют одинаковую высоту, совпадающую с высотой всего дерева
Число ключей, хранящихся в одной вершине, ограничено снизу и сверху:

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

Из определения следует, что все внутренние вершины (кроме корня) имеют не менее детей, и каждая внутренняя вершина имеет не более детей. Число называется минимальной степенью Б-дерева. В простейшем случае, при , получается 2-3-4 дерево. Для эффективной работы с диском на практике выбирают достаточно большим. Внутренние и листовые страницы обычно имеют разную структуру. При поиске в Б-дереве ключ сравнивается с ключами, хранящимися в вершине, результаты сравнения определяют дальнейший путь в дереве.

Теорема [4] Для всякого Б-дерева высоты и минимальной степени (), хранящего ключей, выполнено неравенство

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

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

В этом дереве можно добраться до любого ключа за три доступа к диску. После считывания соответствующего блока в оперативную память, для поиска внутри блока можно применять различные алгоритмы поиска, рассмотренные ранее (обычно применяется последовательный поиск). Число элементов внутри блока определяется выбранным значением . Общее число элементов на -м уровне ограничено сверху числом . Если бы мы сгруппировали по 100 ключей на узел, то за три доступа к диску мы могли бы найти любой ключ из 1000000. Заметим, что поскольку Б-деревья являются сильно ветвящимися и сбалансированными, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Алгоритмы вставки и удаления ключей очень похожи на соответствующие операции для 2-3 деревьев. Во время вставки находится место вставляемого ключа, исследуется соответствующая вершина на предмет возможности добавления ключа в найденный узел. Если узел содержит свободные места, то операция включения является достаточно простой: при включении необходимо сохранить отношение порядка на ключах. Если при добавлении ключа в узел происходит заполнение узла, т.е. образуется узел с ключами, то этот узел разбивается на два узла с ключами в каждом узле. При этом ключ-медиана отправляется к отцу узла и становится разделителем между ключами двух вновь полученных вершин. При условии заполнения вершины , она также делится на две вершины, процесс продолжается до тех пор, пока не найдется вершина, содержащая менее ключей, или не будет достигнут корень дерева. При условии расщепления корня, такая процедура может увеличить высоту дерева на 1. Ниже проиллюстрирован пример включения элемента 8 в дерево

Поскольку число листьев в левом блоке равно 3, происходит расщепление этого узла с переносом элемента 6 на верхний уровень

Поскольку вершина на втором уровне с набором ключей 6, 11, 17, заполнена, то осуществляется разбиение этой вершины

Аналогичные действия предпринимаются при удалении - здесь может потребоваться объединение потомков. При удалении ключа высота дерева может уменьшиться на 1. Такой метод изменения глубины дерева позволяет сохранить его сбалансированность.

В литературе встречаются различные модификации Б-деревьев. Б*-деревья устроены аналогично стандартным Б-деревьям, единственное отличие - узлы заполняются на 2/3. Это приводит к лучшему использованию места, занимаемого деревом, и чуть лучшей производительности.

Б+ дерево - это разновидность Б-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах - ключи разделители, содержащие диапазон изменения ключей для поддеревьев. На рисунке представлено Б+ дерево. Все ключи хранятся в листьях, там же хранится и информационная часть узла. Во внутренних узлах хранятся копии ключей - они помогают искать нужный лист. У указателей смысл немножко не такой, как при работе с обычными Б-деревьями. Левый указатель ведет к ключам, которые меньше заданного значения, правый - ключам, которые больше или равны (GE). Например, к ключам, меньшим 22, ведет левый указатель, а к ключам от 23 и выше ведет правый.

Обратите внимание на то, что ключ 22 повторяется в листе, где хранятся соответствующие ему данные. Во время вставки и удаления необходимо аккуратно работать с родительскими узлами. Когда модифицируются первый ключ в листе, дерево проходится от листа к корню. Последний из GE-указателей, найденный при спуске по дереву, и является тем, который потребуется модифицировать, чтобы отразить новое значение ключа. Поскольку все ключи повторяются в листьях, мы можем связать их для последовательного доступа.

Основные достоинства Б деревьев

Во всех случаях полезное использование пространства вторичной памяти занимает свыше 50 %. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.
Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).
В среднем достаточно эффективно реализуются операции включения и удаления записей; при этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

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

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒