Программная инженерия Нижний Новгород 017 Лабораторный

2.2.3. Таблицы на основе деревьев поиска 
Снижение трудоемкости операций вставки и удаления за счет исключения перепаковок 
может быть обеспечено при использовании списковых структур хранения. При этом 
сохранение эффективности двоичного поиска требует прямого доступа к звену со средней 
записью таблицы; из этого звена должна существовать возможность доступа к средним 
записям левой и правой частей таблицы и т.д. Данные требования могут быть обеспечены при 
использовании деревьев поиска для представления таблиц.
Использование деревьев поиска обеспечивает сложность в среднем log
2
N для всех 
операций обработки (поиска, вставки и удаления) таблиц 
N
T
ср
2
log

Максимальная сложность обработки деревьев поиска имеет порядок N (в случае 
вырождения дерева в список). 
Для исключения вырожденных случаев деревья поиска обобщаются до сбалансированных 
деревьев поиска, в которых высота поддеревьев для любых узлов отличаются не более чем на 
1. Подобные деревья обеспечивают сложность порядка log
2
N для любых вариантов исходных 
данных, но требуют расхода времени на проведение балансировки (методы балансировки 
деревьев поиска могут быть рассмотрены в качестве дополнительного задания).
2.2.4. Таблицы с вычисляемыми адресами 
Иной возможный способ построения таблиц при большом количестве записей состоит в 
предварительном 
(перед 
непосредственным 
поиском 
по 
таблице) 
вычислении 
месторасположения искомой записи. Данный метод предполагает наличие некоторой простой 
функции h(key), которая отображает множество имен на множество номеров строк таблицы. 
Эта функция называется функцией хеширования или расстановки; таблицы, получаемые при 
таком способе построения, называются хеш-таблицами, таблицами с вычисляемыми 
адресами или перемешиваемыми таблицами. 
Функции расстановки могут быть построены разными способами. Например, в качестве 
номера строки, в которой хранится или будет храниться при вставке некоторый ключ, можно 
взять код первого символа имени, либо сумму всех кодов символов ключа по модулю числа 
М, где М – длина таблицы (размер массива, отведённого для её хранения). 
При использовании таблиц с вычисляемыми адресами может возникнуть ряд 
дополнительных проблем. Так, например, при вставке новой записи функция расстановки 
может выдать номер занятой строки массива (функция расстановки может определять одни и 
те же значения для нескольких разных ключей). Такая ситуация при вставке записи называется 
относительным переполнением таблицы или коллизией. При возникновении коллизий 
возможны разные методы их разрешения. Рассмотрим два из них: 

метод открытого перемешивания состоит в добавлении к вычисленному 
занятому 
номеру 
некоторого 
фиксированного 
смещения 
(повторное 

---

 
95 
перемешивание) 
N
p
k
k
mod
)
(
'


; если новый адрес k’ также является занятым, 
следует повторить процедуру повторного перемешивания до тех пор, пока не 
обнаружится свободная строка, либо таблица не будет исчерпана (если значения p 
и N являются взаимнопростыми, открытое перемешивание обеспечивает 
нахождение свободной строки массива); 

метод цепочек при возникновении коллизий формирует линейные списки 
(цепочки), в каждом из которых располагаются записи с одинаковым значением 
функции расстановки (в этом случае в строках массива для размещения записей 
следует добавить ещё одно поле для ссылки на следующее звено списка). 
Среднее количество просматриваемых записей при поиске записи в перемешиваемых 
таблицах при предположении равной вероятности использования ключей и при 
использовании функции расстановки с равномерным рассеиванием ключей по строкам 
массива определяется следующим соотношением (разрешение коллизий по методу открытого 
перемешивания): 


)
1
(
2
/
1





ср
T
где

 – коэффициент заполненности таблицы (

=N/M); 
M – количество строк в массиве для хранения записей; 
N – количество записей в таблице. 
Следует отметить, что количество сравнений при поиске в перемешиваемых таблицах 
зависит не от количества записей в таблице, а от заполненности памяти, отведённой для 
размещения записей. Для примера, при заполненности массива на 75% (

=0.75) количество 
сравнений в среднем равно 2.5.