Блог

Как это, например,

В этом сообщении говорится, что LL Rotation это single left Rotation . https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor /

Однако, из вики tree rotation , https://en.wikipedia.org/wiki/Tree_rotation, я думаю, что это single right Rotation ?

Более того, я также вижу, https://www.codingeek.com/data-structure/avl-tree-introduction-to-rotations-and-its-implementation/ . Здесь говорится, что это RR Rotation и это single right Rotation есть?

Меня смущают разные мнения. Кто-нибудь может сказать мне правду о приведенной выше картинке?

• Является ли это полным вращением?
• Это одиночное вращение влево или одиночное вращение вправо?

Прежде всего, все веб-сайты, на которые даны ссылки, согласны с тем, что изображенный пример представляет собой одиночный поворот вправо.

Вы пишете:

Как это, например, полный поворот дерева

В этом сообщении говорится, что полный поворот — это один левый поворот https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor /

Действительно, хотя нет никакой двусмысленности в отношении того, что означают термины «вращение влево» и «вращение вправо», кажется, что существуют две противоречивые интерпретации того, что означают «вращение LL» и «вращение RR».

Однако, из wiki о вращении дерева, https://en.wikipedia.org/wiki/Tree_rotation, я думаю, что это одиночное вращение вправо?

Ну, в статье Википедии не используется термин «поворот LL». Но это также согласуется с тем, что изображенный пример представляет собой поворот вправо. Пока нет двусмысленности в терминах «поворот влево» и «поворот вправо».

Кто-нибудь может сказать мне правду о приведенной выше картинке?

Как объясняют все эти сайты: это одиночный поворот вправо.

LL, RR

Двусмысленность возникает при использовании терминов «вращение LL» и «вращение RR»:

Сокращения «LL» и «RR» имеют больше смысла при описании дисбаланса перед выполнением любого вращения. Статья Википедии классифицирует несбалансированные деревья по 4 категориям (4 столбца):

В каждом столбце вверху вы видите исходное состояние, а затем под ним результат поворота (ов), который (которые) следует выполнить, чтобы привести дерево в равновесие.

Итак, для дерева в левом левом случае нам нужен поворот вправо. И для дерева в правом Правом случае нам нужен поворот влево.

Следующие примечания к курсу ICS в Калифорнийском университете в Ирвине объясняют, откуда берутся буквы LL, RR, LR, RL:

Поворот выбирается с учетом двух ссылок вдоль пути ниже узла, где находится дисбаланс, возвращаясь вниз к тому месту, где вы вставили узел. (Если вам интересно, откуда взялись имена LL, RR, LR и RL, вот ответ на эту загадку.)

• Если обе ссылки расположены слева, выполните полный поворот с корнем там, где есть дисбаланс.
• Если обе ссылки расположены справа, выполните поворот RR, основанный на том месте, где находится дисбаланс.
• Если первое звено расположено слева, а второе — справа, выполните поворот LR с корнем там, где находится дисбаланс.
• Если первое звено расположено справа, а второе — слева, выполните поворот RL с корнем там, где находится дисбаланс.

Но я чувствую, что разговор о вращении LL может вызвать путаницу, поскольку здесь мы видим, что двойной поворот LL описывает дисбаланс исходного состояния и не описывает действие. Было бы более разумно говорить о состоянии LL (или дисбалансе), а затем называть разрешающее действие «правым вращением». Имея это в виду, я думаю, что статья в Википедии занимает хорошую позицию, поскольку в ней избегается термин «поворот LL».

Это недоразумение не возникает при вращениях LR и RL. Вы можете сказать, что начальным состоянием является LR (дисбаланс был вызван предоставлением левому листу правого дочернего элемента), и вы также можете сказать, что сначала требуется поворот влево, а затем поворот вправо. В обоих случаях аббревиатура LR имеет смысл. Так что никакой двусмысленности нет.

Заключение

Термины поворот влево и поворот вправо понятны.

Существуют разные традиции, для какого из этих вращений называть вращение LL или RR. На мой взгляд, нам следует избегать говорить о «вращении LL» или «вращении RR», поскольку эти буквы описывают не сам акт вращения, а начальное состояние. Лучше говорить о «случае LL» или «дисбалансе LL».

Используя эти термины, мы можем сказать:

• Дерево с дисбалансом LL нуждается в повороте вправо
• Дерево с дисбалансом RR нуждается в повороте влево