1

我需要帮助理解张开树中之字形和之字形旋转的具体示例。我在一本书、维基百科以及其他一些在线资源中阅读过它们,虽然当它们应用于简单的树(即节点很少的树)时我可以理解它们,但当我看到示例时我会迷路其中应用于更大的树(即具有更多节点的树)。

特别是,我不明白这两个例子中的至少一个:

示例 1

展开示例 1 (这不是完整的例子,但这是我不明白的部分)

我们可以在(1)中看到即将展开的节点是左孩子的右孩子,因此我们必须做一个之字形。因此,我可以理解 (1) 和 (2) 之间发生了什么,其中展开的节点现在已经取代了它的父节点。据我了解,整个锯齿形操作都发生在那里。所以第一次展开结束了,我们仍然需要展开节点,直到它位于树的根部。

我不明白(2)和(3)之间会发生什么。在 (2) 中,展开的节点是左子节点的左子节点,因此我期望进行 zig-zig 操作,其中展开的节点围绕其祖父节点旋转,即 (20, Z)。相反,幻灯片显示与其父级 (10, A) 的旋转。为什么?我所期望的是,我们的展开节点 (8, N) 做了一个 zig-zig 并因此取代了 (20, N) 的位置,它是它的祖父母,也是根。为什么家长反而参与其中?

在我找到此示例的资源(我的讲师的幻灯片)中,锯齿形旋转被描述为“与其父级一起旋转节点,然后与其祖父级一起旋转节点”。这就是这里发生的事情吗?这就是为什么在(2)和(3)之间,(8,N)随(10,A)而不是(20,Z)旋转的原因吗?

我对这个描述很困惑,因为 zig-zig 旋转被描述为“旋转节点与其祖父节点,然后旋转节点与其父节点”。但是,每次我看到一个 zig-zig 旋转的例子时,总是只有一个与节点的祖父节点的旋转,仅此而已。我从来没有见过2轮换。

然后是另一个例子: 展开示例 2

在该示例中,展开操作涉及 zig-zig。如您所见,只有 1 次旋转。然后是第二次展开,因为被访问的节点仍然不在根位置。

我在这里所期望的是:

  • 提供的 zig-zig 和 zig-zag 的描述都是正确的,因此在第二个示例中会有 2 次旋转:一次围绕节点的祖父母,然后围绕其父节点。
  • 或者,提供的描述是错误的,因此第二个示例是正确的,但第一个示例不是因为我们在节点处于锯齿形位置时使用其父节点而不是其祖父节点旋转节点。

你能告诉我这两个例子中是否有任何一个是错误的,哪个是错误的?如果他们都没有错,我错在哪里?

谢谢您的帮助。

PS:很明显我是一名学生,我只想告诉你,我不是在作业的背景下问这个问题,因此我没有作弊。然而,我下周一有一个考试,我希望在我参加考试之前澄清任何误解。

4

1 回答 1

0

节点x的展开是一系列展开步骤,直到x成为树的根。这些步骤是之字形、之字形和之字形。

对于节点x,它的父节点pp的父节点g,节点x上的之字形操作是针对p不是根节点且xp的右子节点且pg的左子节点的情况定义的:先向左旋转x,然后向右旋转x。您的第一个示例正好显示了这种情况:zig 向左旋转x = (8, X) 及其父p = (7, T),然后 zag 向右旋转 (8, X) 和g = (10, A)。因此,此示例在x上显示锯齿形,但是展开本身并没有完成,因为x还不是根(这意味着需要更多的展开步骤)。

zig-zig是针对xp都是其各自父母的右孩子的情况定义的:首先向左旋转p,然后向左旋转x。第二个示例的第二张图片显示了x = (40, X), p = (37, P), g = (35, R) 上 zig-zig 的结果:首先p向左旋转,然后x向左旋转. 第二个示例的第三张图片显示了对x的附加 zig 操作(向左旋转x,因为其父p是根)移动到根并完成x的张开。

(所有 zig、zig-zig 和 zig-zag 操作都有其对称对应物)。

于 2016-12-18T10:02:04.420 回答