53488

Процедура вставки вершин в AVL дерева и ее особенности

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-04-01

19.29 KB

0 чел.

Процедура вставки вершин в AVL дерева и ее особенности.

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Николасом Виртом в «Алгоритмы и структуры данных»):

  1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
  2. Включения новой вершины в дерево и определения результирующих показателей балансировки.
  3. «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к

  1. hl < hr: выравняется hl = hr. Ничего делать не нужно.
  2. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
  3. hl > hr: теперь hl — hr = 2, — требуется балансировка.

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.


 

А также другие работы, которые могут Вас заинтересовать

57486. Ukraine is our native country 73.5 KB
  The aims: to repeat the learnt vocabulary; to revise the information pupils have learnt about Ukraine; to recollect some facts about our country by doing different tasks: making up sentences and monologues, writing pass-letters;
57487. Кількість, густота, природний рух населення України 99 KB
  Після цього уроку учні зможуть: ознайомитись з кількістю населення України і її зміною в часі; давати визначення поняттям природний приріст міграція розкривати вплив природних історичних умов на розміщення населення на території України...
57489. Ukraine and Great Britain 1.86 MB
  Today we have unusual lesson. It’s a Presentation Lesson and its topic is “Differences and Similarities of Ukraine and Great Britain”. The aim of our lesson is to improve our knowledge, to learn more and broaden our outlook, to watch presentations, to play games.
57490. Welcome to Ukraine! 169.5 KB
  Today we have an unusual lesson. We are going to prepare for journey around Ukraine. We’ll travel next time. We’ll go by bus. But first of all we need tickets. You shouldn’t pay money for these tickets. You should answer some my questions to get a ticket. Let’s start.
57491. Послевоенное восстановление и развитие Украины (1945 - начало 1953 года). Голод 1946-1947 гг 65.5 KB
  Давайте мы пополним этот коллаж нарисовав свой символ голодоморов. Приложение №1 Документ №1 29 августа 1946 года былю официально объявлено что в связи с засухой в ряде областей СССР и сокращением государственных...
57492. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ РАБОТА ПО ФОРМИРОВАНИЮ НАВЫКОВ ПОСТРОЕНИЯ КОМПОЗИЦИИ В РИСУНКЕ У МЛАДШИХ ШКОЛЬНИКОВ СРЕДСТВАМИ ИЗОБРАЗИТЕЛЬНОГО ИСКУССТВА 166.82 KB
  Изобразительное искусство является художественным отражением действительности в зрительно воспринимаемых образах. Средствами цвета, пластики или рисунка художник создает на холсте, в глине или мраморе картины окружающей жизни, сильные и прекрасные образы человека.
57493. Точність і доречність мовлення. Складні випадки слововживання. Пароніми і омоніми. Вибір синонімів 375.5 KB
  Що таке лексикологія Що вона вивчає З яких груп складається лексика Які слова називають іншомовними Що таке термін термінологія Що таке професіоналізм Наведіть приклади. Випишіть словатерміни поясніть значення.
57494. Die Welt ist so schön! 42 KB
  Wir machen Mundgymnastik und wiederholen die Zungenbrecher: Hans hackt heute Holz hinter Hoffmanns Haus. Kleine Kinder können keine Kirschkerne knacken. Schneiders Schere schneiden scharf, scharf schneiden Schneiders Schere.