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), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.


 

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

77087. Влияние поверхностно-активных веществ на микроорганизмы, феноменологию и механизм 135 KB
  Но несмотря на широкий спектр применения ПАВ оказывают негативное воздействие на окружающую среду. Попадая в водоёмы ПАВ активно участвуют в процессах перераспределения и трансформации других загрязняющих веществ таких как железо канцерогенные вещества пестициды нефтепродукты тяжёлые металлы и др. Большинство ПАВ и продукты их распада токсичны для различных групп гидробионтов: микроорганизмов 0840 мг дм3 водорослей 0560 мг дм3 беспозвоночных 00109 мг дм3 даже в малых концентрациях особенно при хроническом воздействии.
77088. Водогрейный котел КВГМ 375 KB
  Наилучшим решением в этой ситуации является разработка полномасштабных интегрированных автоматизированных систем управления технологическим процессом АСУ ТП взамен устаревших систем а также внедрение современного технологического оборудования позволяющего максимально использовать возможности систем управления и тем самым добиться качественно нового уровня технологии. Современные автоматизированные системы управления котельной и котельными агрегатами по отдельности включают систему управления водогрейным отделением содержащую...