Информатика и технология программирования
Деревья - часть 2
Для примера рассмотрим функцию включения нового элемента в качестве потомка к вершине, максимально близкой к началу. Здесь есть проблема, общая для всех деревьев и рекурсивных алгоритмов. Войдя в поддерево, невозможно производит какие-либо действия для вершин, расположенных на том же уровне, но в других поддеревьях. Поэтому задача решается так : используется функция включения с просмотром дерева на заданную глубину, а сама глубина просмотра, в свою очередь, задается равной длине минимальной ветви дерева.
//------------------------------------------------------bk55-04.cpp
//------Включение вершины в дерево на заданную глубину
int Insert(tree *ph, int v, int d)
// результат логический - вершина включена
// ph - указателя на текущую вершину
// d - текущая глубина включения
{
if (d == 0) return 0; // Ниже не просматривать
for ( int i=0; i< 4; i++)
if (ph- >child[i] == NULL)
{
tree *pn=new tree;
ph->child[i]=pn;
pn->val=v;
for (i=0; i< 4; i++) p n->child[i]=NULL;
return 1;
}
else
if (Insert(ph->child[i], v , d-1)) return 1;
return 0;
}
void main()
{
tree PH={ 1,{NULL,NULL,NULL,NULL}}; // пример вызова функции
Insert( &PH, 5, MinDepth( &PH));
}
Здесь впервые всплывает на поверхность свойство дерева, ради которого оно, собственно говоря, и используется. Оно соответствует пословице " Дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогрессии. Отсюда следует, как можно эффективно использовать деревья для поиска данных : если включать в вершины дерева данные таким образом, что наиболее часто используемые будут располагаться ближе к корню, и при этом анализ текущий вершин позволит сделать вывод о том, стоит ли " опускаться" в поддеревья. Рассмотрим пример. Допустим, дерево, каждая вершина которого содержит строку, организовано так, что самая короткая строка в поддереве находится в корневой вершине. Тогда при поиске слова в дереве будет соблюдаться принцип - чем оно короче, тем меньше вершин будет просмотрено.