3

enter image description here

The tree has invariance that the parent node must always be smaller than its child, like the image shown above. Now suppose some of the node's key has changed and breaks the invariance and I want to maintain the invariance. I think it's basically compare-swap every child of a parent node but I can't figure out how to write the recursion to traverse the tree. It seems different from binary tree I learnt before...

Btw each node has no index but only three pointers: parent, leftChild, rightSibling. If the node is root, its parent point to NULL; if the node is the right most node, its rightSibling points to NULL... Can anyone shed some light on this? Thx in advance!

4

1 回答 1

1

首先，将这种多路树表示为二叉树称为左子/右兄弟表示，并且与正常的多路树表示有一些折衷。这个较旧的问题/答案可能会提供一些有关如何递归遍历这些树的背景。

至于您的问题：节点的值更改有两种可能的结果：

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

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

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

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 循环看起来有点奇怪。我们首先下降到左边的孩子，然后继续向右，直到我们用完节点。在伪代码中：

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);
    }
}

这里的所有都是它的！从概念上讲，递归并不是那么难，唯一奇怪的部分是我们如何访问孩子。

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

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);
    }
}

我们应该都准备好了！

希望这可以帮助！

于 2013-02-24T18:45:14.053 回答