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