I see no way to design a O(n) algorithm with the given blackbox functions and their time complexities, given that they could only be called a (maximum) constant number of times (like 3 times) to stay within the O(n) constraint.
But if it is allowed to access and create BSTs with basic, standard node manipulations (traversing via left or right child, setting the left or right child to a given subtree), then you could do the following:
Create three new empty BSTs that will be populated and returned. Name them left, mid, and right, where the first one will have all values less than k, the second one will have at the most one node (with value k), and the final one will have all the rest.
While populating left and right, maintain references to the nodes that are closest to value k: in left that will be the node with the greatest value, and in right the node with the least value.
Follow these steps:
- Apply the usual binary search to walk from the root towards the node with value k
- While doing this: whenever you choose the left child of a node, the node itself and its right subtree then belong in
right. However, the left child should at this moment not be included, so create a new node that copies the current node, but without its left child. Maintain a reference to the node with the least value in right, as that is the node that may get a left new subtree when this step occurs more than once.
- Do the similar thing for when you choose the right child of a node.
- When the node with k is found, the algorithm can add its left subtree to
left and the right subtree to right, and create the single-node tree with value k.
Time complexity
The search towards the node with value k could take O(n) in the worst case, as the BST is not given to be balanced. All the other actions (adding a subtree to a specific node in one of the new BSTs) run in constant time, so in total they are executed O(n) times in the worst case.
If the given BST is balanced (not necessarily perfectly, but like with AVL rules), then the algorithm runs in O(logn) time. However, the output BSTs may not be as balanced, and may violate AVL rules so that rotations would be needed.
Example Implementation
Here is an implementation in JavaScript. When you run this snippet, a test case will run one a BST that has nodes with values 0..19 (inserted in random order) and k=10. The output will iterate the three created BSTs in in-order, so to verify that they output 0..9, 10, and 11..19 respectively:
class Node {
constructor(value, left=null, right=null) {
this.value = value;
this.left = left;
this.right = right;
}
insert(value) { // Insert as a leaf, maintaining the BST property
if (value < this.value) {
if (this.left !== null) {
return this.left.insert(value);
}
this.left = new Node(value);
return this.left;
} else {
if (this.right !== null) {
return this.right.insert(value);
}
this.right = new Node(value);
return this.right;
}
}
// Utility function to iterate the BST values in in-order sequence
* [Symbol.iterator]() {
if (this.left !== null) yield * this.left;
yield this.value;
if (this.right !== null) yield * this.right;
}
}
// The main algorithm
function splitInThree(root, k) {
let node = root;
// Variables for the roots of the trees to return:
let left = null;
let mid = null;
let right = null;
// Reference to the nodes that are lexically closest to k:
let next = null;
let prev = null;
while (node !== null) {
// Create a copy of the current node
newNode = new Node(node.value);
if (k < node.value) {
// All nodes at the right go with it, but it gets no left child at this stage
newNode.right = node.right;
// Merge this with the tree we are creating for nodes with value > k
if (right === null) {
right = newNode;
} else {
next.left = newNode;
}
next = newNode;
node = node.left;
} else if (k > node.value) {
// All nodes at the left go with it, but it gets no right child at this stage
newNode.left = node.left;
// Merge this with the tree we are creating for nodes with value < k
if (left === null) {
left = newNode;
} else {
prev.right = newNode;
}
prev = newNode;
node = node.right;
} else {
// Create the root-only tree for k
mid = newNode;
// The left subtree belongs in the left tree
if (left === null) {
left = node.left;
} else {
prev.right = node.left;
}
// ...and the right subtree in the right tree
if (right === null) {
right = node.right;
} else {
next.left = node.right;
}
// All nodes have been allocated to a target tree
break;
}
}
// return the three new trees:
return [left, mid, right];
}
// === Test code for the algorithm ===
// Utility function
function shuffled(a) {
for (let i = a.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[a[i], a[j]] = [a[j], a[i]];
}
return a;
}
// Create a shuffled array of the integers 0...19
let arr = shuffled([...Array(20).keys()]);
// Insert these values into a new BST:
let root = new Node(arr.pop());
for (let val of arr) root.insert(val);
// Apply the algorithm with k=10
let [left, mid, right] = splitInThree(root, 10);
// Print out the values from the three BSTs:
console.log(...left); // 0..9
console.log(...mid); // 10
console.log(...right); // 11..19
与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
