Относительно Splay Trees

Question

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

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

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

Спасибо!

Answer 1

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

Пример.

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

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

Answer 2

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

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

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

Есть только 3 случая для поворота в деревах. Перечислен здесьВы можете увидеть разницу во время выполнения в поиске с распылением и без него.