Информатика и технология программирования


         

если вершина дерева имеет индекс


Так, если вершина дерева имеет индекс n в массиве, то вершины левого и правого поддерева - 2*n и 2*n+1 соответственно. Головная вершина дерева имеет индекс, равный 1 . Кроме того, в таком массиве необходимо как-то обозначать пустые вершины (аналог указателя NULL).

Поиск в двоичном дереве требует количества сравнений, не превышающего максимальной длины ветви дерева, или максимальной длины цепочки его вершин. Следовательно, условием эффективности поиска в дереве является равенство длин его ветвей (сбалансированность). В самом крайнем случае дерево имеет одну ветвь и вырождается в односвязный список, в котором имеет место последовательный поиск. В идеальном случае, когда длины ветвей дерева отличаются не более, чем на 1 (сбалансированное дерево) и равны n или n-1 , при общем количестве вершин в дереве порядка " 2 в степени n " требуется не более n сравнений для нахождения требуемой вершины. Это соответствует характеристикам алгоритма двоичного поиска в упорядоченном массиве.

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

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





//------------------------------------------------------bk55-07.cpp

// Рекурсивный обход двоичного дерева с выводом

// значений вершин в порядке возрастания

void Scan(btree *p)
{
if (p==NULL) return;
Scan(p-&#62left);
cout &#60&#60 p-&#62val &#60&#60 endl;
Scan(p-&#62right);
}


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