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

Припишем каждой вершине дерева V_i вес w_i, пропорциональный частоте поиска этой вершины. Сумма весов всех вершин дает вес дерева W. Каждая вершина V_i расположена на высоте h_i, корень расположен на высоте 1. Высота вершины равна количеству операций сравнения, необходимых для поиска этой вершины. Определим средневзвешенную высоту дерева с n вершинами следующим образом: h_ср=(w₁h₁+w₂h₂+…+w_nh_n)/W. Дерево поиска, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска.

При выполнении лабораторной работы №2 будем считать вес w_i = key.