Относительно кустарников

Question

Я читаю о деревьях в структурах данных и алгоритмах. Автор - Марк Аллен Весис

Стратегия распространения похожа на идею вращения, за исключением того, что мы немного более избирательны в отношении выполнения вращения,Мы все еще будем вращаться снизу вверх вдоль пути доступа.Пусть x (не корневой) узел на пути доступа, по которому мы вращаемся.Если родительский элемент x является корнем дерева, мы просто поворачиваем x и корень.Это последний поворот на пути доступа.В противном случае у x есть и родитель (p), и дед (g), и есть два случая плюс симметрии, которые нужно рассмотреть.Первый случай - это зигзагообразный случай. Здесь x - правый дочерний элемент, а p - левый дочерний (или наоборот).Если это так, мы выполняем двойной поворот, точно так же, как двойной поворот AVL.В противном случае мы имеем зигзагообразный регистр: x и p являются либо левыми, либо правыми детьми.

В вышеприведенном тексте автор подразумевает следующее утверждение: «Есть два случая плюс симметрии»?даны два случая, но что такое симметры здесь?

Спасибо!

Answer 1

Я думаю, что это просто базовая осевая симметрия:

пример для случая зигзага, вот 2 симметричных дерева:

     g
    / \ 
    p  d
   /\
  c  x
    / \
   a   b

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b

Answer 2

Например, допустим, что кейс имеет вид «Когда рассматриваемый узел является правым дочерним элементом своего родителя, а родительский - левым дочерним элементом дедушки». В этом случае вы делаете левый поворот, а затем правый поворот.Таким образом, узел подходит к прародителю.

Симметричная часть этого случая - «Когда узел в вопросах является левым дочерним элементом своего родителя, а родительский является правым дочерним элементом прародителя».Если вы делаете правое вращение, а затем левое вращение.Таким образом, узел подходит к прародителю.

замените левый на правый, а правый на левый, вы получите симметричный регистр.

В Splay Tree есть только 3 случая для вращения.Перечислил это здесь Вы можете увидеть разницу во времени выполнения поиска с и без отображения.