Оптимизация поиска. Переупорядочивание таблицы с учетом вероятности поиска элемента. Дерево оптимального поиска.

Будем считать, что искомый элемент в таблице существует.

Можно говорить о некотором значении вероятности поиска того или иного элемента в таблице.

Тогда вся таблица поиска может быть представлена как система с дискретными состояниями, а вероятность поиска i - го элемента - это вероятность p(i) i - го состояния системы.

Количество сравнений при поиске в таблице, представленной как дискретная система, представляет собой значение дискретной случайной величины, определяемой вероятностями состояний и номерами состояний системы как математическое ожидание.

Z = C = 1p(1) + 2p(2) + 3p(3) +…+ np(n)

Желательно, чтобы

p(1) ≥ p (2) ≥ p (3) ≥ …≥ p (n).

Это минимизирует количество сравнений, то есть увеличивает эффективность. Так как последовательный поиск начинается с первого элемента, то на это место надо поставить элемент, к которому чаще всего обращаются (с наибольшей вероятностью поиска).

Если извлекаемые элементы сформировали некоторое постоянное множество, то может быть выгодным настроить дерево бинарного поиска для большей эффективности последующего поиска.

Рассмотрим деревья бинарного поиска, приведенные на рисунках a и b.

Оба дерева содержат три элемента - к1, к2, к3, где к1<к2<к3. Поиск элемента к3 требует двух сравнений для рисунка a), и только одного - для рисунка б).

Число сравнений ключей, которые необходимо сделать для извлечения некоторой записи, равно уровню этой записи в дереве бинарного поиска плюс 1.

Предположим, что:

p1 - вероятность поиска первого элемента

р2 - вероятность поиска второго элемента

р3 - вероятность поиска третьего элемента

q0 - вероятность того, что ключ меньше k1

q1 - вероятность того, что ключ больше k1

q2 - вероятность того, что ключ больше k2

q3 - вероятность того, что ключ больше k3

С1 - число сравнений в дереве «а»

С2 - число сравнений в дереве «б»

Ожидаемое число сравнений в некотором поиске есть сумма произведений вероятности того, что данный аргумент имеет некоторое заданное значение, на число сравнений, необходимых для извлечения этого значения, где сумма берется по всем возможным значениям аргумента поиска. Поэтому

 

С1 = 2р1+1р2+2р3+2q0+2q1+1q2+2q3

С2 = 2р1+3р2+1р3+2q0+2q1+3q2+1q3

Пусть заданы следующие вероятности значений ключей

•P1 = 0.1 P1 = 0.1

•P2 = 0.3 P2 = 0.1

•P3 = 0.1 P3 = 0.3

•q0 = 0.1 q0 = 0.1

•q1 = 0.2 q1 = 0.1

•q2 = 0.1 q2 = 0.1

•q3 = 0.1 q3 = 0.2

 

Тогда

•С1 = 1.6 С1 = 1.8

 

•С2 = 2.2 С2 = 1.7

 

Ожидаемое число сравнений может быть использовано как некоторая мера того, насколько "хорошо" конкретное дерево бинарного поиска подходит для некоторого данного множества ключей и некоторого заданного множества вероятностей. Так, для вероятностей, приведенных далее слева, дерево из a) является более эффективным, а для вероятностей, приведенных справа, дерево из б) является более эффективным:

Дерево бинарного поиска, которое минимизирует ожидаемое число сравнений некоторого заданного множества ключей и вероятностей, называется оптимальным.

 

Хотя алгоритм создания дерева может быть очень трудоемким, дерево, которое он создает, будет работать эффективно во всех последующих поисках. К сожалению, однако, заранее вероятности аргументов поиска редко известны.