> укладений між 0 і 255.
unsigned char HashIndexType; Hash (char * str) {h=0; (* str) h +=* str ++; h;
}
VI. Виключає АБО для рядків змінної довжини ( розмір таблиці дорівнює 256 ). Цей метод аналогічний аддитивному, але успішно розрізняє схожі слова і анаграми (адитивний метод дасть одне значення для XY і YX).
VII. Метод, як легко здогадатися, полягає в тому, що до елементів рядка послідовно застосовується операція виключає або raquo ;. У наступне алгоритмі додається випадкова компонента, щоб ще поліпшити результат.
typedef unsigned char HashIndexType; char Rand8 [256]; Hash (char * str) {char h=0; (* str) h=Rand8 [h ^ * str ++];
return h;
}
Тут Rand8 - таблиця з 256 восьмибітових випадкових чисел. Їх точний порядок не критичний. Коріння цього методу лежать в криптографії; він виявився цілком ефективним.
VIII. Виключає АБО для рядків змінної довжини ( розмір таблиці lt;=65536 ). Якщо ми хешіруем рядок двічі, ми отримаємо хеш-значення для таблиці будь-якої довжини до 65536. Коли рядок хешіруется вдруге, до першого символу додається 1. Отримувані два 8-бітових числа об'єднуються в одне 16-бітове.
typedef unsigned short int HashIndexType; char Rand8 [256]; Hash (char * str) {h; char h1, h2; (* str == 0) return 0;=* str; h2=* str + 1; ++; (* str) {= Rand8 [h1 ^ * str];=Rand8 [h2 ^ * str]; ++;
}
/* h is in range 0.65535 * /=((HashIndexType) h1 lt; lt; 8) | (HashIndexType) h2;
/* use division method to scale */
return h% HashTableSize
}
Розмір хеш-таблиці повинен бути достатньо великим, щоб у ній залишалося розумно велике число порожніх місць. Чим менше таблиця, тим більше середній час пошуку ключа в ній. Хеш-таблицю можна розглядати як сукупність пов'язаних списків. У міру того, як таблиця росте, збільшується кількість списків і, відповідно, середнє число вузлів в кожному списку зменшується. Нехай кількість елементів дорівнює n . Якщо розмір таблиці дорівнює 1, то таблиця вироджується в один список довжини n . Якщо розмір таблиці дорівнює 2 і хешування ідеально, то нам доведеться мати справу з двома списками по n /100 елементів у кожному. Це сильно зменшує довжину списку, в якому потрібно шукати.
1.2 АВЛ-дерево
АВЛ-дерево - збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев розрізняється не більше ніж на 1.
АВЛ-дерева названі за першими літерами прізвищ їх винахідників, Г.М. Адельсона-Бєльського і Е.М. Ландіса, які вперше запропонували використовувати АВЛ-дерева в 1962.
Загальні властивості
У АВЛ-дереві висоти h є не менше F h вузлів, де F h - число Фібоначчі. Оскільки
,
де - золотий перетин,
то маємо оцінку на висоту АВЛ-дерева h = O ( log ( n )), де n - число вузлів. Слід пам'ятати, що O ( log ( n )) - мажоранту, і її можна використовувати тільки для оцінки (Наприклад, якщо в дереві тільки два вузла, значить в дереві два рівні, хоча log (2)=1). Для точної оцінки глибини дерева слід використовувати налаштовувану підпрограму.
TreeDepth (Tree: TAVLTree): byte;
beginTree lt; gt; nil then:=1 + Max (TreeDepth (Tree ^. left), TreeDepth (Tree ^. right))
else:=0 ;;
Тип дерева можна описати так
TKey=LongInt;=LongInt;=- 1.1;=^ TAVLNode;=record, right: TAVLTree;
key: TKey ;: TInfo;
{Поле визначальне сбалансированность вершини}: TBalance ;;
Балансування
Щодо АВЛ-дерева балансуванням вершини називається операція, яка у разі різниці висот лівого і правого піддерев=2, змінює зв'язку предок-нащадок в поддереве даної вершини так, що різниця стає lt;=1, інакше нічого не змінює. Зазначений результат виходить обертаннями поддерева даної вершини.
Використовуються 4 типу обертань:
. Мале ліве обертання
Дане обертання використовуєть...
