logo search
УП_САОД_2003

Оптимальные деревья поиска

При поиске в двоичном дереве одни элементы могут искаться чаще, чем другие, то есть существуют вероятности pk поиска k-го элемента и для различных элементов эти вероятности неодинаковы. Можно сразу предположить, что поиск в дереве в среднем будет более быстрым, если те элементы, которые ищутся чаще, будут находиться ближе к корню дерева.

Пусть даны 2n+1 вероятностей p1, p2, …, pn, q0, q1, …, qn, где

pi – вероятность того, что аргументом поиска является Ki;

qi – вероятность того, что аргумент поиска лежит между Ki и Ki+1;

q0 – вероятность того, что аргумент поиска меньше, чем K1;

qn – вероятность того, что аргумент поиска больше, чем Kn;

Тогда цена дерева поиска C будет определяться следующим образом:

где levelrootj – уровень узла j, а levellistk – уровень листа k.

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

Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска (см. п. 3.3.4.2), которое будет далеко от оптимального.

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

Существуют алгоритмы, которые позволяют построить оптимальное дерево поиска. К ним относится, например, алгоритм Гарсия-Воча. Однако такие алгоритмы имеют временную сложность порядка O(n2), а некоторые еще имеют такую же пространственную сложность. Таким образом, создание оптимальных деревьев поиска требует больших накладных затрат, что не всегда оправдывает выигрыш при быстром поиске.