java我需要找到与slowChop具有类似功能的fast chop

Question

我已经实现了BinarySearchTree。慢跳，但需要实现更快的算法

定义：

public BinarySearchTree<Node,T> chop(T x)

在元素x处将我们的排序集分成两部分。SSet包含元素<；x、 并且返回的SSet是包含元素的SSet>；=x、 这应该适用于所有元素，而不管它们是否在该视图中。

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

slowChop方法已实现，但需要O（n）时间，如果树是平衡的，则需要将其至少减少到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; 
  }

以下驱动器链接包含帮助器类：BinarySearchTree BinaryTree DefaultComparator SSet

https://drive.google.com/drive/folders/1Uc6pNFg8e3WyeiinVFk6yA4W0LdB6UGx?usp=sharing