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


Двоичное дерево - часть 2


Так, если вершина дерева имеет индекс 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);
}




Начало  Назад  Вперед



Книжный магазин