КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Сбалансированные деревья
Оптимальные деревья Оптимальным назовем дерево, высота которого минимальна. Это означает, что у него заполнены все уровни, кроме, быть может, последнего. Алгоритм построения оптимального дерева заключается в следующем: - отсортируем ключи и средний из них поместим в корень - левым сыном сделаем ключ, являющийся средним среди ключей слева от корня - правым сыном сделаем ключ, являющийся средним среди ключей справа от корня - точно также поступим при выборе сыновей каждого из узлов. Ниже представлен текст функции, формирующей оптимальное дерево. const int LEFT=0; const int RIGHT=1; struct NODE { int Info; struct NODE *Left; struct NODE *Right; }; NODE *CreateOptimalTree(int KeyArray[], int m, int n){ /*создать оптимальное дерево из ключей отрезка от m до n сортированного массива ключей KeyArray */ int k; NODE *Root; if(n<m) return NULL; Root=new NODE; k=(n+m)/2; Root->Info=KeyArray[k]; if(n==m){ Root->Left=NULL; Root->Right=NULL; } else { Root->Left=CreateOptimalTree(KeyArray,m,k-1); Root->Right=CreateOptimalTree(KeyArray,k+1,n); } return Root; } Построение оптимальных деревьев имеет смысл для статических деревьев, то есть для таких, для которых операции вставки и удаления отсутствуют. Восстановление оптимальности после вставки или удаления требует полного перестроения дерева. Сбалансированные деревья представляют собой компромисс между оптимальными и случайными деревьями. Авторы идеи сбалансированного дерева - Адельсон-Вельский и Ландис (1962 г.), поэтому такие деревья называют также AVL-деревьями. AVL-деревья используют дополнительно 2 бита на узел и позволяют за время ~ log2N, выполнять операции вставки, поиска и удаления. Определим высоту дерева как максимальную длину пути от корня до листа. Будем называть дерево сбалансированным, если в каждом узле высота правого и левого поддеревьев различаются не более чем на ±1. На рис. 43
Рис.43 Пример сбалансированного дерева изображен пример сбалансированного дерева. Оценим максимальную высоту сбалансированного дерева. Обозначим минимальное число узлов в AVL-дереве высоты h через N(h). В таком дереве с минимальным числом узлов одна из ветвей, исходящих из корня, должна содержать N(h-1) узлов, а другая - N(h-2) узлов. Таким образом, (6) Очевидно, что N(0)=1, N(1)=2. Далее по формуле (6) находим, что N(2)=4. Для h=3 и h=4 можно непосредственно проверить, а затем по индукции доказать, что при h³3 справедливо неравенство (7) где -положительный корень уравнения , которое является характеристическим для разностного уравнения (6). Действительно, допустим, что неравенство (7) выполняется для всех k<N. Тогда, подставив в правую часть равенства (6) нижние границы N(h-1), N(h-2) в соответствии с неравенством (7), получим: (8) Подставим в левую часть неравенства (7) нижнюю грань для N(h) из неравенства (8). В результате будет получено более сильное неравенство: (9) Очевидно, что если (9) справедливо, то тем более справедливо (7). Преобразуем неравенство (9) к виду:
Трехчлен в скобках тождественно равен нулю, так как a - его корень. Остается –1<0. Таким образом, неравенство (7) доказано. Следовательно, если сбалансированное дерево содержит ветвь длины h>3, то число его вершин n удовлетворяет неравенству , откуда (10) Величина h+1 – это число сравнений ключей при поиске записи, расположенной в конце пути длиной h, исходящем из корня. Окончательный вывод: число сравнений ключей при поиске в сбалансированном дереве из n узлов не превышает .
Дата добавления: 2014-12-08; Просмотров: 501; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |