Существует множество примеров ротации AVL в книгах и в Интернете, но то, что я нашел, казалось произвольным, и ни в одном месте не было простых примеров для вставки и удаления всех 4 случаев.
Это самый простой тестовый пример, который я мог придумать для 4 видов вращений. Чтобы упростить описание, я использовал символы ascii в качестве ключа, поэтому тестовый пример может быть выражен в виде строки. Например, строка «abc» будет вставлять «a», вставлять «b», а затем вставлять «c».
Полные тестовые наборы создают несколько довольно сложных деревьев, поэтому я создал два набора тестов. Первый вызывает повороты, но имеет пустые поддеревья для вращающихся узлов, что позволяет легко увидеть, что на самом деле произошло. Во втором наборе есть непустые поддеревья для полного тестирования кода поворота.
Кажется, есть две разные номенклатуры для вращений - то, что я узнал как вращение 2L, некоторые книги называют вращением rl, а вращение 2R называется вращением lr. Текст ниже использует 2R / 2L.
Это простые тестовые примеры для вставки
«abc», для вставки «c» потребуется 1 л вращения
a b
\ / \
b == 1L ==> a c
\
c
«cba», для вставки «a» потребуется 1R вращения
c b
/ / \
b == 1R ==> a c
/
a
"acb" на вставке "b" потребует вращения 2L
a b
\ / \
c == 2L ==> a c
/
b
«cab» на вставке «b» потребует 2R вращения
c b
/ / \
a == 2R ==> a c
\
b
Для удаления
«bcad», при удалении «а» потребуется 1 л вращения
b c
x \ / \
a c == 1L ==> b d
\
d
«cbda», при удалении «d» потребуется 1R вращения
c b
/ x / \
b d == 1R ==> a c
/
a
«bdac» при удалении «a» потребует вращения 2L
b c
x \ / \
a d == 2L ==> b d
/
c
«cadb» при удалении «d» потребует 2R вращения
c b
/ x / \
a d == 2R ==> a c
\
b
Более сложные тестовые случаи имеют поддеревья, большинство из которых представляют собой один узел. Чтобы сделать этот пост короче, вставьте и удалите контрольные примеры. Пример удаления становится примером вставки, пропуская вставку символа удаления. Например, при использовании простого случая удаления 2R выше «cadb» становится регистром ввода «cab», пропуская вставку «d». Одним из следствий этого является случай двойного поворота, приведенный ниже, который требует вставки дополнительного узла, чтобы сохранить сбалансированное дерево после вставки удаляемого узла. Это приводит к тому, что случай вставки не является минимальным.
«cbedfag» при удалении «a» или пропуске «a», а для вставки «g» потребуется 1 л вращения при c
c e
/ \ / \
b e == 1R ==> c f
x / \ / \ \
a d f b d g
\
g
«ecfbdga» при удалении «g» или пропуске «g», а для вставки «a» потребуется 1R вращения при e
- e - c
/ \ / \
c f == 1R ==> b e
/ \ x / / \
b d g a d f
/
a
«ecjadhkgilbf» при удалении «b» или пропуске «b», а при вставке «f» потребуется поворот 2L в точке j, а затем в e. Футляр для вставки может при желании пропустить вставку «d».
- e - —- h —-
/ \ / \
c j - e- j
/ \ / \ == 2L ==> / \ / \
a d h k c g i k
x / \ \ / \ / \
b g i l a d f l
/
f
«hckbeiladfjg» для удаления «j» или пропуска «j», а для вставки «g» потребуется поворот 2R в точке c, а затем в b. Футляр для вставки может опционально пропускать вставку «l»
- h - - e -
/ \ / \
c k c - h -
/ \ / \ == 2R ==> / \ / \
b e i l b d f k
/ / \ x / \ / \
a d f j a g i l
\
g
Используйте методы 1 и 2 из вопроса, чтобы проверить, что дерево перебалансировано по мере необходимости (т. Е. Убедиться, что дерево все еще в порядке и сбалансировано). Если вы хотите быть действительно уверенным, преобразуйте визуальные тестовые примеры, чтобы включить список значений глубины и баланса конечного дерева для проверки во время обхода по порядку.