Деревья - часть 2

Для примера рассмотрим функцию включения нового элемента в качестве потомка к вершине, максимально близкой к началу. Здесь есть проблема, общая для всех деревьев и рекурсивных алгоритмов. Войдя в поддерево, невозможно производит какие-либо действия для вершин, расположенных на том же уровне, но в других поддеревьях. Поэтому задача решается так : используется функция включения с просмотром дерева на заданную глубину, а сама глубина просмотра, в свою очередь, задается равной длине минимальной ветви дерева.

//------------------------------------------------------bk55-04.cpp

//------Включение вершины в дерево на заданную глубину

int Insert(tree *ph, int v, int d)
// результат логический - вершина включена

// ph - указателя на текущую вершину

// d - текущая глубина включения

{
if (d == 0) return 0; // Ниже не просматривать

for ( int i=0; i&#60 4; i++)
if (ph- &#62child[i] == NULL)
{
tree *pn=new tree;
ph-&#62child[i]=pn;
pn-&#62val=v;
for (i=0; i&#60 4; i++) p n-&#62child[i]=NULL;
return 1;
}
else
if (Insert(ph-&#62child[i], v , d-1)) return 1;
return 0;
}
void main()
{
tree PH={ 1,{NULL,NULL,NULL,NULL}}; // пример вызова функции

Insert( &#38PH, 5, MinDepth( &#38PH));
}

Здесь впервые всплывает на поверхность свойство дерева, ради которого оно, собственно говоря, и используется. Оно соответствует пословице " Дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогрессии. Отсюда следует, как можно эффективно использовать деревья для поиска данных : если включать в вершины дерева данные таким образом, что наиболее часто используемые будут располагаться ближе к корню, и при этом анализ текущий вершин позволит сделать вывод о том, стоит ли " опускаться" в поддеревья. Рассмотрим пример. Допустим, дерево, каждая вершина которого содержит строку, организовано так, что самая короткая строка в поддереве находится в корневой вершине. Тогда при поиске слова в дереве будет соблюдаться принцип - чем оно короче, тем меньше вершин будет просмотрено.

Содержание Назад Вперед