如何使一个有效的算法将一棵二叉搜索树按给定的值切成两个？

Question

实现了slowchop方法，但是它的时间复杂度为O(n)，但是当树平衡时（其中h是树的高度），我需要将它至少减少到O(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; 
}

Answer 1

null

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