关于张开的树

Question

我正在阅读有关数据结构和算法中的散布树的信息

散发策略类似于旋转的想法，只是我们对旋转的执行方式更具选择性。我们仍将沿着访问路径向上旋转。令x为我们旋转的访问路径上的（非根）节点。如果x的父是树的根，我们只是旋转x和根。这是沿访问路径的最后旋转。否则，X既有父母（P）和祖父母（G），并且有两种案例以及对称性。第一种情况是Zig-Zag案例，这里X是一个正确的孩子，P是左儿童（反之亦然）。如果是这种情况，我们进行双旋转，就像AVL双旋转一样。否则，我们会有一个Zig-Zig案例：X和P是左子女或两个右子女。

在上文中，作者通过以下陈述“有两种情况加上对称性”是什么意思？给出了两种情况，但是这里有什么对称？

谢谢！

Answer 1

我认为这只是相当基本的轴向符号：

曲折案例的示例，以下是2种符号树：

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

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

Answer 2

例如，假设一个案例是“当问题中的节点是其父母的正确孩子时，父母是祖父母的左子女”，在这种情况下，您要进行左转，然后进行右转。因此，节点将出现在大父母身上。

这种情况的对称部分是“当问题中的节点是其父母的左子女时，父母是祖父母的右子孩子”，在这种情况下，您进行了正确的旋转，然后进行左转。因此，节点将出现在大父母身上。

用左右左右替换为左右，您会得到对称情况。

在张开树中只有3例旋转。列出了它 这里您可以在搜索中看到和不散布的情况下的运行时差异。