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


 

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

20447. Денежно-кредитная политика 87 KB
  Понятие и цели ДКП. Спрос на деньги и предложение денег. Создание банковской системы и новых денег. Банковский и денежный мультипликаторы. Инструменты ДКП. Политика дешевых и дорогих денег. Эффективность ДКП. Особенности ДКП в РБ.
20448. PHP 288.5 KB
  PHP: Hypertext Preprocessor PHP: препроцессор гипертекста англ. Область применения В области программирования для Сети PHP один из популярных скриптовых языков наряду с JSP Perl и языками используемыми в ASP.NET благодаря своей простоте скорости выполнения богатой функциональности кроссплатформенности и распространению исходных кодов на основе лицензии PHP.
20449. Диаграмма последовательности (sequence diagram) 112.5 KB
  Сообщения изображаются в виде горизонтальных стрелок с именем сообщения а их порядок определяется временем возникновения. То есть сообщения расположенные на диаграмме последовательности выше инициируются раньше тех которые расположены ниже. Сообщения В UML каждое взаимодействие описывается совокупностью сообщений которыми участвующие в нем объекты обмениваются между собой. Прием сообщения инициирует выполнение определенных действий направленных на решение отдельной задачи тем объектом которому это сообщение отправлено.
20450. HTTP 261 KB
  Основой HTTP является технология клиентсервер то есть предполагается существование потребителей клиентов которые инициируют соединение и посылают запрос и поставщиков серверов которые ожидают соединения для получения запроса производят необходимые действия и возвращают обратно сообщение с результатом. HTTP в настоящее время повсеместно используется во Всемирной паутине для получения информации с вебсайтов. В 2006 году в Северной Америке доля HTTPтрафика превысила долю P2Pсетей и составила 46 из которых почти половина это...
20451. Диаграмма кооперации (collaboration diagram) 122.5 KB
  Прежде всего на диаграмме кооперации в виде прямоугольников изображаются участвующие во взаимодействии объекты содержащие имя объекта его класс и возможно значения атрибутов. В отличие от диаграммы последовательности на диаграмме кооперации изображаются только отношения между объектами играющими определенные роли во взаимодействии. Кооперация Понятие кооперации collaboration является одним из фундаментальных понятий в языке UML.
20452. MySQL 122 KB
  MySQL является собственностью компании Oracle Corporation получившей её вместе с поглощённой Sun Microsystems осуществляющей разработку и поддержку приложения. MySQL является решением для малых и средних приложений. Обычно MySQL используется в качестве сервера к которому обращаются локальные или удалённые клиенты однако в дистрибутив входит библиотека внутреннего сервера позволяющая включать MySQL в автономные программы.
20453. Диаграмма деятельности (activity diagram) 136 KB
  Для моделирования процесса выполнения операций в языке UML используются диаграммы деятельности. Каждое состояние на диаграмме деятельности соответствует выполнению некоторой элементарной операции а переход в следующее состояние выполняется только при завершении этой операции. Таким образом диаграммы деятельности можно считать частным случаем диаграмм состояний.
20454. Разработка и эксплуатация информационных систем 273.62 KB
  Объект сущность в адресном пространстве вычислительной системы появляющаяся при создании экземпляра класса например после запуска результатов компиляции и линковки исходного кода на выполнение. Конечным продуктом этапа проектирования являются: схема базы данных на основании erмодели разработанной на этапе анализа; набор спецификаций модулей системы они строятся на базе моделей функций. На основании системного проекта осуществляется: составление перечня автоматизированных рабочих мест предприятия и способов взаимодействия между...