tify"> i
(i = 0, ..., k- 1). Розглянемо найгірший варіант роботи алгоритму BSEARCH . Число порівнянь M, необхідних для відшукання заданого ключа, max (M) = k {(k-1) - рівень вершини і k = log 2 (N +1 ) Гњ N = 2 k -1}.
Нехай всі записи рівноймовірні і N COMP (i) -1 рівень ключа k i в двійковому дереві. Тоді N COMP < i> (i) - є число порівнянь, необхідних для відшукання k i. Середнє число порівнянь тепер визначається за допомогою виразу:
де
Розглянемо величину S k - суму членів геометричної прогресії
В В
або і
В
Інтерфейс програми
Програма складається з двох частин або форм. p align="justify"> Перша частина - програма Chain формує пов'язану хеш-таблицю. Введіть число створюваних списків у полі Table Creation (Створення таблиці). Позначте опцію Sort Lists (Впорядковані списки), якщо хочете, щоб програма використовувала сортовані списки. Потім клацніть по кнопці Create Table (Створити таблицю), і програма сформує хеш-таблицю. Можна вводити інші значення і неодноразово використовувати кнопку Create Table, щоб створювати нові хеш-таблиці.
Хеш-таблиці, що містять велику кількість елементів, найбільш цікаві, тому програма Chain дозволяє заповнювати таблицю випадковими елементами. Введіть число елементів і максимальне значення елементів в області Random Items (Випадкові елементи). Потім клацніть по кнопці Create Items (Створити елементи), і програма додасть випадкові елементи в хеш-таблицю.
І нарешті, введіть ...
