0

我正在阅读 Mark Allen Wesis 的数据结构和算法中的伸展树

张开策略类似于轮换的想法，只是我们对如何执行轮换更有选择性。我们仍将沿访问路径自下而上旋转。让 x 是我们正在旋转的访问路径上的（非根）节点。如果 x 的父节点是树的根，我们只需旋转 x 和根。这是沿访问路径的最后一次旋转。否则，x 既有父母（p）又有祖父母（g），有两种情况，加上对称性，需要考虑。第一种情况是 zig-zag 情况，这里 x 是右孩子，p 是左孩子（反之亦然）。如果是这种情况，我们执行双重旋转，就像 AVL 双重旋转一样。否则，我们有一个 zig-zig 情况：x 和 p 要么都是左孩子，要么都是右孩子。

在上面的文字中，作者所说的“有两种情况加对称”是什么意思？给出了两种情况，但这里的对称性是什么？

谢谢！

4

2 回答 2

2

我认为这只是非常基本的轴对称：

以之字形为例，这里有 2 棵对称树：

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

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b
于 2011-09-05T09:41:31.560 回答
0

例如，假设一个案例是“当有问题的节点是其父节点的右子节点并且父节点是祖父节点的左子节点时”在这种情况下，您先进行左旋转，然后再进行右旋转。所以节点会出现在祖父节点上。

这种情况的对称部分是“当有问题的节点是其父节点的左子节点并且父节点是祖父节点的右子节点时”在这种情况下，您先进行右旋转，然后再进行左旋转。所以节点会出现在祖父节点上。

将左替换为右，将右替换为左，您将得到对称的情况。

展开树中只有 3 个旋转案例。在这里列出 您可以看到在搜索时展开和不展开的运行时差异。

于 2012-01-18T03:53:32.450 回答