Алгоритмы и структуры данных

2.3.4. Поиск по вторичным ключам

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

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

2.3.3.1. Инвертированные индексы

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

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

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

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

2.3.3.2. Битовые карты

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

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

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

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

2.3.4. Использование деревьев в задачах поиска

 

2.3.4.1. Упорядоченные деревья поиска

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

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

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

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

Итак, основными операциями, производимыми с упорядоченным деревом, являются:

• поиск вершины;
• добавление вершины;
• удаление вершины;
• очистка дерева.

Реализацию этих операций приведем в виде соответствующих процедур.

Алгоритм поиска можно записать в рекурсивном виде. Если искомое значение Item меньше Tree^A.Data, то поиск продолжается в левом поддереве, если равен - поиск считается успешным, если больше - поиск продолжается в правом поддереве; поиск считается неудачным, если достигли пустого поддерева, а элемент найден не был.

function Find Tree(Item: TypeElement; Tree: PTree): boolean;

{Поиск вершины дерева, содержащую значение Item}

var

Current: PTree; begin

Find_Tree := False;

if Tree <> nil then begin   {Дерево не пустое} Current := Tree;

if Current^A.Data = Item then   {Вершина найдена}

Find_Tree := True else

if CurrentA.Data > Item then   {Ищем в левом поддереве} Find Tree := Find Tree(Item, CurrentA.Left)

else    {Ищем в правом поддереве}

Find Tree := Find Tree(Item, CurrentA.Right);

end; end;

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

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

(процедура написана в предположении, что добавляемого элемента в дереве нет):

procedure Add Tree(Item: TypeElement; var Tree:  PTree);

{Добавление в дерево вершины со значением Item}

var

NewNode, Current: PTree; begin

if Tree = nil then begin   {Дерево пустое} {Создаем корень}

New(Tree);

TreeA.Data := Item;

TreeA.Left := nil;

TreeA.Right := nil; end else begin

Current := Tree;

{Поиск вершины}

while ((Item > CurrentA.Data) and (CurrentA.Right <> nil)) or ((Item < CurrentA.Data) and (CurrentA.Left <> nil)) do if Item > CurrentA.Data then

Current := CurrentA.Right else

Current := CurrentA.Left; {Создание новой вершины} New(NewNode); NewNodeA.Data := Item; NewNodeA.Left := nil; NewNodeA.Right := nil;

If Item > CurrentA.Data then {Новая вершина больше найденной} CurrentA.Right := NewNode     {Присоединяем новую справа}

else {Новая вершина меньше найденной}

CurrentA.Left := NewNode;     {Присоединяем новую слева}

end; end;

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

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

procedure Del Tree(Item: TypeElement; var Tree: PTree);

{Удаление из дерева вершины со значением Item}

var

Parent, Cur, Cur2: PTree;

Direction:  (L, R);  {направление движения (влево/вправо)} begin

{Поиск удаляемого элемента}

Parent := nil;  {предок удаляемой вершины}

Cur := Tree;

while ((Item > Cur^A.Data) and (Cur^A.Right <> nil)) or

((Item < CurA.Data) and (CurA.Left <> nil)) do begin Parent := Cur;

if Item > CurA.Data then begin

Cur := CurA.Right; Direction := R; end else begin

Cur := CurA.Left; Direction := L; end; end;

if Cur <> nil then begin     {Вершина найдена}

{Анализируем наличие потомков у найденной вершины} {и удаляем соответствующим образом}

if (CurA.Left <> nil) and (CurA.Right <> nil) then begin {Удаление вершины в случае наличия у нее обоих потомков} Parent := Cur; Cur2 := CurA.Right; {Поиск кандидатуры на замену} while Cur2A.Left <> nil do begin

Parent := Cur2; Cur2 := Cur2A.Left; end;

{Заменяем}

CurA.Data := Cur2A.Data;

{Спасаем правое поддерево вершины, которой заменяем} if Parent <> Cur then

ParentA.Left := Cur2A.Right else

ParentA.Right := Cur2A.Right; Dispose(Cur2); end else begin

{Удаление вершины в случае наличия у нее} {не более одного потомка} if (CurA.Left = nil) then begin if Parent <> nil then begin if Direction = L then

ParentA.Left := CurA.Right else

ParentA.Right := CurA.Right; end else begin

Tree := CurA.Right; end; end;

if (CurA.Right = nil) then begin if Parent <> nil then begin if Direction = L then

ParentA.Left := CurA.Left else

ParentA.Right := CurA.Left; end else begin

Tree := CurA.Left; end; end;

Dispose(Cur); end; end; end;

Временная сложность этих алгоритмов (она одинакова для этих алгоритмов, так как в их основе лежит поиск) оценим для наилучшего и наихудшего случая. В лучшем случае, т. е. случае полного двоичного дерева, получаем сложность O_min(log n). В худшем случае дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем придется просмотреть половину списка. Это даст сложность O_max(n).

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

Procedure Clear Tree(var Tree:  Ptree);

{Очистка дерева}

begin

if Tree <> nil then begin

Clear_Tree(TreeA.Left);

Clear_Tree(TreeA.Right);

Dispose(Tree);

Tree := nil; end; end;

Временная сложность этой операции O(n).

2.3.4.2. Случайные деревья поиска

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

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

зируется время поиска элемента в таком дереве, которое пропорционально O(log n). При поступлении элементов в упорядоченном виде (рис. 32, б) или в несколько необычном порядке (рис. 32, в) происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(n).

2.3.4.3. Оптимальные деревья поиска

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

Пусть даны 2n+1 вероятностей p_x, p₂, p_n, q₀, q₁, q_n, где p_i -вероятность того, что аргументом поиска является K_{; q_i - вероятность того, что аргумент поиска лежит между K_i и K_i+1; q₀ - вероятность того, что аргумент поиска меньше, чем q_n - вероятность того, что аргумент поиска больше, чем K_n.

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

где levelrooty - уровень узла j, а levellistk - уровень листа k.

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

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

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

Существуют алгоритмы, которые позволяют построить оптимальное дерево поиска. К ним относится, например, алгоритм Гарсия-Воча. Однако такие алгоритмы имеют временную сложность порядка O(n²), а некоторые еще имеют такую же пространственную сложность. Таким образом, создание оптимальных деревьев поиска требует больших накладных затрат, что не всегда оправдывает выигрыш при быстром поиске.

2.3.4.4. Сбалансированные по высоте деревья поиска

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

Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому в 1962 году два советских математика Г. М. Адельсон-Вельский и Е. М. Лан-дис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/ удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.

Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.