Лекция 17. AVL-деревья (1107992), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Пример построения АВЛ-дерева.Пусть на «вход» функции Search() последовательно поступают целые числа4,5,7,2,1,3,6. Изобразим процесс «роста» АВЛ-дерева (в скобках для части вершинуказан показатель сбалансированности) [1,с.256]:Это тщательно подобранный пример, показывающий ситуацию: как можно большеповоротов при минимальном числе включений. (рис. 6)7(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годРис.6.

Построение АВЛ-дерева17.5. Исключение узла из АВЛ-дерева17.5.1. Объявление функции:AvlTree Delete( ElementType X, AvlTree T ){}17.5.2. Исключение узла из АВЛ-дерева отличается от исключения узла из двоичного дерева(рассматривалось на прошлой лекции) необходимостью балансировки дерева послеисключения узла. Иными словами в конец функции, выполняющей исключение узланеобходимо добавить вызовы функций:SingleRotateWithRight(T), SingleRotateWithLeft(T),DoubleRotateWithRight(T) и DoubleRotateWithLeft(T)17.5.3.

При исключении узла, имеющего двух детей возможен случай, не возникающий привставлении узлов: дерево, подвешенное к узлу rr, имеет высоту h + 1 (при вставленииузлов такой случай возникнуть не может, так как в этом случае может увеличитьсявысота только одного поддерева). В этом случае необходим дополнительный поворототносительно узла r.17.6.

Оценки сложностиНа прошлой лекции были получены оценки высоты для самого «хорошего» АВЛ-дерева,содержащего m узлов – h = O(log2m) (полностью сбалансированное дерево) и самого«плохого» АВЛ-дерева, содержащего m узлов – h ≤ 1.44⋅ log 2 (m + 1) – 0.32 (дерево8(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годФибоначчи). Следовательно, для «среднего» АВЛ-дерева, содержащего m узлов оценкавысоты будет log 2 (m + 1) ≤ h ≤ 1.44⋅ log 2 (m + 1) – 0.32.mmlog 2 mlog 2 m1065,536161641,048,47620256816,778,616244,096129(с) Кафедра системного программирования ф-та ВМК МГУ, 2010.

Характеристики

Список файлов лекций