53495

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота

Доклад

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

Следовать по пути поиска, пока не окажется, что узла нет в дереве. Включить новый узел и определить показатель сбалансированности. Пройти обратно по пути поиска, определяя сбалансированность.

Русский

2014-04-01

129.41 KB

1 чел.

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота.

Алгоритм добавления узла в AVL дерево

3 этапа:

  1. Следовать по пути поиска, пока не окажется, что узла нет в дереве.
  2. Включить новый узел и определить показатель сбалансированности.
  3. Пройти обратно по пути поиска, определяя сбалансированность.

Включение узла:

  1. Выполнить вставку в бинарное дерево.
  2. Если вставка в левое поддерево, то имеют место 3 случая:
  3. Если правое поддерево было длиннее, то стало сбалансированным.
  4. Если был баланс, то левое поддерево выросло, и нужно проверить балансировку выше.
  5. Левое поддерево было длинее, имеем расбалансировку.
  6. Если в правое:
  7. Если левое поддерево было длиннее, то стало сбалансированным.
  8. Если был баланс, то правое поддерево выросло, и нужно проверить балансировку выше.
  9. Правое поддерево было длинее, имеем расбалансировку.

Случай левого поворота


 

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

80242. Прийняття управлінських рішень. Методи творчого пошуку альтернатив 6.79 MB
  Прийняття управлінських рішень. Основи теорії прийняття рішень. Процес прийняття рішень. Основи теорії прийняття рішень У науковій літературі зустрічається як розширене так і вузьке розуміння процесу прийняття рішень в управлінні.
80243. Методи обґрунтування управлінських рішень 5.47 MB
  Методи обґрунтування управлінських рішень. Відповідно до цього способу всі методи обґрунтування управлінських рішень поділяються на кількісні та якісні. Кількісні методи або методи дослідження операцій застосовують коли фактори що впливають на вибір рішення можна кількісно визначити та оцінити. Якісні методи використовують тоді коли фактори що визначають прийняття рішення не можна кількісно охарактеризувати або вони взагалі не піддаються кількісному вимірюванню.
80244. Рынок и его инфраструктура 94.5 KB
  Рынок и его инфраструктура План 1. Сущность функции и структура рынка Объединенное понятие рынок как место массовой куплипродажи товаров лишь частичного отражает содержание которое вкладывается в понятие рынок экономической науки и хозяйственной практикой. Рынок в широком смысле объединяет в себе несколько понятий. Вовторых рынок есть вся совокупность процессов торговли актов куплипродажи который характеризуется такими признаками как вид продаваемых товаров объем продаж способ торговли уровень цен.
80245. Основы саморегулирования рыночной экономики 134 KB
  Объективные факторы: экономические: базовый уровень развития производства; объём реальных потребностей и уровень их удовлетворения; средний уровень денежных доходов населения; рыночные цены; уровень цен товаровзаменителейи взаимодополняемых товаров; принципы распределения доходов; условия предоставления кредитов качество товара. Он отражает причинноследственную связь между изменением цены и изменением величины спроса. Рост цены при прочих неизменных условиях вызывает снижение спроса что способствует разрешению противоречия...
80246. Экономическая роль государства в рыночной экономике 74.5 KB
  Необходимость и сущность государственного регулирования рыночной экономики. Формы государственного регулирования рыночной экономики. Необходимость и сущность государственного регулирования рыночной экономики. Государственное регулирование экономики сложилось не сразу.
80247. Доходы и их распределение. Заработная плата 81.5 KB
  Марксистская теория исходит из того что новая стоимость товара созданная трудом наемных работников проходя через сферу обращения в ходе конкурентной борьбы распределяется и перераспределяется принимая различные формы: заработной платы наемных работников; прибыль капиталистов; процентов ссудных капиталистов банкиров; ренты владельцев земли и других природных факторов объектов добывающей промышленности и строительства. Объективное распределение доходов зависит от того что вновь созданная стоимость слагается из необходимого продукта...
80248. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ЦЕН В ЗАВИСИМОСТИ ОТ МОДЕЛИ РЫНКА 55.5 KB
  Рынок совершенной конкуренции: характерные черты и механизм ценообразования. Особенности рынка несовершенной конкуренции. Механизм рыночных цен позволяет стимулировать рациональное использование ограниченных и редких ресурсов добиваться эффективного хозяйствования решать триаду экономических проблем: что как и для кого производить На решение этих проблем направлен и механизм конкуренции. Монополия вырастая из конкуренции на определенном этапе своего развития уничтожает конкуренцию но рыночная конкуренция как известно неотъемлемый...
80249. Особенности предпринимательства в агропромышленном комплексе 65.5 KB
  Аграрные отношения это составная часть экономических отношений которые складываются в сельском хозяйстве в связи с владением и использованием земли как главного средства производства в сельскохозяйственной отросли. Это обусловлено использованием в производстве земли как специфического искусственно невоспроизводимого средства производства различающегося по плодородию места расположению. Эти свойства наоборот даже могут улучшаться что приведет к росту ценности земли. Тесная зависимость земли от природноклиматических условий сезонный...
80250. ДЕНЕЖНОЕ ОБРАЩЕНИЕ. ФИНАНСОВАЯ СИСТЕМА И ФИСКАЛЬНАЯ ПОЛИТИКА 78 KB
  Особенности рынка денег. Особенности рынка денег. Сущность денег состоит в том что они: обладают всеобщей обмениваемостью; представляют собой кристаллизацию меновой стоимости; являются воплощением всеобщего рабочего времени. С развитием общества изменялись функции и виды денег.