6. Идеально сбалансированное бинарное дерево
 

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

Говорят, что бинарное дерево идеально сбалансировано, если для каждого его узла количество узлов в левом и правом поддеревьях различается не более чем на 1.

Создание идеально сбалансированного дерева не вызывает затруднений. Если число узлов и известно и дана последовательность значений поля данных вершин а[0], а[1],...,а[п - 1], то можно использовать следующий рекурсивный алгоритм построения идеально сбалансированного дерева:
1.  Начиная с а[0], берем очередное значение а[i] в качестве значения корня дерева (поддерева).
2.  Строим левое поддерево с n1 = n/2 узлами тем же cпособом.
3.  Строим правое поддерево с nr = n - nl - 1 узлами.

Таким образом, значение a[0] окажется в корне дерева, а именно на него будет ссылаться указатель дерева, а[1],...а[nl] значения попадут в левое поддерево, остальные — в правое поддерево. Следовательно, распределение значений по узлам дерева полностью определяется исходной последовательностью данных.

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

Пример.

/* ИДЕАЛЬНО СБАЛАНСИРОВАННОЕ БИНАРНОЕ ДЕРЕВО */

#include
#include
#include
typedef struct RECORD    /* Структура элемента дерева */
{ int DATA;          /* данные узла — здесь только ключ */
RECORD *LPTR,*RPTR;    /* левый и правый указатели на поддерево*/
};
RECORD *ROOT;    /* Указатель корня дерева */
static int ndi=0;
/*последовательный номер включаемого элемента ,
удобства работы пользователя и контроля наличия дерева. Перед
каждым обращением к функциям tree, preorder в вызывающей функции
переменную ndi нужно обнулять. */

RECORD* tree(int k);         /* функция создания дерева, к - число узлов*/
int preorder(RECORD *)           ;      /* функция нисходящего обхода дерева*/
void p(RECORD*);   /* Печать данных в узле */
void lnData(RECORD*);   /* Ввод данных узла*/
/* ===============================================9
/* ГЛАВНАЯ ФУНКЦИЯ */
main()
{int i,n;
printf("\n\n РАБОТА С ИДЕАЛЬНО СБАЛАНСИРОВАННЫМ БИНАРНЫМ ДЕРЕВОМ");
printf("\n Создание дерева");
printf("\n Введите число узлов дерева =>");
scanf("%d",&n);
/* Создание идеально сбалансированного дерева */
ndi=O;
if( (ROOT=tree(n))==NULL)
      { printf("\n Дерево не создано");
         getch();          /* return -1; */
}
printf("\n Обход дерева с выводом данных в узлах");
printf("\n Нисходящий обход дерева:\n");
ndi=O;    preorder(ROOT); getch();
printf("\n Конец\n"); getch(); return 0;
}
/* ПОСТРОЕНИЕ БИНАРНОГО ИДЕАЛЬНО СБАЛАНСИРОВАННОГО ДЕРЕ-ВА*/
RECORD* tree(int k)
{ RECORD *newnode;
int nl,nr;
if (k≤0)                       /* k<0 - ошибочное задание параметра */
newnode =0;
   else
    { nl = k/2;
       alloc(1,sizeof(RECORD));
InData(newnode);
newnode.LPTR=tree(nl);
newnode.RPTR=tree(nr);

}
return newnode;
}

/* НИСХОДЯЩИЙ ОБХОД ДЕРЕВА */
int preorder(RECORD *T)
  { if(T==NULL && ndi==0)
     { printf("\n Дерево пустое");
getch(); return -1;
}
if (T!=0)
{ ndi++; p(T);       /* обработка данных в узле */
preorder(T.LPTR);
preorder(T.RPTR);
}
return 0;
}

//* ОБРАБОТКА ДАННЫХ УЗЛА ДЕРЕВА */
void p(RECORD *B)
{ printf(" %d ",B.DATA);
}
/* ВВОД ДАННЫХ УЗЛА ДЕРЕВА */
void lnData(RECORD* d)
   {         printf(“Введите %d-й ключ =>",++ndi);
              scanf("%d",&d.DATA);
}

    Функция tree возвращает указатель на корень построенного дерева, а при рекурсивном обращении — указатель на очередной дочерний узел.

Идеально сбалансированное бинарное дерево, построенное из последовательности ключей: 9,17,20,16,12,21,6,3,11,4,19,14,13,1,5,2,8,18,7,10,15, будет иметь следующий вид:

Рис. Идеально сбалансированное бинарное дерево

При таком построении, несмотря на то, что идеально сбалансированное дерево является упорядоченным в смысле порядка следования вершин на каждом уровне, никакие особые требования относительно значений данных в вершинах не накладываются, т.е. значения данных в вершинах в общем случае не упорядочены. Это ведет к тому, что поиск узла с нужными данными осуществляется последовательным обходом всех n узлов дерева, затраты на поиск будут порядка О(n). Поэтому такие «простые» сбалансированные деревья применяются редко. Обычно используются сбалансированные деревья поиска, которые обеспечивают минимальную длину поиска порядка O(log₂n), где n — число узлов дерева.

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