我需要帮助理解张开树中之字形和之字形旋转的具体示例。我在一本书、维基百科以及其他一些在线资源中阅读过它们,虽然当它们应用于简单的树(即节点很少的树)时我可以理解它们,但当我看到示例时我会迷路其中应用于更大的树(即具有更多节点的树)。
特别是,我不明白这两个例子中的至少一个:
示例 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轮换。
在该示例中,展开操作涉及 zig-zig。如您所见,只有 1 次旋转。然后是第二次展开,因为被访问的节点仍然不在根位置。
我在这里所期望的是:
- 提供的 zig-zig 和 zig-zag 的描述都是正确的,因此在第二个示例中会有 2 次旋转:一次围绕节点的祖父母,然后围绕其父节点。
- 或者,提供的描述是错误的,因此第二个示例是正确的,但第一个示例不是因为我们在节点处于锯齿形位置时使用其父节点而不是其祖父节点旋转节点。
你能告诉我这两个例子中是否有任何一个是错误的,哪个是错误的?如果他们都没有错,我错在哪里?
谢谢您的帮助。
PS:很明显我是一名学生,我只想告诉你,我不是在作业的背景下问这个问题,因此我没有作弊。然而,我下周一有一个考试,我希望在我参加考试之前澄清任何误解。