algorithm - 在节点的键更改后使多路树成为堆？

Question

树具有不变性，即父节点必须始终小于其子节点，如上图所示。现在假设一些节点的键已经改变并打破了不变性，我想保持不变性。我认为它基本上是比较交换父节点的每个子节点，但我不知道如何编写递归来遍历树。好像和之前学的二叉树不一样...

顺便说一句，每个节点没有索引，只有三个指针:parent、leftChild、rightSibling。如果节点是root，它的父节点指向NULL；如果节点是最右边的节点，它的 rightSibling 指向 NULL... 任何人都可以阐明这一点吗？ 提前致谢!

Answer 1

对于初学者来说，这种多路树作为二叉树的表示称为 left-child/right-sibling representation并且与正常的多路树表示有一些权衡。这个较旧的问题/答案可能会提供有关如何递归遍历这些树的一些背景知识。

关于你的问题:节点的值变化有两种可能的结果:

• 如果节点的值下降，那么您可能需要向上交换它，直到它的值不再小于其父节点。
• 如果节点的值上升，那么您可能需要将它与其最小的子节点交换，直到该值不再大于它的任何子节点。

编写此递归的一种方法是分两次处理树，每次检查这两种情况中的一种。没有根本原因不能将这些通行证组合在一起，但为了解释简单起见，我将分别对待每个通行证。

在第一种情况下，我们可能需要将一个节点与其父节点交换，因为它的值已经减少。在那种情况下，我们需要模拟某种树遍历，首先处理所有子节点，然后处理节点本身。这样，如果一个值需要跨多个层交换到根，我们可以递归地将它带到尽可能高的层而不穿过根，然后再提升一个层。如果我们有一个标准的多路树，递归将如下所示:

void FixTreeUpward(TreeNode curr) {
    /* If the current node is null, we're done. */
    if (curr == null) return;

    /* Process each child. */
    for (TreeNode child that is a child of curr) {
        FixTreeUpwardRec(child);
    }

    /* If we need to swap values with our parent, do so here. */
    if (curr.parent != null && curr.value < curr.parent.value) {
        swap(curr.value, parent.value);
    }
}

由于我们使用的是多路树的左子右兄弟表示，所以中间的 for 循环看起来有点奇怪。我们首先下降到左边的 child ，然后继续向右直到我们用完节点。在伪代码中:

void FixTreeUpward(TreeNode curr) {
    /* If the current node is null, we're done. */
    if (curr == null) return;

    /* Process each child. */
    for (TreeNode child = curr.left; child != null; child = child.right) {
        FixTreeUpwardRec(child);
    }

    /* If we need to swap values with our parent, do so here. */
    if (curr.parent != null && curr.value < curr.parent.value) {
        swap(curr.value, parent.value);
    }
}

这就是它的全部!从概念上讲，递归并没有那么难，唯一奇怪的部分是我们如何访问 child 。

让我们考虑一下算法的第二部分，如果有必要，我们必须在其中冒泡。为此，我们将执行以下操作:对于每个节点，查看其所有子节点并找到具有最小值的子节点。如果该值小于根节点的值，则将树的根与该子节点交换，然后重复。在伪代码中:

void FixTreeDownward(TreeNode root) {
    /* If the root is null, we have nothing to do. */
    if (root == null) return;

    /* Find the smallest child. */
    TreeNode smallChild = (root's first child, or null if none exists);

    for (TreeNode child in the children of the root) {
        if (child.value < smallChild.value) {
            smallChild = child.value;
        }
    }

    /* If we have a smallest child and it's smaller than our value,
     * swap values and recursively repeat this.
     */
    if (smallChild != null && smallChild.value < root.value) {
        swap(smallChild.value, root.value);
        FixTreeDownward(smallChild);
    }
}

所以现在唯一的问题是遍历所有子项，幸运的是，这并不难!和以前一样，我们下降到左子树，然后继续向右直到我们用完节点。这显示在这里:

void FixTreeDownward(TreeNode root) {
    /* If the root is null, we have nothing to do. */
    if (root == null) return;

    /* Find the smallest child. */
    TreeNode smallChild = root.left;

    for (TreeNode child = root.left; child != null; child = child.right) {
        if (child.value < smallChild.value) {
            smallChild = child;
        }
    }

    /* If we have a smallest child and it's smaller than our value,
     * swap values and recursively repeat this.
     */
    if (smallChild != null && smallChild.value < root.value) {
        swap(smallChild.value, root.value);
        FixTreeDownward(smallChild);
    }
}

我们应该准备就绪!

希望这对您有所帮助!