Поиск в упорядоченной таблице

 

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

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

Для увеличения эффективности поиска в отсортированном файле существует другой метод, но он приводит к увеличению требуемого пространства. Этот метод называется индексно-последовательным методом поиска. В дополнение к отсортированному файлу заводится некоторая вспомогательная таблица, называемая индексом. Каждый ее элемент состоит из ключа k_index и указателя на запись в файле, соответствующую этому ключу p_index. Элементы в таблице index должны быть отсортированы по этому ключу также как и элементы в файле. Рассмотрим пример такого построения [3].

 

Рис. 4.1. Индексно-последовательный файл

 

Алгоритм, используемый для поиска в индексно-последовательном файле, прост.

Пусть k_index будет массивом ключей в индексе, и пусть p_index будет массивом указателей внутри индекса на записи в файле. Пусть данный файл представлен в виде массива, n — размер файла, n_index — размер таблицы индекса; тогда алгоритм может быть представлен следующим фрагментом программы:

 

// key – искомый ключ записи

…

search=0;

i=1;

 

while ((i<=nindex) && (kindex[i]<=key)) i:=i+1;

 

// установить lowlim на наименьшую возм. позиц.в таблице

 

if (i==1) lowlim=1;

else lowlim=pindex[i-1];

 

//установить hillim на наиб. возм. позиц.в таблице

 

if (i==nindex+1) hillim=n;  // последний элемент

 else hillim=pindex[i];

 

// поиск в таблице от позиции lowlim по дозиции hilim

 

for (j= lowlim;j<= hillim;j++)

 {

   if (k[j]==key)

  {

      search:=j; cout<<”Элемент найден. Его номер =”<< j;

      return;

}

}

…

 

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

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

 

 Рис. 4.2. Использование вторичного индекса

 

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

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

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

 

Бинарный поиск

 

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

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

 

low=l; hi=n; search = 0;

while (low<=hi)

{

     mid=(low + hi)/2;

     if (key= = k[mid])

            {

                        search = mid;

                       cout<<”Элемент найден.Его номер=”<< mid;

                       return 0;

            }

       else

       {

           if (key<k[mid]) hi =mid-1;

           else low = mid+1;

      }

}

Каждое сравнение в бинарном поиске уменьшает число возможных кандидатов сравнения в 2 раза. Таким образом, максимальное число сравнений ключа, которые будут сделаны, составляет приблизительно log ₂ n, т.е. алгоритм бинарного поиска имеет порядок O (log ₂ n).

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

 

Сбалансированные деревья (AVL-деревья)

Для удобства определим высоту пустого дерева как 0.

Баланс некоторого узла в дереве определяется как высота его левого поддерева минус высота его правого поддерева.

Сбалансированным бинарным деревом (деревом AVL) является такое бинарное дерево, у которого абсолютное значение баланса каждого узла £1.

Рис. 4.3. Сбалансированное бинарное дерево

 

Поиск по дереву

 

Ранее мы рассматривали построение бинарного дерева, в котором все левосторонние потомки некоторого узла с ключом key имели ключи, которые < key, а все правосторонние потомки имели ключи >= key [3].

Прохождение такого бинарного дерева в симметричном порядке дает файл, упорядоченный по возрастанию значения ключа. Такое дерево может быть использовано для бинарного поиска. Алгоритм поиска ключа key в бинарном дереве представляется следующим образом. Предполагаем, что каждый узел дерева содержит четыре поля: поле k, в котором хранится значение ключа данной записи; поле r, в котором хранится сама запись; поля left и right, которые являются указателями на поддеревья:

 

class item

 {

   public:       

      item *left; item *right;

      int k;      char r;

 };

void main()

{

  item * p;  // создается объект р

item * search=NULL;

     …

 

while(p!=NULL)

{

     if (p->k==key) search=p;

     if(p->k>key) p=p->left;

     if (p->k<key) p=p->right;

}

 

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

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

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

 

30	a1
47	a2
86	a3
95	a4
115	a5
130	a6
138	a7
159	a8
166	a9
184	a10
206	a11
212	a12
219	a13
224	a14
237	a15
258	a16
296	a17
307	a18
314	a19

Рис. 4.4

Рис. 4.5