Стр. 28 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
26
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Таким образом, если вероятности обращения к ключам различаются, мы
можем строить дерево бинарного поиска исходя из некоторых предпочтений, а
не деля таблицу пополам.
Для того, чтобы явно задавать требуемую структуру бинарного поиска,
очевидно, достаточно для каждой вершины
i
хранить указатели на ее левого
i
l
или правого сына
i
r
. То есть каждая вершина будет представляться структурой
из трёх полей (
i i i
r lx
, ,
).
Для организации поиска в таком дереве вместо алгоритма 4 используется
следующий алгоритм 5.
Алгоритм №5.
i = (корень дерева>
while (i ≠
λ
)
{
╓
║ z = x
i
: < успех >;
║
case ─╢ z < x
i
: i = l
i
;
║
║ z > x
i
: i = r
i
;
╙
}
<неудача>
Поставим задачу построения оптимального дерева бинарного поиска в
общем виде.
Пусть заданы:
i
β
, где
n i
,1
=
- вероятность обращения к каждому из ключей
i
x
.
j
α
, где
n j
,0
=
- вероятность, с которой поиск заканчивается неудачей в
соответствующих листьях. Листьев неудач на 1 больше, чем вершин.
Число сравнений до неудачи – (ее уровень – 1).
Тогда среднее время поиска в таком дереве:
•
∑
=
n
i
i
1
β
<уровень узла
i
> +
∑
=
n
j
j
0
α
<уровень листа
j
- 1>
// на успех // на неудачный поиск
Очевидно, оптимальным, то есть самым быстрым, деревом бинарного
поиска, будет то, которое даст минимальную сумму.
