Открытое перемешивание
Перемешанная таблица, использующая открытое перемешивание (или перемешивание сложением), обладает следующими свойствами:
Вся перемешанная таблица отображается вектором;
Размер таблицы (вектора) должен быть достаточным для размещения всех элементов таблицы (что очевидно) и отображения их ключей (так как значение ключа отображается в индекс вектора);
Разделение таблицы на две области является весьма условным и зависит от конкретных значений ключей включаемых в таблицу элементов (в одной ситуации некоторый элемент вектора может быть отнесен к основной области, в другой – этот же элемент принадлежит области переполнения).
Рассмотрим способ открытого перемешивания на примере выполнения операции включения элементов в таблицу.
Пусть дана следующая последовательность ключей элементов, записываемых в таблицу (всего 15 элементов):
12, 48, 3, 5, 7, 63, 15, 202, 103, 188, 30, 43, 6, 18, 19
Прежде всего выберем функцию расстановки. Возьмем для примера функцию
I(k) = k%10;
Тогда данная функция расстановки отобразит исходное множество ключей в следующее множество производных ключей:
номер элемента |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
исходный ключ |
12 |
48 |
3 |
5 |
7 |
63 |
15 |
202 |
103 |
188 |
30 |
43 |
6 |
18 |
19 |
производный ключ |
2 |
8 |
3 |
5 |
7 |
3 |
5 |
2 |
3 |
8 |
0 |
3 |
6 |
8 |
9 |
Пусть размер таблицы равен M = 14 элементам (размер выбран так, чтобы показать реакцию на переполнение таблицы). В исходном состоянии таблица пуста.
При занесении элемента в таблицу, прежде всего, вычисляется производный ключ и анализируется позиция таблицы, которая определяется значением производного ключа. Если эта позиция свободна (что имеет место для первых пяти элементов), элемент заносится в таблицу (в основную область), и для занесения потребуется только одно обращение к таблице. Таким образом, после записи в таблицу первых пяти элементов таблица будет иметь вид, представленный на рис. II–47,а.
Рис. II–26
Если позиция таблицы занята, что имеет место, например, при записи в таблицу элемента с ключом 63, тогда начинается процесс перемешивания: последовательно выбираются следующие позиции таблицы с целью найти свободную. Определение "открытое перемешивание" обусловлено тем свойством, что элементы таблицы, просматриваемые, начиная с конкретной позиции, являются открытыми для ключей, отображаемых в другие позиции. Как только свободная позиция будет найдена, элемент записывается в нее, и эта позиция считается принадлежащей области переполнения (рис. II–47,b; позиции таблицы, относящиеся к области переполнения, выделены цветом). В соответствии с описанным выше алгоритмом в таблицу будут записаны первые 14 элементов, после чего таблица примет вид, представленный на рис. II–47,c.
Если же при поиске свободной позиции мы возвращаемся в исходную точку, что происходит при попытке записать в таблицу последний элемент с ключом 19 (рис. II–47,c), это означает, что в таблице нет свободного места.
В результате для занесения элемента в таблицу в общем случае требуется несколько обращений. Например, при занесении в таблицу элементов с ключами 63 и 15 потребуется по 2 обращения к таблице, а при занесении элемента с ключом 202 – 8 обращений. Количество обращений при занесении в таблицу каждого элементов представлено ниже:
исходный ключ |
12 |
48 |
3 |
5 |
7 |
63 |
15 |
202 |
103 |
188 |
30 |
43 |
6 |
18 |
производный ключ |
2 |
8 |
3 |
5 |
7 |
3 |
5 |
2 |
3 |
8 |
0 |
3 |
6 |
8 |
количество обращений |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
8 |
8 |
4 |
1 |
10 |
8 |
8 |
Суммарное
количество обращений к таблице равно
56, среднее –
.
Важный результат, который всегда необходимо учитывать при построении функции расстановки, состоит в том, что для случайных записей средняя длина поиска минимизируется, если функция расстановки отображает одинаковое количество ключей на все позиции таблицы-вектора от 1 до M. Вообще говоря, это условие может оказаться невыполнимым по разным причинам (в приведенном выше примере это условие не выполняется). В таких случаях следует, насколько это возможно, приблизить отображение к такой желаемой форме (лучшим вариантом функции расстановки была бы функция I(k) = k % M).
В приведенном выше примере скопление записей образовалось после третьей позиции, в результате чего для занесения элемента с ключом 202 потребовалось 8 обращений к таблице. Подобное скопление неизбежно при использовании открытого перемешивания. Можно несколько улучшить результаты, если переопределить понятие следующей позиции таблицы. В общем случае использование открытого перемешивания при определении следующей позиции требует увеличения индекса элемента на некоторую величину h, называемую шагом перемешивания (другими словами, значение индекса складывается с шагом перемешивания; поэтому открытое перемешивание называют еще перемешиванием сложением). Значение шага перемешивания может быть любым, но обязательно взаимно простым с величиной, определяющей размер таблицы, чтобы обеспечить просмотр всех ее позиций (например, для таблицы размером 14 элементов можно использовать шаг перемешивания 3 или 5, но нельзя 2 или 6). Выбор шага перемешивания может повлиять на количество обращений к таблице.
В приведенном выше примере был использован шаг перемешивания, равный 1. Если для той же последовательности ключей использовать другое значение шага перемешивания, например, 5, получим следующее количество обращений к таблице:
h = 5
исходный ключ |
12 |
48 |
3 |
5 |
7 |
63 |
15 |
202 |
103 |
188 |
30 |
43 |
6 |
18 |
производный ключ |
2 |
8 |
3 |
5 |
7 |
3 |
5 |
2 |
3 |
8 |
0 |
3 |
6 |
8 |
количество обращений |
1 |
1 |
1 |
1 |
1 |
3 |
2 |
3 |
4 |
4 |
1 |
9 |
1 |
10 |
Суммарное
количество обращений к таблице равно
42, среднее –
.
При занесении элементов в таблицу нужно иметь возможность определять, занята позиция таблицы или свободна. Для этого достаточно включить в элемент таблицы дополнительное поле занятости (по аналогии с динамической просматриваемой таблицей-вектором: значение 0 в этом поле указывает на то, что позиция свободна); тогда структура элемента таблицы может быть представлена следующим образом;
struct Item{
int busy; /* признак занятости позиции таблицы */
int key;
Type info;
};
Алгоритм занесения элемента в перемешанную таблицу с использованием открытого перемешивания приведен на рис. II–48.
Рис. II–27
Поиск элемента осуществляется по такому же правилу: вычисляется производный ключ и анализируется позиция таблицы, которая определяется значением производного ключа. Если искомый ключ находится в этой позиции, поиск завершен успешно, причем потребовалось только одно обращение к таблице. Если позиция свободна, поиск заканчивается не успешно – в таблице нет элемента с искомым ключом. Если позиция таблицы занята, но ключи не совпадают, выбирается и анализируется следующий элемент таблицы (с учетом используемого шага перемешивания).
Из-за эффекта скопления записей, отмеченного выше, не так просто определить среднюю длину поиска в перемешанной таблице, использующей открытое перемешивание. Кроме того, средняя длина поиска будет зависеть также и от степени заполненности таблицы. В книге Ф. Хопгуд. Методы компиляции. – М.: Мир, 1972. (стр. 33) приведена следующая оценка средней длины поиска в предположении, что в скоплении все записи, отображенные в i-ю позицию, появились раньше записей, отображенных в (i+1)-ю позицию:
,
где 
– степень заполнения таблицы,
M – размер таблицы,
N – число записей, уже включенных в таблицу.
Важно отметить, что значения, полученные для средней длины поиска, не зависят от размера таблицы, а зависят только от того, насколько заполнена таблица. Даже для таблицы, заполненной на 80%, средняя длина поиска все еще равна приблизительно 3.
Если для таблицы определена операция удаления элемента, нужно иметь в виду следующее:
При удалении элемента нельзя перемещать информацию в таблице, так как это может привести к нарушению пути доступа к элементу, и элемент, занесенный в таблицу до выполнения операции удаления, в дальнейшем может быть не найден. Достаточно отметить найденную позицию, в которой находится удаляемый элемент, как удаленную.
При занесении в таблицу нового элемента удаленная позиция должна рассматриваться как свободная.
При поиске элемента удаленная позиция не должна рассматриваться ни как свободная (иначе нельзя будет найти элементы, занесенные в таблицу перед удалением элемента и расположенные после него), ни как занятая; она должна просто пропускаться.
Алгоритм поиска элемента в перемешанной таблице, использующей открытое перемешивание, приведен на рис. II–49.
Рис. II–28
Алгоритм удаления элемента достаточно прост и здесь не приводится.
Функции занесения элемента и поиска элемента в перемешанной таблице приводятся ниже, а также в файле tab3vec.cpp.
struct Item{
int busy; /* 0 – позиция свободна, 1 – занята, (-1) – удалена */
int key;
Type info;
};
const int M = 100; /* размер таблицы */
Item ptable[M]; /* таблица */
/* хеш-функция */
int I(int k)
{
return k % M;
}
/* Занесение нового элемента в таблицу.
* Результат: 0, если элемент включен в таблицу,
* -1, если в таблице есть элемент с заданным ключом,
* -2, если в таблице нет свободного места
*/
int insert(int k, Type in)
{
int strt, i, h = 1; /* шаг перемешивания */
/* вычисление исходной позиции таблицы */
strt = i = I(k);
while(ptable[i].busy > 0){ /* позиция занята */
if(ptable[i].key == k)
return -1; /* элемент с заданным ключом есть в таблице */
i = (i+h) % M; /* следующая позиция */
if(i == strt)
return -2; /* вернулись в исходную позицию – таблица полна */
}
/* занесение нового элемента */
ptable[i].key = k;
ptable[i].busy = 1;
ptable[i].info = dup(in);
return 0; /* элемент занесен */
}
/* Поиск элемента в таблице.
* Результат: индекс элемента таблицы, если элемент найден,
* -1, если в таблице нет элемента с заданным ключом
*/
int search(int k)
{
int strt, i, h = 1; /* шаг перемешивания */
/* вычисление исходной позиции таблицы */
strt = i = I(k);
while(ptable[i].busy != 0){ /* позиция не свободна */
if(ptable[i].busy > 0 && ptable[i].key == k)
return i; /* элемент найден */
i = (i+h) % M; /* следующая позиция */
if(i == strt)
break;
}
return -1; /* вернулись в исходную позицию – элемента в таблице нет */
}
Хэш таблица, использующая перемешивание сложением: определение, основные операции, особенности их реализации.
Деревья: определение, разновидности деревьев. Представление произвольного дерева с помощью двоичного дерева. Операции обхода дерева.
Дерево – это иерархическая структура, состоящая из множества вершин (или элементов). Каждая вершина дерева относится к определенному уровню и обладает тем свойством, что, помимо внутренней информации, в ней также содержатся указатели на вершины более низкого уровня.
Понятие уровня основано на следующих положениях (рис. II–5):
Рис. II–29.
каждое дерево должно иметь одну самую верхнюю вершину, на которую не указывает ни одна из других вершин. Такую вершину называют корнем дерева;
ни одна вершина не может указывать на вершину, определенную ранее (на предыдущих уровнях);
вершины, на которые указывает корень дерева, являются вершинами первого уровня; они, в свою очередь, указывают на вершины второго уровня, и так далее. Вершина (n-1)-го уровня указывает на вершину n-го, более низкого, уровня;
на самом нижнем уровне дерева размещаются вершины, определяемые как листья – вершины, которые не указывают ни на одну другую вершину дерева и состоят из внешних по отношению к дереву структур данных;
указатели в дереве всегда расположены так, что от корня к любой вершине дерева, в том числе и к любому листу, существует только один путь.
Дерево определяет рекурсивную структуру данных, которую можно определить следующим образом:
Дерево представляет собой множество вершин, которое либо является пустым, либо состоит из корня и некоторого множества починенных ему поддеревьев. Каждое поддерево представляет собой дерево.
Частным случаем дерева, широко используемым при решении различных задач, является двоичное дерево, каждая вершина которого указывает не более чем на две вершины более низкого уровня, определяющие левое и правое поддеревья. На рис. II–6 схематически изображено двоичное дерево, представляющее выражение (a+b)*(c-d).
Рис. II–30
Левое и правое поддеревья в двоичном дереве не являются эквивалентными. Так, если рассмотреть два двоичных дерева, каждое из которых состоит только из двух вершин, но одно дерево представляет собой корень и левое поддерево, а другое – корень и правое поддерево, то эти два дерева определяют разные структуры (рис. II–7).
Рис. II–31
Примечание: если бы приведенные на рис. II–7 структуры были определены как обычное – не двоичное дерево, тогда они были бы эквивалентными.
Разработанные логические структуры определяют набор алгоритмов их обработки. Реализация алгоритма зависит от организации внутренних (физических) структур данных – или от способа представления данных в памяти компьютера.
Бинарные деревья поиска: определение, обход дерева, операции поиска. Поиск по ключу, минимума и максимума. Оценки эффективности.
В соответствии с данным выше определением дерева бинарное дерево можно определить как конечное множество узлов, которое либо пусто, либо состоит из корня и двух поддеревьев – левого и правого, каждое из которых является бинарным деревом. Бинарное дерево является упорядоченным, так как для него имеет значение относительный порядок поддеревьев.
Деревья наиболее естественно отображаются в памяти ЭВМ сетями. При отображении двоичного дерева каждый элемент сети, помимо информации, содержит два указателя – на левое и правое поддеревья. Элемент бинарного дерева может быть представлен следующей структурой:
struct Node{
Type info; /* информация, располагаемая в узле дерева */
Node *left; /* указатель на левое поддерево */
Node *right; /* указатель на правое поддерево */
};
Само дерево задается указателем на корень:
Node *proot;
Если дерево пусто, то указатель на корень дерева имеет пустое (NULL) значение. Пусть ptr определяет указатель на некоторый узел дерева (если дерево не пусто, такой узел обязательно найдется). Тогда ptr->left определяет левое поддерево данного узла, а ptr->right – правое поддерево. Если левое и/или правое поддерево пусты, соответствующее поле (ptr->left и/или ptr->right) будет иметь пустое значение.
Для работы с древовидными структурами имеется множество алгоритмов, и во всех этих алгоритмах неизменно встречается одна и та же идея – прохождение, или обход дерева:
Обход дерева – это способ методичного исследования узлов дерева, при котором каждый узел проходится (исследуется) точно один раз.
Полный обход дерева дает линейную расстановку узлов дерева.
Для обхода дерева можно воспользоваться тремя алгоритмами: можно проходить узлы в прямом (прямой обход), обратном (обратный обход) и концевом (концевой обход) порядках. Эти три обхода определяются рекурсивно. Если бинарное дерево пусто, оно проходится без выполнения каких-либо действий; в противном случае прохождение выполняется в три этапа:
Прямой обход дерева (КЛП):
попасть в корень (К),
пройти левое поддерево (Л),
пройти правое поддерево (П).
Обратный обход дерева (ЛКП):
пройти левое поддерево (Л),
попасть в корень (К),
пройти правое поддерево (П).
Концевой обход дерева (ЛПК):
пройти левое поддерево (Л),
пройти правое поддерево (П),
попасть в корень (К).
Примеры обходов дерева приведены на рис. II–32.
Рис. II–32
В силу рекурсивности структуры двоичного дерева реализация алгоритмов обхода дерева оказывается очень простой, если система программирования допускает создание рекурсивных функций. Так как язык С/С++ обладает такими возможностями, функции обхода дерева, написанные на С/С++, выглядят следующим образом:
struct Node{
char *info; /* информация, располагаемая в узле дерева */
Node *left; /* указатель на левое поддерево */
Node *right; /* указатель на правое поддерево */
};
int cnt; /* порядковый номер узла дерева в процессе обхода */
/* прямой обход дерева */
void straight(Node *root)
{
/* если дерево пусто, не выполнять никаких действий – обход дерева завершается */
if(!root)
return;
/* здесь выполняется необходимая обработка корня – например,
вывод информации в выходной поток */
printf("%d. \"%s\"\n", ++cnt, root->info);
/* обход левого поддерева */
straight(root->left);
/* обход правого поддерева */
straight(root->right);
}
/* обратный обход дерева */
void reverse(Node *root)
{
/* если дерево пусто, не выполнять никаких действий – обход дерева завершается */
if(!root)
return;
/* обход левого поддерева */
reverse(root->left);
/* здесь выполняется необходимая обработка корня – например,
вывод информации в выходной поток */
printf("%d. \"%s\"\n", ++cnt, root->info);
/* обход правого поддерева */
reverse(root->right);
}
/* концевой обход дерева */
void tail(Node *root)
{
/* если дерево пусто, не выполнять никаких действий – обход дерева завершается */
if(!root)
return;
/* обход левого поддерева */
tail(root->left);
/* обход правого поддерева */
tail(root->right);
/* здесь выполняется необходимая обработка корня – например,
вывод информации в выходной поток */
printf("%d. \"%s\"\n", ++cnt, root->info);
}
Бинарные деревья поиска: поиск предшествующего и последующего элементов. Оценки эффективности.