时间戳

首页 > 解决方案 > 识别二叉搜索树中的交换子树

algorithm - 识别二叉搜索树中的交换子树

问题描述

我正在研究这个挑战：

假设二叉搜索树中的两个子树已交换，并且 BST 属性已损坏。设计一种算法，在O(n)时间内识别两个交换的子树。

我的想法

当完成 BST 的中序遍历时，对元素进行排序。现在当两个子树交换时，中序遍历不会被排序。因此，如果您比较原始树和交换的树的中序遍历，就好像您在原始树中获取了排序数组的两个子集并交换了它们。

但是现在挑战来识别相应的子树，我不知道如何从中序遍历中推导出它。

标签： algorithmbinary-search-tree

解决方案

首先，如果树有重复的值，并且它们并不总是存储在其父级的同一侧（具有相同的值），那么并不总是可以检测到交换。想象一棵树在许多不同的地方具有相同的值：

         ______ 8 _____
        /              \
     _ 8_           ___ 8 __
    /    \         /        \
   2      8*      8*        14   
  / \    / \     /  \      /  \
 1   3  8   8   8    8   13    15

这是一个有效的 BST。如果我们要交换标有星号的两个子树，我们最终会得到一个有效的 BST，因此无法检测哪些子树被交换了。很可能是已交换的第一个 *-node 的子节点，或者已交换的第二个 *-node 的子节点。没有办法知道这一点。

因此，只有在交换的结果将涉及的两个子树插入到无效位置时，才有可能检测到交换。确保这一点的一种方法是规定重复值应始终存储在具有相同值的父节点的同一侧（例如右侧）。

算法

有序遍历是一个好主意，但随后验证访问节点是否以正确的顺序出现的想法不太有用。

相反，在遍历期间，跟踪当前访问的子树中允许的值的“窗口”（最小-最大范围）。一旦你找到一个在那个窗口之外有值的子节点，就报告那个子节点被放错了位置，并且不要在那个子节点的子树中继续（因为我们可以假设子树本身是一个一致的 BST）。

如果确实有一个交换，你会发现两个这样的异常。

代码

这是一些代码（实际上是 JavaScript），假设您有一个Node具有通常value,left和right属性的类，并且重复值只能存储在具有相同值的父节点的右侧。该函数将 BST 的根节点作为参数：

function findSwap(root) {
    let results = []; // This array (stack) will be filled with 2 nodes
    
    // Recursive function, which will populate the array:
    function recur(node, min, max) {
        if (node.value < min || node.value >= max) { // Out of range!
            results.push(node); // log this node, and don't bother recurring deeper
        } else {
            if (node.left != null) {
                recur(node.left, min, node.value); // Narrow the window
            } 
            if (node.right != null) {
                recur(node.right, node.value, max); // Narrow the window
            }
        }
    }
    
    // Start the search with an infinite window
    recur(root, -Infinity, Infinity);
    return results; // Return the two nodes found as an array of nodes
}

请注意，超出范围的条件恰好需要这些不等式：

node.value < min || node.value >= max

该min值表示一个允许值，但max不是。所以一个节点的有效取值范围是[min, max)（包括min，不包括max）。这是因为重复值应该始终存储在右侧的额外要求。如果您决定始终将它们存储在左侧，那么应该允许min值而不是max值上的相等性。

执行

下面是一个可运行的片段，它首先创建了这个二叉搜索树：

         ______ 8 _____
        /              \
     _ 4_           __ 12 __
    /    \         /        \
   2      6       10        14   
  / \    / \     /  \      /  \
 1   3  5   7   9    11  13    15

然后它将 6 处的子树与 10 处的子树交换。最后它调用上述函数并报告结果：

function findSwap(root) {
    let results = [];
    
    function recur(node, min, max) {
        if (node.value < min || node.value >= max) {
            results.push(node);
        } else {
            if (node.left) {
                recur(node.left, min, node.value);
            }
            if (node.right) {
                recur(node.right, node.value, max);
            }
        }
    }
    
    recur(root, -Infinity, Infinity);
    return results;
}

