Методы программирования. Громов Ю.Ю - 119 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

119
А9. [Двукратный поворот.] Установить P ← LINK(–а, R), LINK(–а, R) ←
LINK(а, P), LINK(а, P) ← R, LINK(а, S) ← LINK(–а,P), LINK(–а, P) ← S;
присвоить сначала
−=
=
=−
←
;)(если),,0(
;0)(если),0,0(
;)(если),0,(
))(),((
aPBa
PB
aPBa
RBSB
а затем В(Р) ← 0.
А10. [Последний штрих.] (Балансирующее преобразование (рис. 41)
в (рис. 42) завершено. Р указывает на корень нового поддерева, а Т –
на родительский по отношению к корню старого поддерева узел S.) Если
S = RLINK(Т), то присвоить RLINK(Т) ← Р; в противном случае присво-
ить LLINK(Т) ← Р. ■
Этот алгоритм достаточно длинный, однако разделяется на три про-
стые части: на шагах А1…А4 осуществляется поиск, на шагах А5…А7
выполняется вставка нового узла и на шагах А8…А10 при необходимости
балансируется дерево. Отметим, что алгоритм может использоваться и
для прошитых деревьев.
Известно, что для этого алгоритма требуется около
NC log
единиц
времени, где С – некоторая константа.
Упражнения
1. Выполните алгоритм A в условиях вставки в корень пустого де-
рева ключа JANUARY и дальнейшей последовательной вставки ключей
FEBRUARY, MARCH, APRIL, MAY, JUNE, JULY, AUGUST, SEPTEMBER,
OCTOBER, NOVEMBER, DECEMBER и постройте сбалансированное би-
нарное дерево, которое при этом получится.
22. ХЕШИРОВАНИЕ
До сих пор были рассмотрены методы поиска, основанные на срав-
нении данного аргумента K с ключами в таблице. Другой путь заключа-
ется в так называемом хешировании, когда отказываются от поиска по
данным и выполняют арифметические действия над K, позволяющие вы-
числить некоторую хеш-функцию h(K). Последняя укажет адрес в табли-
це, где хранится K и связанная с ним информация.
Заметим, что поиск таких функций h(K) является довольно сложной
задачей, поскольку функции, дающие неповторяющиеся значения, встре-
чаются на удивление редко. Например, в соответствии со знаменитым
«парадоксом дней рождения» получается, что в компании из двадцати
трёх человек более вероятно совпадение дней рождения у двух из них,

Страницы