Оптимальным назовем дерево, высота которого минимальна. Это означает, что у него заполнены все уровни, кроме, быть может, последнего. Алгоритм построения оптимального дерева заключается в следующем:
- отсортируем ключи и средний из них поместим в корень
- левым сыном сделаем ключ, являющийся средним среди ключей слева от корня
- правым сыном сделаем ключ, являющийся средним среди ключей справа от корня
- точно также поступим при выборе сыновей каждого из узлов.
Ниже представлен текст функции, формирующей оптимальное дерево.
const int LEFT=0;
const int RIGHT=1;
struct NODE {
int Info;
struct NODE *Left;
struct NODE *Right;
};
NODE *CreateOptimalTree(int KeyArray[], int m, int n){
/*создать оптимальное дерево из ключей отрезка от m до n
сортированного массива ключей KeyArray */
int k;
NODE *Root;
if(n<m) return NULL;
Root=new NODE;
k=(n+m)/2;
Root->Info=KeyArray[k];
if(n==m){
Root->Left=NULL;
Root->Right=NULL;
} else {
Root->Left=CreateOptimalTree(KeyArray,m,k-1);
Root->Right=CreateOptimalTree(KeyArray,k+1,n);
}
return Root;
}
Построение оптимальных деревьев имеет смысл для статических деревьев, то есть для таких, для которых операции вставки и удаления отсутствуют. Восстановление оптимальности после вставки или удаления требует полного перестроения дерева.
