Алгоритмы и структуры данных на С++. Аксёнова Е.А - 77 стр.

6.5.   Хеширование                                                  77


мальное дерево. Построение оптимальных деревьев сложно и требу-
ет знания вероятностей обращения к ключам. Поэтому на практике
обычно ограничиваются построением в некотором смысле ”хороших”
деревьев. Один из таких методов был предложен в 1962 году совет-
скими математиками Е. М. Ландисом и Г. М. Адельсоном-Вельским.
Они предложили AVL-деревья, или иначе – сбалансированные дере-
вья. В таком методе требуется не более C ·log2 n операций для поиска и
вставки. Но платить за это надо расходами памяти по 2 бита в каждом
узле для хранения разности высот левого и правого поддеревьев.
   Высотой бинарного дерева называется число вершин на самом длин-
ном пути от корня.
   Бинарное дерево называется сбалансированным, если высота лево-
го поддерева каждого узла отличается от высоты правого поддерева
не более чем на 1 (рис. 6.3). Существуют и другие определения сба-
лансированности.




                               Рис. 6.3


                       6.5. Хеширование

   В этом методе поиска считается, что на множестве ключей задана
некоторая функция h(K), которая называется хеш-функцией, так что
по ключу K можно сразу вычислить его порядковый номер в таблице
поиска. Например, если ключи – это числа 0, 1, 2, ..., n, то существует
простая хеш-функция h(K) = K (рис. 6.4). При хеш-поиске может