Сбалансированные и идеально сбалансированные бинарные деревья поиска

Бинарное дерево называется сбалансированным, если для любой его вершины v высоты левого и правого поддерева, выходящих из v (т.е. поддеревьев с корнями v->left и v->right), отличаются не более чем на 1.

Бинарное дерево называется идеально сбалансированным, если длины всех ветвей, начинающихся в корне дерева и заканчивающихся в узле с хотя бы одним из нулевых указателей v->left и v->right, отличаются не более чем на 1.

В литературе встречается другое (неравносильное) определение идеально сбалансированных деревьев. Будем неазывать идеально сбалансированными’ деревьями такие деревья, для которых для каждой вершины количество элементов в левом и правом поддереве отличается не более, чем на единицу.

Следующее условие равносильно условию идеально сбалансированности дерева: длины любых двух ветвей, начинающихся в одной вершине дерева, отличаются не более чем на 1. Доказательство тривиально. Из данного условия сразу же вытекает

Теорема. Идеально сбалансированное дерево является сбалансированным.

Иными словами, можно сказать, что для идеально сбалансированного дерева полностью заполнены элементами все слои дерева, кроме, быть может, последнего. Т.о. для идеально сбалансированного дерева высоты h количество элементов лежит в пределах 2^h-1£N<2^h. из чего сразу же вытекает следующая элементарная

Теорема. Для идеально сбалансированного дерева, состоящего из N вершин, высота дерева h лежит в пределах

log₂ N < h £ 1+ log₂ N.

Оказывается, верна следующая

Теорема. Идеально сбалансированное’ дерево является идеально сбалансированным.

Доказательство. Докажем данную теорему по индукции. Для деревьев высоты не более 1 теорема верна. Пусть для деревьев высоты h теорема верна, докажем ее для деревьев высоты h +1.

По определению идеально сбалансированных’ деревьев, каждое поддерево такого дерева – идеально сбалансировано’, а по условию индукции левое и правое поддеревья корня дерева высоты h+1 – идеально сбалансированы. В идеально сбалансированных деревьях высоты l для количества элементов дерева N выполнено соотношение 2^l-1£N<2^l, из чего сразу вытекает: если у двух идеально сбалансированных деревьев количество элементов в них отличается не более, чем на единицу, то либо их высоты равны, либо (если их высоты, соответственно, равны 2^l-1 и 2^l) в меньшем дереве последний слой полностью заполнен. В обоих случаях длины всех ветвей обоих деревьев, начинающихся в корне, заканчивающихся в вершинах, не имеющих хотя бы одного потомка, отличаются не более, чем на единицу. Отсюда сразу вытекает, что и для дерева, полученного с помощью объединения двух таких деревьев с помощью общего корневого элемента, длины всех ветвей, начинающихся в корне, заканчивающихся в вершинах, не имеющих хотя бы одного потомка, отличаются не более, чем на единицу.

¢

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

Теорема. Для сбалансированного дерева, состоящего из N вершин, высота дерева h имеет оценку:

h =Q(log₂ N).

Доказательство. Пусть t_n – минимальное количество элементов в сбалансированном дереве высоты n. Тогда верна рекурсивная формула

t_n=t_n-1+t_n-2+1

т.е. для сбалансированного дерева высоты n с минимальным количеством вершин одно из поддеревьев, дочерних корневому элементу, должно быть сбалансированным деревом высоты n-1 с минимальным количеством вершин, а другое - сбалансированным деревом высоты n-2 с минимальным количеством вершин.

Уравнение t_n-t_n-1-t_n-2=1 имеет общее решение вида

t_n=с₁l₁ⁿ + с₁l₂ⁿ –1

где l_i являются решениями уравнения l²-l-1=0. Из этого следует, что

t_n= (1+sqrt(5))/2)ⁿ (1+o(1))

после логарифмирования последнего равенства мы сразу получаем требуемое соотношение:

log₂ C₁ + log₂ t_n ≥ n log₂ ((sqrt(5)+1)/2)

n ≤ (log₂ t_n + log₂ C₁)/ log₂ ((sqrt(5)+1)/2)

для некоторого C₁>0. Или, в исходных обозначениях,:

h ≤ log₂ N / log₂ ((sqrt(5)-1)/2)+ log₂ C ≤ 1.45 log₂ N+ log₂ C

¢

---

Дата добавления: 2015-10-30