Балансировка бинарного дерева поиска. 1. Балансировка бинарного дерева поиска

План

1. Балансировка бинарного дерева поиска

2. Упорядочивание массива методом вставки

3. Функция, упорядочивающая массив

Алгоритмы вставки элемента в бинарное дерево поиска, поиска элемента по ключу, удаления элемента из бинарного дерева поиска требуют количества операций линейно зависящее от высоты дерева .

При вставке элементов в бинарное дерево поиска дерево может иметь как вид а) так и вид б).

а) б)

Очевидно, что в случае а) высота дерева равна числу узлов. Поэтому возникает задача приведения бинарного дерева поиска к виду с высотой как можно меньше.

Введём понятие уровня узла А.

Если узел А является корнем дерева Т, он принадлежит первому уровню.

В противном случае уровень узла на единицу больше чем уровень его предка.

Бинарное дерево Т, имеющее высоту , является совершенным, если выполняются следующие условия:

1. все узлы, начиная с уровня и выше, имеют по два дочерних узла;

2.если узел, находящийся на уровне , имеет дочерние узлы, то все узлы, находящиеся на этом же уровне слева от него, имеют по два дочерних узла;

3.если узел, находящийся на уровне , имеет один дочерний узел, то он является его левым дочерним узлом.

При симметричном обходе бинарного дерева поиска узлы посещаются в порядке возрастания ключа.

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

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

Удалить исходное дерево.

Создать пустое бинарное дерево поиска.

Вставлять элементы из массива длины при помощи следующей рекурсивной функции (псевдокод).

Insert_from_array(BinaryTree *binTree, Type_elem *a, int n)

{

if(n == 0) return;

else{

Insert(binTree, a[n/2]);

Insert_from_array(binTree, a, (n/2));

Insert_from_array(binTree, &a[n/2+1],(n-(n/2)-1));

}

}

Здесь Insert(BinaryTree *binTree, Type_elem a) – функция вставляющая элемент в бинарное дерево поиска.

			…		…
			…		…

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

Доказательство по индукции.

1. При , утверждение верно.

2.Предположим, что оно верно при всех .

3.Докажем для Высота полученного дерева равна . Поскольку левое поддерево содержит не меньше вершин, чем правое, то

Утверждение доказано.

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

Бинарное дерево поиска называется сбалансированным по высоте, или просто сбалансированным, если высота правого поддерева любого его узла отличается от высоты левого поддерева не больше чем на 1.

Сбалансированное бинарное дерево поиска с узлами имеет высоту между и (см. D. Knuth, The Art of Computer Programming, v.3).

Методы балансировки бинарных деревьев, требующие существенно меньших затрат памяти, чем изложенный, не рассматриваются в данном курсе.

Дата добавления: 2014-01-20