47287

Алгоритм пересчета балансов вершин выделенного пути и его особенности

Доклад

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

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Русский

2014-03-31

76.6 KB

0 чел.

Алгоритм пересчета балансов вершин выделенного пути и его особенности.

Основная идея

Если вставка или удаление элемента приводит к нарушению сбалансированности дерева то выполняется его балансировка 

 Коэффициент сбалансированности узла

это разность высот его левого и правого поддеревьев 

В АВЛ дереве коэффициент сбалансированности любого

узла принимает значения из множества {-1, 0, 1}

Балансировка дерева

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Типы поворотов:

Одиночный правый поворот

Одиночный левый поворот

Двойной лево -правый поворот

Двойной право- левый поворот


 

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

5271. Пассивные операции коммерческих банков 168 KB
  Пассивные операции коммерческих банков Ресурсы коммерческого банка: содержание и структура Собственный капитал банка. Международные стандарты капитала Заемный капитал коммерческого банка Депозиты коммерческого банка Деп...
5272. Регулирование банковской деятельности коммерческих банков 51.25 KB
  Регулирование банковской деятельности коммерческих банков Содержание банковского регулирования Сущность и типы денежно-кредитной политики Методы и инструменты денежно-кредитного регулирования экономики Характеристика ме...
5273. Коммерческие банки 52.58 KB
  Коммерческие банки Коммерческий банк: сущность, функции, классификация Типовая структура коммерческих банков Операции коммерческого банка. Введение Итак, банк — это предприятие, но предприятие особого рода. Если в деятельности...
5275. Банковская система России 438 KB
  Банковская система России Этапы реформирования банковской системы России Тенденции и проблемы развития банковской системы России Структура современной банковской системы России Вопрос 1. Этапы реформирования банковской системы Росс...
5276. Структура современной экономики США. Роль государства в экономике 78 KB
  Введение Экономика США — крупнейшая и одна из наиболее диверсифицированных национальных экономик мира, она также является локомотивом мировой экономики. Несмотря на общий для всех рыночных экономик механизм функционирования, основанный на домин...
5277. Банковская система 141 KB
  Банковская система Понятие и структура кредитной системы Банковская система: понятие, виды, структура, уровни, элементы. Характеристика элементов банковской системы Вопрос 1. Понятие и структура кредитной системы Выделяют два основ...
5278. Лесопиление. Окорка, пилорама с брусовкой 241.29 KB
  Введение. По объему выпускаемой продукции лесопромышленный комплекс в структуре промышленного производства России занимает пятое, по объемам экспорта - четвертое место. В нашей стране сосредоточены крупнейшие в мире лесосырьевые ресурсы...