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. Правое поддерево было длинее, имеем расбалансировку.

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


 

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

2842. Функции как совокупность объявлений и операторов 79 KB
  Функции Функция – это совокупность объявлений и операторов, предназначенных для выполнения отдельной задачи и заключённых в специальный блок. Необходимость в использовании функций возникает при решении сложных задач, когда нужно выполнять набор...
2843. Время жизни и область видимости в программировании 54 KB
  Время жизни и область видимости В языке C блоком считается последовательность объявлений, определений и операторов, заключенная в фигурные скобки. Объект языка C может быть объявлен на внешнем уровне (вне любого блока), на внутреннем уровне (внутри ...
2844. Препроцессор языка C 75.5 KB
  Препроцессор языка C Препроцессор языка C – это программа, выполняющая обработку исходного кода для передачи его компилятору, в процессе которой происходит подстановка директив и выполнение операций препроцессора. Все директивы препроцессора на...
2845. Интерпретация составных описателей 36 KB
  Интерпретация составных описателей При объявлении переменных, массивов, указателей или функций кроме простых идентификаторов могут использоваться составные описатели. Составной описатель – это идентификатор, дополненный более чем одним признако...
2846. Типы данных, определяемые пользователем (агрегативные типы данных) 51 KB
  Типы данных, определяемые пользователем (агрегативные типы данных) Язык C позволяет программисту создавать следующие типы данных: переименование типов перечислимый тип структура битовые поля объединение Переименование типов. Язык C позволяет дать но...
2847. Прерывания в ОС MS-DOS 36 KB
  Прерывания в ОС MS-DOS Драйвер – это программа, являющаяся посредником между устройством и программой пользователя и предоставляющая набор функций для работы с устройством. В MS-DOS существуют драйверы символьных устройств (за одну операцию обм...
2848. Процесс взаимодействия системы с клавиатурой в ОС MS-DOS 39 KB
  Процесс взаимодействия системы с клавиатурой в ОС MS-DOS Клавиатура – это устройство компьютера, предназначенное для ввода текстовой информации. Технически клавиатура представляет собой матрицу ключей (кнопок), замыкаемых пользователем при нажа...
2849. Работа с мышью 89 KB
  Работа с мышью. Мышь – это устройство компьютера для ввода информации, относящееся к классу манипуляторов. Курсор мыши – это указатель мыши, перемещающийся по экрану в зависимости от перемещения мыши по столу. Так как курсор мыши представля...
2850. Видеосистема компьютера 54.5 KB
  Видеосистема компьютера Видеосистема компьютера включает в себя ряд аппаратных и программных средств, позволяющих получать на экране терминала изображения. К аппаратным средствам относятся монитор и видеоадаптер. К программным средствам относятся ср...