Двоичный поиск (делением пополам)
ПОИСК ДАННЫХ
Таблицы
Таблица – это набор элементов, содержащих ключ - отличительный признак для поиска элемента, и тело (сопутствующую информацию).
Примеры таблиц.
а) Таблица значений функции: ключ элемента - аргумент X, тело – значение функции f(X);
б) Словарь: ключ - слово, тело - перевод слова;
в) Телефонный справочник: ключ - имя владельца, тело - номер телефона;
г) Таблица имен транслятора: ключ - имя какого-либо объекта транслируемой программы, тело - его характеристики (тип, размерность, адрес, значение переменной и т. п.).
Везде, где есть поиск информации, используются таблицы. Трансляторы тратят на работу с таблицами до 50 % времени.
Основные операции над таблицами:
1. Инициализация (подготовка к работе);
2. Поиск элемента по ключу - основная операция (входит в другие операции);
3. Включение в таблицу данного элемента;
4. Исключение из таблицы элемента с данным ключом;
5. Изменение в таблице тела элемента с данным ключом;
6. Перебор (например, вывод) элементов таблицы в порядке, определяемом ключами.
Виды таблиц: статическая (постоянная) и динамическая (меняющаяся при работе программы), внутренняя (в оперативной памяти) и внешняя (во внешней памяти). Таблицу размещают во внешней памяти, если ее необходимо сохранять после работы программы или она слишком велика для ОЗУ. Рассмотрим основные методы организации внутренних таблиц.
Линейные таблицы
Линейной (последовательной) называют таблицу, в которой производится линейный поиск (последовательный перебор элементов). Линейные таблицы бывают упорядоченными или неупорядоченными в виде вектора или списка. Рассмотрим две из них на примерах.
Таблица в виде вектора
Пример 5.1. Неупорядоченная векторная таблица.Задача: составить программу подсчета количества повторений каждого слова входного текста. Результат вывести в лексикографическом порядке.
Пример работы:
Вход: to be or not to be
Выход:
Слово Кол-во
be 2
not 1
or 1
to 2
Для решения задачи нужна таблица, ключом в которой служит слово, тело - количество его повторений. Очередное слово ищется в таблице. Если его там нет, оно включается в таблицу, а если есть, то увеличивается число повторений. Требуемые операции: инициализация, поиск, включение, изменение и вывод.
Для примера используем неупорядоченную линейную таблицу в виде вектора (рис. 5.1). Ключи размещены в ней в порядке поступления. Тогда перед распечаткой потребуется еще сортировка (упорядочивание) таблицы.
| Индекс | t | kol | |||
| To | |||||
| Длина таблицы dt = 3 | Be | ||||
| │ | Or | ||||
| Барьер └ → 3 | Not | ||||
| … | . . . | ||||
| DTMAX | |||||
| Рис. 5.1. Неупорядоченная таблица в виде вектора c барьером (при поиске слова not входного текста: to be or not to be) |
Ниже показана нисходящая разработка программы напсевдокоде. Сначала алгоритм записывается укрупненно с использованием неформальных обозначений данных и операций, например:
Заполнение таблицы t;
Если данные или операции достаточно сложны и не описаны в другом разделе пособия, они затем детализируются через более мелкие данные и операции в одном из фрагментов программы с соответствующим комментарием:
/* Заполнение таблицы t */.
Так продолжается, пока программа не станет достаточно подробной. Этапы разработки отделены горизонтальными линиями.
Алгоритм 5.1. Подсчет количества повторений слов текста с применением неупорядоченной линейной таблицы в виде вектора
#include <stdio.h>
void main ()
{ 1. Инициализация таблицы;
2. Чтение текста и заполнение таблицы слов;
3. Сортировка таблицы по алфавиту;
4. Вывод таблицы;
}
------------------------------------------------------------------------------------------------
Определение данных:
#define DTMAX 1001 /* Маx колич-во разных слов + 1 (для барьера) */
#define DSLMAX 21 /* Максимальная длина слова + 1 (для'\0') */
/* Последовательная таблица в виде вектора: t,kol,dt */
/* (представлена параллельными массивами t, kol) */
char t[DTMAX][DSLMAX]; /* Слова */
int kol[DTMAX]; /* Количество повторений */
int dt; /* Длина таблицы (количество слов) */
------------------------------------------------------------------------------------------------
dt = 0; /* 1. Инициализация таблицы */
------------------------------------------------------------------------------------------------
int sim; /* Текущий символ входного текста */
char sl[DSLMAX]; /* Текущее слово входного текста */
…
/* 2. Чтение текста и заполнение таблицы слов */
sim = getchar(); /* 1-й символ текста */
while (sim != EOF)
{ Чтение слова sl (и 1-го символа следующего слова);
Корректировка таблицы для прочитанного слова;
}
------------------------------------------------------------------------------------------------
int j; /* Индекс символа в слове */
…
/* Чтение слова sl (и 1-го символа следующего слова) */
for (j=0; sim!=' ' && sim!=',' && sim!='.' && sim!='\n'
&& sim!=EOF; sim=getchar())
if (j < DSLMAX-1) sl[j++] = sim;
sl[j] = '\0'; /* Признак конца слова */
/* Пропуск разделителей слов */
while (sim==' ' || sim==',' || sim=='.' || sim=='\n')
sim = getchar();
------------------------------------------------------------------------------------------------
int i; /* Индекс текущего элемента таблицы */
/* Корректировка таблицы для прочитанного слова */
/* Линейный поиск с барьером слова sl в таблице t */
strcpy (t[dt], sl); /* Создание барьера == sl */
for (i=0; strcmp(sl,t[i]); i++);
if (i < dt) /* Нашли t[i] == sl */
kol[i]++; /* Изменение количества повторений sl */
else /* Не нашли */
/* Включение слова sl в таблицу */
if (dt < DTMAX-1) /* Есть место */
kol[dt++] = 1;
else /* Таблица переполнена */
{ fprintf (stderr,
"\nОшибка: разных слов больше %d"
"\nслово '%s' не учитывается\n", DTMAX-1, sl);
}
Ускорить поиск, избежав проверок в цикле на конец таблицы, можно с помощью "барьера" - элемента в конце таблицы, содержащего искомый ключ. Плата за ускорение - память для барьера.
---------------------------------------------------------------------------------------------------
int L; /* Длина просмотра сортировки */
/* 3. Сортировка таблицы по алфавиту методом обмена */
for (L=dt-1; L>0; L--)
/* Просмотр элементов t[0]...t[l] */
for (i=0; i<L; i++)
/* Сортировка пары t[i] и t[i+1] */
if (strcmp(t[i],t[i+1]) > 0)
{ /* Обмен t[i] <--> t[i+1] */
strcpy (sl, t[i]); strcpy (t[i], t[i+1]); strcpy (t[i+1], sl);
/* Обмен kol[i] <--> kol[i+1] */
j = kol[i]; kol[i] = kol[i+1]; kol[i+1] = j;
}
------------------------------------------------------------------------------------------------
/* 4. Вывод (сортированной) таблицы */
printf ("\n%*s%s", DSLMAX, "Слово ", "Кол-во\n");
for (i=0; i<dt; i++)
printf ("%-*s %5d\n", DSLMAX, t[i], kol[i]);
Таблицы в виде списка
Пример 5.2. Упорядоченная линейная таблица в виде списка(другой метод решения задачи из примера 5.1). Подсчитаем количество повторений слов текста с помощью упорядоченной линейной таблицы в виде списка с элементами переменной длины, организованного с помощью указателей.
При нисходящей разработке программы на псевдокоде приведем только фрагменты, отличающиеся от примера 5.1. Упорядоченность таблицы устраняет необходимость ее сортировки (алгоритм зависит от структуры данных!) – алг. 5.2:
Алгоритм 5.2. Подсчет количества повторений слов текста с применением упорядоченной линейной таблицы в виде списка.
#include <stdio.h>
#include <stdlib.h>
void main ()
{
1. Инициализация таблицы;
2. Чтение текста и заполнение таблицы слов;
3. Вывод таблицы;
}
Чтение слов входного текста выполняется как в примере 5.1. Отличаются лишь операции с таблицей. На рис. 5.2 показана структура упорядоченной таблицы в виде списка.
sled kol sl
Барьер
pt
Указатель baryer
списка DSLMAX символов
Рис. 5.2. Упорядоченная списковая таблица
с барьером и элементами переменной длины
(при поиске слова not входного текста: to be or not to be)
Первый фиктивныйэлементсписка содержит указатель фактического начала списка. Хранение указателя в фиктивном элементе списка позволяет включать элемент в начало списка так же, как в его середину - упрощает операцию включения (за счет памяти).
Последний фиктивный элемент списка используется как барьер для устранения проверок на конец списка в цикле поиска, подобно примеру 5.1. Это упрощает и ускоряет поиск (тоже за счет памяти).
Здесь у барьера адрес постоянный и, чтобы не копировать туда каждое слово, текущее слово расположено в барьере! Изменяется описание переменой sl, но не программа чтения слова!
Поскольку ключи упорядочены, и при встрече ключа, превышающего искомый, поиск прекращается, в качестве барьера можно было использовать не только искомый ключ, но и код, состоящий из единиц и заведомо превышающий любой ключ.
Чтобы обеспечить постоянство смещений адресов полей внутри элемента списка, в начале элемента размещены поля фиксированной длины (sled и kol), а затем - поле переменной длины sl (для языка высокого уровня это может делать и сам компилятор).
Определение данныхдля таблицы:
struct el_tab /* Элемент таблицы (списка) */
{ struct el_tab *sled; /* Указатель следующего элемента */
int kol; /* Количество повторений */
char sl[]; /* Слово */
};
struct el_tab *pt; /* Указатель фиктивного начала таблицы */
struct el_tab *baryer; /* Указатель барьера */
char *sl; /* Адрес текущего входного слова (в барьере) */
----------------------------------------------------------------------------------------------------
Пустая таблица состоит из фиктивного элемента и барьера.
/* 1. Инициализация таблицы */
baryer = malloc (sizeof(struct el_tab)
+ DSLMAX); /* Место для слова и '\0' */
sl = baryer->sl;
pt = malloc (sizeof(struct el_tab));
pt->sled = baryer; /* Пустая таблица */
----------------------------------------------------------------------------------------------------
struct el_tab *i, /* Указатели текущего и */
ipr; /* предыдущего элементов таблицы */
/* Корректировка таблицы для прочитанного слова */
/* Линейный поиск с барьером слова sl в таблице */
i = pt->sled; ipr = pt;
while (strcmp(sl,i->sl) > 0)
{ ipr=i; i = i->sled; /* К следующему элементу списка */
}
if (i!=baryer && strcmp(sl,i->sl)==0) /*Нашли i->sl==sl */
i->kol ++; /* Изменение количества повторений sl */
else /* Не нашли */
{ /* Включение слова sl в таблицу */
i = malloc (sizeof(struct el_tab)
+ strlen(sl)+1); /* Место для sl и '\0' */
if (i != NULL) /* Есть место */
{ /* Создание нового элемента */
strcpy (i->sl, sl); /* Слово sl - в новый элемент */
i->kol = 1;
/* Включение элемента в список после *ipr */
i->sled = ipr->sled; ipr->sled = i;
}
else /* Таблица переполнена */
{ fprintf (stderr,
"\nОшибка: слишком много разных слов, "
"слово '%s' не учитывается\n", sl);
}
}
----------------------------------------------------------------------------------------------------
/* 3. Вывод таблицы */
printf ("\n%*s%s", DSLMAX, "Слово ", "Кол-во\n");
i = pt->sled; /* Указатель 1-го не фиктивного элемента списка */
while (i != baryer) /* Не дошли до барьера */
{ printf ("%-*s %5d\n", DSLMAX, i->sl, i->kol);
i = i->sled; /* К следующему элементу списка */
}
Длина поиска
Основная характеристика способа организации таблицы - средняя длина поиска элемента, пропорциональная среднему времени поиска.
Длина поиска D - количество просматриваемых при поиске элементов таблицы. D - случайная величина с возможными значениями D1=1, D2=2, ... , Dm=m, где m - количество элементов таблицы.
Из теории вероятностей известно, что среднее арифметическое значение (математическое ожидание) случайной величины X с возможными значениями X1, ..., Xm равно
m
Xср = å Xi*Pi (5.1)
i=1
где Pi - вероятность того, что X = Xi;
m
причем å Pi = P1 + ... + Pm = 1 (5.2)
i=1
По формуле (5.1) средняя длина поиска равна
m m
Dср = å Di * Pi = å i * Pi = P1 + 2*P2 + 3*P3 + ... + m*Pm (5.3)
i=1 i=1
где Pi - вероятность того, что длина поиска D=i, т.е. искомый элемент имеет в таблице порядковый номер i (i=1..m-1); Pm - сумма вероятностей того, что искомый элемент имеет номер m, и того, что он отсутствует в таблице (безуспешный поиск требует m шагов).
В частном случае, когда элементы таблицы отыскиваются одинаково часто (равновероятно), и такова же вероятность безуспешного поиска, из формулы (5.2) получим
P1 = P2 = ... = Pm-1 = Pm/2 = 1/(m+1)
Тогда из (5.3) следует, что
лин
Dср = (1/(m+1))*(1+2+...+m) = (1/(m+1))*m*(m+1)/2 = m/2
т.е. средняя длина линейного поиска - половина длины таблицы:
лин
Dср = m/2 (5.4)
Из формулы (5.3) видно, что длина поиска уменьшится, если элементы таблицы упорядочить по убыванию частоты обращения к ним (ближе размещать то, что чаще приходится искать), чтобы соблюдались неравенства
P1 ≥ P2 ≥ ... ≥ Pm.
Двоичный поиск (делением пополам)
Двоичный поиск (дихотомия, деление пополам) используется в векторе, упорядоченном по возрастанию или убыванию ключей. Каждое сравнение позволяет определить, в какой части таблицы находится искомый ключ при неравенстве ключей: до или после сравниваемого с ним ключа. Если на каждом шаге делить область поиска пополам, максимальная длина поиска из m элементов равна
дих
Dmax = log2 m + 1 (5.5)
Алгоритм 5.3. Дихотомический поиск ключа kl в упорядоченном по возрастанию векторе t (t[i-1] £ t[i] для i=1, ..., m-1)
L = 0; R = m; /* Индексы левой и правой границы поиска */
while (L < R)
{ /* (t[k] < kl для k=0, ..., L) && (t[k] >= kl для k = R ,..., m-1) */
i = (L+R) / 2; if (t[i] < kl) L = i+1; else R = i;
}
if (R < m && t[R] == kl) ... /* Нашли */
Доказательство правильности алгоритма 5.3:
а) Инвариантцикла:
(t[k]<kl для k=0, ..., L) && (t[k]>=kl для k=R, ..., m-1)
б) Конечностьцикла следует из того, что R - L убывает при каждом повторении цикла и обязательно станет нулем, т. к.: перед телом цикла L<R; средний индекс L £ i < R; на каждом шаге либо L увеличивается до i+1, либо R уменьшается до i. При L = R цикл заканчивается.
в) При R=m - ненашли (т. к. t[m] вне вектора!), иначе надо проверить t[R], поскольку он не участвует в сравнениях.
Алгоритм 5.3а. Дихотомический поиск ключа kl в упорядоченном по возрастанию векторе t (t[i-1] £ t[i] для i=1, ..., m-1) с использованием указателей L, R, j (быстрее, чем 5.3)
L = &t[0]; R = &t[m]; /* Адреса левой и правой границы поиска */
while (L < R)
{ j = L + (R - L) / 2; /* Нельзя складывать ссылки: j=(L+R)/2 */
if (*j < kl) L = j + 1; else R = j;
}
if (R < &t[m] && *R == kl) ... /* нашли */
Примечание. Разность адресов равна числу ячеек между ними, а сумма адресов бессмысленна. Поэтому в языке C запрещено сложение указателей, и среднее приходится вычислять через разность.
Двоичный поиск намного быстрее линейного, но требует, чтобы ключи образовали упорядоченный вектор. Обычно он применяется для постоянных таблиц или в случаях, когда сначала таблица заполняется, затем упорядочивается и потом уже используется только для поиска.
Древовидные таблицы
Древовидная таблица (дерево поиска) – это бинарное дерево, в котором вершины соответствуют элементам таблицы; причем ключ каждой вершины больше ключей ее левого поддерева и меньше ключей правого поддерева (рис. 5.3). Ключи могут быть любого типа (сравниваются их числовые коды).
| а) Поступающие ключи: 7, 8, 4, 9, 2, 6, 5 | в) Представление дерева |
| Ключ | Ссылки | ||
| Индекс | kl | men | bol |
| . . . | |||
| -1 | |||
| -1 | -1 | ||
| -1 | -1 | ||
| -1 | |||
| -1 | -1 | ||
| . . . |
| б) Дерево поиска | параллельными массивами |
Рис. 5.3. Древовидная таблица
Первый поступающий элемент образует корень дерева. Очередной ключ ищется в таблице, начиная с корня. После сравнения с ключом текущей вершины поиск продолжается в ее левом или правом поддереве: область поиска делится на две части, подобно дихотомии. Если нужное поддерево отсутствует (соответствующая ссылка пустая), искомого ключа нет в таблице. При включении новый элемент размещается в свободном месте памяти и подвешивается к найденной пустой ссылке, роль которой играет -1 (рис. 5.3).
Для ускорения поиска как и в последовательной таблице удобно использовать барьер с искомым ключом. Барьером заканчиваются все пути дерева: все пустые ссылки заменяются ссылками на барьер (рис. 5.4). Барьер избавляет от проверки пустоты ссылок в цикле поиска (алг. 5.4, 5.5).
Алгоритм 5.4. Создание древовидной таблицы t с барьером b
/* Описание таблицы */
struct el_tab /* Элемент таблицы */
{ Тип_ключа kl; /* Ключ */
Тип_инф inf; /* Тело элемента */
struct el_tab *men, *bol; / * Ссылки влево и вправо */
};
struct el_tab *t; /* Указатель корня дерева */
struct el_tab *b; /* Указатель барьера */
. . .
/* Инициализация пустой таблицы */
/* Создание элемента для барьера */
b = malloc (sizeof(struct el_tab)); t = b; /* "Пустая" ссылка на корень дерева */
Алгоритм 5.5. Нерекурсивный поиск и включение элемента
{kl, inf} в древовидной таблице t с барьером b
Тип_ключа kl; /* Ключ нового элемента */
Тип_инф inf; /* Тело нового элемента */
struct el_tab *i, *ip; /* Указ-ли текущего и предыд-го эл-в */
. . .
/* Поиск с барьером ключа kl в таблице t */
b->kl = kl; /* Создание барьера = kl */
for (i = t; kl != i->kl;)
{ ip = i;
if (kl < i -> kl) i = i-> men;
else i = i-> bol;
}
if (i == b) /* Не нашли (наткнулись на барьер) */
{ /* Включение элемента с ключом kl в таблицу t */
i = malloc (sizeof (struct el_tab));
if (i == NULL) ... /* Переполнение таблицы */
else /* Есть место для нового элемента */
{ i->kl=kl; i->inf=inf; /* Создание нового элемента */
i->men = i->bol = b; /* "Пустые" ссылки на барьер */
/* Прицепление нового элемента к дереву */
if (t == b) /* Дерево пусто */
t = i; /* Новый элемент - корень дерева */
else /* Прицепление нового элемента к *ip */
if (kl < ip->kl) ip -> men = i; else ip->bol = i;
}
}
else . . . /* Нашли i->kl == kl */
Алгоритм 5.6. Вывод по возрастанию ключей древовидной таблицы t с барьером b (рекурсивный обход бинарного дерева слева направо)
void pech_tab (struct el_tab *t)
{ if (t != b) /* b - "пустая" ссылка на барьер */
{ pech_tab (t -> men);
Вывод t->kl, t -> inf;
pech_tab (t -> bol);
}
}
Примечания. 1. Если нет барьера, вместо b - пустая ссылка NULL.
2. Можно использовать фиктивный корень с ключом равным 0.
Исключение элемента из древовидной таблицы показано на рис. 5.5. При исключении элемента, имеющего менее двух потомков, например, элемента с ключом 6, он уничтожается. Ссылка на него заменяется ссылкой на его потомка (она может быть и пустой).
Некоторые трудности создает исключение элемента с двумя потомками, например, элемента с ключом 7. В этом случае, чтобы не нарушить структуру дерева поиска, в исключаемый элемент пересылаются данные из элемента с ближайшим меньшим (или большим) ключом, который затем уничтожается. В алг. 5.7 это - самый правый элемент (с ключом 6) левого поддерева исключаемого элемента.
| |
Рис. 5.5. Исключение элемента с ключом 7 из древовидной таблицы
а) до исключения; б) после исключения; "и", "у" - исключаемый и уничтожаемый элементы
Ссылка на уничтожаемый элемент заменяется ссылкой на его левое поддерево (правого поддерева у него нет).
Алгоритм 5.7. Исключение элемента из древовидной таблицы с барьером b
struct el_tab **i, /* Указатель ссылки на исключаемый эл-т */
*u, /* Указатель уничтожаемого элемента */
**r; /* Указатель ссылки на уничтож-мый эл-т */
. . .
u = *i; /* Указатель исключаемого элемента */
if (u->men == b) *i = u->bol; /* Нет левого потомка */
else if (u->bol == b) *i = u->men; /* Нет правого потомка */
else /* Исключаемый элемент имеет двух потомков */
{ /* Поиск правого элемента левого поддерева исключаемого элемента */
r=&(u->men); u=u->men;
while (u->bol != b) { r=&(u->bol); u=u->bol; }
/* Пересылка уничтожаемого элемента в исключаемый элемент */
(*i)->kl=u->kl; (*i)->inf=u->inf;
*r=u->men; /* Cсылка в обход уничтожаемого элемента */
}
free (u); /* Уничтожение элемента *u */
Длина поиска в древовидной таблице зависит от конфигурации дерева, которая определяется порядком поступления ключей в таблицу. В худшем случае, когда ключи поступают по возрастанию или убыванию, дерево вырождается в одну ветку, длина поиска как в последовательной таблице:
посл
Dср = m / 2, (m - количество элементов таблицы).
В среднем по всем конфигурациям деревьев (считая их равновероятными) средняя длина поиска равна:
древ
Dср = 1.39 log2 m (5.6)
Для ускорения поиска после каждого включения и исключения элемента дерево балансируют (перестраивают). Рассмотрим два вида сбалансированных деревьев: выровненное и подравненное (рис. 5.6).
Выровненным (идеально сбалансированным) называют дерево, в котором незаполненным может быть только последний уровень (рис. 5.5а). Максимальная длина поиска в таком дереве, как при дихотомии:
выр
D max = log2 m + 1 (5.7)
Российские математики Г.М. Адельсон-Вельский и Е.М. Ландис предложили более удобный для практики критерий сбалансированности: подравненное дерево (АВЛ-дерево) - такое дерево, в котором высоты двух поддеревьев каждой вершины отличаются не более чем на 1 (рис. 5.5 б). Выровненное дерево является частным случаем АВЛ-дерева. Алгоритм балансировки АВЛ-дерева значительно проще, а максимальная длина поиска всего на 44% больше чем у выровненного дерева и приблизительно равна средней длине поиска в древовидной таблице:
АВЛ
Dmax = 1.44 log2 m (5.8)
Рис. 5.6. Сбалансированные деревья
а) Выровненное дерево б) Подравненное дерево (АВЛ-дерево)