Рандомизированные деревья поиска

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

Доказано [8, 10], что если при построении дерева исходные данные будут поступать в случайном порядке (т. е. равновероятны все n! перестановок исходных данных), то средняя высота такого дерева будет пропорциональна log n. Считаем, что все ключи уникальны.

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

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

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

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

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

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

typedef int T_key; //тип ключа, может быть любым

typedef char T_data;//тип связанных данных, любой

struct item //структура элемента массива

{ T_key key; //ключ

T_data data; //связанные данные

};

struct node

{item data;

 int n;

 node *left, *right;

 node(item x)

 {data=x;left=right=NULL;}

};

typedef node* bst; //bst - binary seach tree

//малое правое вращение

void RightRotate(bst &root)

{ bst x;

x=root->left; root->left=x->right; x->right=root; root=x;

}

//малое левое вращение

void LeftRotate(bst &root)

{ bst x;

x=root->right; root->right=x->left; x->left=root; root=x;

}

// вставка в корень

void insert_root(bst &root, item x)

{ if (!root)// дерео пустое- терминальная ветвь

   { root=new node(x); root->n=1;

   return;

   }

   if (x.key<root->data.key)

           { insert_root(root->left,x);

           RightRotate(root); }

else

           { insert_root(root->right,x);

           LeftRotate(root); }

}

// рекурсивная функция вставки

void insert_rec(bst &root, item x)

{ if (!root)// дерео пустое- терминальная ветвь

   { root=new node(x); root->n=1;

   return;

   }

if (rand()<RAND_MAX/(root->n+1))

{ insert_root(root,x);

   return;

}

if (x.key<root->data.key) insert_rec(root->left,x);

else                 insert_rec(root->right,x);

root->n++;

return;

}

// формирование дерева из n случайных элементов

void randtree(bst &root, int n)

{ item x;

for (int i=0;i<n; i++)

{ x.key=rand()%1000;

x.data=rand()%26+65;

insert_rec(root,x);

}

}

5.6. Структуры данных, основанные на хеш-таблицах

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

В некоторых частных случаях такая задача легко решается. Например, если ключи поиска представляют собой неотрицательные целые значения в ограниченном диапазоне, то можно использовать ключ в качестве индекса элементов массива, в котором ведется поиск. Такие структуры называются таблицами прямого доступа [14]. Допустим, известно, что все ключи имеют целочисленные значения, не выходящие за пределы диапазона [0, 9999]. Тогда использование массива размером 10000 элементов обеспечит минимально возможное время выполнения всех основных операций: поиск, вставка и удаление элементов реализуются как прямой доступ по индексу к элементам этого массива.

Например, при продаже билетов в кино или на концерт схему зрительного зала можно представить в виде таблицы прямого доступа, в данном конкретном случае, двумерного массива, количество элементов которого равно размеру зрительного зала. Каждый элемент определяется двумя индексами (ряд и место) и может принимать одно из двух значений — «занято» или «свободно». Тогда продажа и возврат билетов выполняются как прямой доступ по индексам к элементам данного двумерного массива, которые одновременно являются и ключами поиска. Таблица хорошо поддается визуализации, поэтому с поиском свободных мест проблем не возникает. При хорошей наполняемости зрительного зала дополнительные расходы памяти на хранение незанятых мест будут минимальны.

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

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

Эта идея воплощена в одном распространенном методе реализации структур для поддержки поиска, который получил название хеширования (hashing). Математическая функция h(K), которая преобразует значений ключей K в индексы элементов массива, называется хеш-функцией. Сами индексы иначе называются хеш-адресами и находятся в диапазоне от 0 до M-1, где M — некоторое положительное целое число. Массив размером M, в котором ведется поиск, называется хеш-таблицей и обычно представляет собой массив записей (ключи и связанная информация или указатель на нее). В частном случае элементами хеш-таблицы могут быть просто значения ключей (числа или строки текста).

Например, пусть входная последовательность ключей имеет вид: 3 25 7 48 71. Если для организации быстрого поиска использовать таблицу прямого доступа, то она должна содержать не менее 71 элемента (значение наибольшего ключа), и из этих элементов заполненными окажутся только 5. Будем использовать простейшую хеш-функцию, применив к ключам операцию вычисления остатка от деления на размер хеш-таблицы (обозначим эту операцию K mod M). Поскольку входных данных немного, выберем M=7. Тогда все хеш-адреса будут находиться в диапазоне от 0 до 6, а хеш-таблица будет почти заполнена (см. табл. 5.). Заметим, что положение ключей в хеш-таблице не зависит от порядка их следования во входной последовательности

Таблица 5. Хеш-таблица для последовательности 3 25 7 48 71 при применении хеш-функции k mod 7

Хеш-адрес	0	1	2	3	4	5	6
Значение	7	71	пусто	3	25	пусто	48

 

Термин «хеширование» в литературе по программированию появился в 1967 году, хотя сам механизм был известен и ранее. Сама идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. (т. е. хеширование возникло еще до появления языков высокого уровня).  Глагол «hash» в английском языке означает «рубить, крошить, перемешивать», поэтому термин «хеш-таблица» в русском языке можно заменить термином «перемешанная таблица», который довольно точно соответствует сути дела. Академиком А.П. Ершовым был предложен удачный эквивалент термина «хеширование» — «расстановка» (эквивалент хеш-функции — функция расстановки). Однако русскоязычные термины используется реже, чем оригинальные английские.

Реализация алгоритмов поиска, основанных на хеш-таблицах, почти всегда представляет собой нетривиальную задачу. Для приведенного выше первого примера хеш-таблицы данные специально были подобраны таким образом, чтобы не заострять внимания на проблемах. Предположим, что нужно вставить в хеш-таблицу 5. еще одно значение ключа, на этот раз равное 8. Подсчитываем значение хеш-функции: 8 mod 7=1. Однако ячейка с хеш-адресом 1 уже занята ключом 71 и для ключа 8 требуется найти новое место. Такая ситуация иначе называется конфликтом или коллизией. В таблицах   прямого доступа коллизий не может быть в принципе, если все ключи уникальны, при применении метода хеширования коллизии являются обычным явлением, такова плата за экономию памяти.

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

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

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

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

Сначала рассмотрим наиболее часто используемые хеш-функции.