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

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


 

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

44762. Оценка уровня качества телевизора «SAMSUNG» 260 KB
  Телевизор - электронное устройство для приёма и отображения изображения и звука, передаваемых по беспроводным каналам или по кабелю (в том числе телевизионных программ или сигналов от устройств воспроизведения видеосигнала - например, видеомагнитофонов).
44763. Создание проекта СЭУ толкача буксира 2.38 MB
  Целью дипломного проекта является создание проекта СЭУ для вновь проектируемого судна. Учитывая задание на проектировку (тип судна, грузоподъемность, район плавания, требования к маневренности, живучести), а также используя опыт судостроения предыдущих лет...
44764. Предприятие как субъект и объект предпринимательской деятельности 57.38 KB
  Функционирование предприятий в условиях рынка предполагает поиск и разработку каждым из них собственного пути развития. Чтобы не только удержаться, но и развиваться в рынке, предприятие должно улучшать состояние своей экономики
44765. Банковский маркетинг, Краткий конспект лекций 99.59 KB
  Основные понятия банковского маркетинга. Роль маркетинга в банковской деятельности. Концепция банковской технологии маркетинга. Банковская маркетинговая стратегия. Постановка маркетинговой работы в коммерческом банке. Банковская конкуренция. Маркетинг депозитарной деятельности банка. Маркетинг кредитного банковского рынка...