识别二叉搜索树中交换的子树
Identify swapped subtrees in a binary search trees
我正在看这个挑战：
Suppose two subtrees in a binary search tree have been swapped, and that the BST property is broken. Devise an algorithm that identifies the two swapped subtrees in O(n) time.
我的想法
当一个 BST 的中序遍历完成后，元素就被排序了。
现在当交换两个子树时，中序遍历将
不被排序。所以如果对比一下原来的中序遍历
树和交换的树，就好像你拿了两个子集
原始数组中的排序数组并交换它们。
但是现在挑战是识别相应的子树，我不知道如何从中序遍历中推导出来。
首先，如果树有重复的值，并且它们并不总是存储在父节点的同一侧（具有相同的值），那么并不总是能够检测到交换。想象一棵树在许多不同的地方具有相同的价值：
______ 8 _____
/ \
_ 8_ ___ 8 __
/ \ / \
2 8* 8* 14
/ \ / \ / \ / \
1 3 8 8 8 8 13 15
这是一个有效的 BST。如果我们要交换标有星号的两个子树，我们最终会得到一个有效的 BST，因此无法检测交换了哪些子树。很可能是第一个 *-node 的子节点被交换了，或者第二个 *-node 的子节点被交换了。没有办法知道这一点。
因此，只有交换的结果将涉及的两个子树插入到无效位置时，才有可能检测到交换。确保这一点的一种方法是规定重复值应始终存储在具有相同值的父节点的同一侧（例如右侧）。
算法
中序遍历是个好主意，但是验证访问的节点是否以正确的顺序出现的想法不太有用。
相反，在遍历期间，跟踪“window”（最小-最大范围）当前访问的子树中允许的值之间的值。一旦发现一个子节点的值超出 window，就报告该子节点放错了位置，并且不要在该子节点的子树中继续（因为我们可能假设子树 本身 是一致的 BST）。
如果确实有一个交换，你会发现两个这样的异常。
代码
这是一些代码（实际上是 JavaScript），假设你有一个 Node class 和通常的 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）。这是因为重复值应始终存储在 right 侧的额外要求。如果您决定始终将它们存储在 左侧 侧，那么应该允许 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
当然，如果树没有正好交换两个不同的子树，那么 returned 数组将不会总是提供可靠的信息，因为它假定错误附加的子树本身仍然是一致的.
但是如果 returned 数组为空，您可能会得出 BST 没问题的结论。
检测一棵子树的移动
在评论中你给出了一个被移动的子树的例子（没有与另一个交换）：
在那种情况下，上面的代码将 return 只是放错位置的子树，但不会提供有关此子树来自何处的信息。
如果还应涵盖这种情况，那么我们需要更改输出，因为将另一个（退化的）“子树”列为 null 并没有真正帮助。所以我建议输出状态是 parent 和 side 子树被切掉的边缘。
可以调整上述算法，以便在只发现一个异常的情况下进行一些 post 处理：在这种情况下，简单的二分搜索将找到那个放错位置的子树的插入点。这个 post 处理代表 O(logn) 时间复杂度，因此它不会影响整体线性时间复杂度。
这是改编后的代码，以及您post编辑的示例：
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]));
我正在看这个挑战：
Suppose two subtrees in a binary search tree have been swapped, and that the BST property is broken. Devise an algorithm that identifies the two swapped subtrees in O(n) time.
我的想法
当一个 BST 的中序遍历完成后，元素就被排序了。 现在当交换两个子树时，中序遍历将 不被排序。所以如果对比一下原来的中序遍历 树和交换的树，就好像你拿了两个子集 原始数组中的排序数组并交换它们。
但是现在挑战是识别相应的子树，我不知道如何从中序遍历中推导出来。
首先，如果树有重复的值，并且它们并不总是存储在父节点的同一侧（具有相同的值），那么并不总是能够检测到交换。想象一棵树在许多不同的地方具有相同的价值：
______ 8 _____
/ \
_ 8_ ___ 8 __
/ \ / \
2 8* 8* 14
/ \ / \ / \ / \
1 3 8 8 8 8 13 15
这是一个有效的 BST。如果我们要交换标有星号的两个子树，我们最终会得到一个有效的 BST，因此无法检测交换了哪些子树。很可能是第一个 *-node 的子节点被交换了，或者第二个 *-node 的子节点被交换了。没有办法知道这一点。
因此，只有交换的结果将涉及的两个子树插入到无效位置时，才有可能检测到交换。确保这一点的一种方法是规定重复值应始终存储在具有相同值的父节点的同一侧（例如右侧）。
算法
中序遍历是个好主意，但是验证访问的节点是否以正确的顺序出现的想法不太有用。
相反，在遍历期间，跟踪“window”（最小-最大范围）当前访问的子树中允许的值之间的值。一旦发现一个子节点的值超出 window，就报告该子节点放错了位置，并且不要在该子节点的子树中继续（因为我们可能假设子树 本身 是一致的 BST）。
如果确实有一个交换，你会发现两个这样的异常。
代码
这是一些代码（实际上是 JavaScript），假设你有一个 Node class 和通常的 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）。这是因为重复值应始终存储在 right 侧的额外要求。如果您决定始终将它们存储在 左侧 侧，那么应该允许 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
当然，如果树没有正好交换两个不同的子树，那么 returned 数组将不会总是提供可靠的信息，因为它假定错误附加的子树本身仍然是一致的.
但是如果 returned 数组为空，您可能会得出 BST 没问题的结论。
检测一棵子树的移动
在评论中你给出了一个被移动的子树的例子（没有与另一个交换）：
在那种情况下，上面的代码将 return 只是放错位置的子树，但不会提供有关此子树来自何处的信息。
如果还应涵盖这种情况，那么我们需要更改输出，因为将另一个（退化的）“子树”列为 null 并没有真正帮助。所以我建议输出状态是 parent 和 side 子树被切掉的边缘。
可以调整上述算法，以便在只发现一个异常的情况下进行一些 post 处理：在这种情况下，简单的二分搜索将找到那个放错位置的子树的插入点。这个 post 处理代表 O(logn) 时间复杂度，因此它不会影响整体线性时间复杂度。
这是改编后的代码，以及您post编辑的示例：
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]));