如何制作一种有效的算法，通过给定的值将二叉搜索树一分为二?

Question

我实现了public BinarySearchTree<Node,T> chop(T x)在元素x处将我的树切成两部分.SSetthis将包含元素<x，返回的>=x的 SSet。这应该适用于所有元素，无论它们是否在this.

例如，假设s={2,4,6,8}.然后s.chop(3)返回{4,6,8}，s变得{2}。对于s.chop(4)，我们会得到相同的结果。

实现了slowChop方法，但它的时间复杂度为 O(n)，但是当树平衡时，我需要将其至少减少到 O(h)(其中h是树的高度)。

public BinarySearchTree<Node,T> slowChop(T x) {
Node sample = super.newNode();
BinarySearchTree<Node,T> other = new 
BinarySearchTree<Node, T>(sample);
// Iterate through the n nodes in-order.
// When see value >=x, add to new BST in O(height) time, and
// remove it from this BST (on next iteration) in O(height) time.
Iterator<T> it = iterator();
T prev = null;
while( it.hasNext() ) {
T curr = (T)(it.next());
if( c.compare(curr, x) >= 0 ) { // we have our first >= x 
other.add(curr);
if( prev != null ) {
this.remove(prev);          // safe to remove now
}
prev = curr;
}
}
if( prev != null ) {
this.remove(prev); // edge case, get that last one!
}
return other; 
}

public BinarySearchTree<Node,T> chop(T x) {
Node sample = super.newNode();
BinarySearchTree<Node,T> other = new 
BinarySearchTree<Node, T>(sample);
// TODO: Implement this method. It should match slowChop in
// behaviour, but should be faster :-)


return other;
}

Answer 1

事实上，你的算法没有利用你从处理二叉搜索树的事实中获得的效率。因此，通过按顺序遍历遍历树不是要走的路。

相反，执行二叉搜索并切割链接两个节点的边缘，这些节点最终应该在不同的树中。切割时，您还需要将节点重新附加到上一次切割的位置。复杂性与树底部的二叉搜索相同，因此它是 O(logn)。

下面是一个实现，它假设您有常规的 getter 和 setter：

• 在Node类上：getLeft、setLeft、getRight、setRight、getValue和
• 在BinarySearchTree类：getRoot，setRoot

public BinarySearchTree<Node,T> chop(T x) {
// Create two temporary dummy (sentinel) nodes to ease the process.
Node rightRootParent = super.newNode();
Node leftRootParent = super.newNode();

// Set "cursors" at both sides
Node rightParent = rightRootParent;
Node leftParent = leftRootParent;

// Start the binary search for x, cutting edges as we walk down
Node node = this.getRoot();
while (node != null) {
// Decide for each node in the binary search path at which side it should go
if (c.compare(node.getValue(), x) >= 0) {
// Node should belong to the right-side tree
rightParent.setLeft(node); // Establish edge
rightParent = node; 
node = node.getLeft(); // Move down
rightParent.setLeft(null); // Cut next edge for now (it might get restored)
} else { // Symmetric case
leftParent.setRight(node);
leftParent = node;
node = node.getRight();
leftParent.setRight(null);
}
}

// Set the roots of both trees
this.setRoot(leftRootParent.getRight());
return BinarySearchTree<Node, T>(rightRootParent.getLeft());
}