// Define the Node class
class Node {
    constructor(value) {
        this.value = value;
        this.left = this.right = null;
    }
    add(...values) { // Allow adding more than one value with one call
        for (let value of values) {
            if (value < this.value) {
                if (this.left) this.left.add(value);
                else this.left = new Node(value);
            } else {
                if (this.right) this.right.add(value);
                else this.right = new Node(value);
            }
        }
    }
}

// Demo:
// Create a complete binary tree with values 1 through 15
let root = new Node(8);                // root
root.add(     4,            12,        // level 1
          2,     6,     10,     14,    // level 2
        1,  3, 5,  7, 9,  11, 13, 15); // level 3

// Perform a swap of the subtree rooted in 6 and in 10:
[root.left.right, root.right.left] = [root.right.left, root.left.right];

// Call the function:
let result = findSwap(root);

// Report which subtrees were swapped
console.log(result[0].value, result[1].value); // 10, 6

当然，如果树没有恰好两个不同子树的交换，那么返回的数组将不会总是提供可靠的信息，因为它假定错误连接的子树本身仍然是一致的。

但是如果返回的数组是空的，你可能会得出 BST 没问题的结论。

检测一个子树的移动

在评论中，您给出了一个移动的子树示例（未与另一个交换）：

在此处输入图像描述

在这种情况下，上面的代码将只返回放错位置的子树，但不会提供有关该子树来自何处的信息。

如果还应该涵盖这种情况，那么我们需要更改输出，因为将另一个（退化）“子树”列为null. 因此，我建议将输出状态设置为父节点和子树被切掉的边的一侧。

可以调整上述算法，以便在只发现一个异常的情况下进行一些后处理：在这种情况下，简单的二分搜索将找到那个放错位置的子树的插入点。此后处理表示O(logn)时间复杂度，因此它不会影响整体线性时间复杂度。

这是修改后的代码，以及您发布的示例：

function findSwap(root) {
    let results = [];
    
    function recur(node, parent, side, min, max) {
        if (node.value < min || node.value >= max) {
            results.push({parent, side, node});
            return;
        }
        if (node.left != null) {
            recur(node.left, node, "left", min, node.value);
        }
        if (node.right != null) {
            recur(node.right, node, "right", node.value, max);
        }
    }
    recur(root, null, "root", -Infinity, Infinity);
    // Post processing:
    if (results.length === 1) { 
        // It was not a swap, but a move
        let value = results[0].node.value;
        // Look up the insertion point for the misplaced value (and its subtree)
        let parent = root;
        while (results.length < 2) {
            if (value < parent.value) {
                if (parent.left == null) {
                    result.push({parent, side: "left", node: null });
                } else {
                    parent = parent.left;
                }
            } else {
                if (parent.right == null) {
                    results.push({parent, side: "right", node: null });
                } else {
                    parent = parent.right;
                }
            }
        }
    }
    return results;
}

// Define the Node class
class Node {
    constructor(value) {
        this.value = value;
        this.left = this.right = null;
    }
    add(...values) { // Allow adding more than one value with one call
        for (let value of values) {
            if (value < this.value) {
                if (this.left) this.left.add(value);
                else this.left = new Node(value);
            } else {
                if (this.right) this.right.add(value);
                else this.right = new Node(value);
            }
        }
    }
}

// Demo (as in image):
let root = new Node(5);               // root
root.add(     3,            8,        // level 1
          2,     4,     7,     9);    // level 2

// Perform the move of the subtree rooted in 8, below the node 4
root.left.right.right = root.right;
root.right = null;

// Call the function:
let result = findSwap(root);

// Report which subtrees were swapped
function edgeName(edge) {
    return "the " + edge.side + " child (" + (edge.node?.value??null) + ") of node " + edge.parent.value;
}
console.log(edgeName(result[0]) + " was swapped with " + edgeName(result[1]));

推荐阅读