0

public BinarySearchTree<Node,T> chop(T x) 我在 element实现了将我的树分成两部分x。SSetthis将包含元素 < x，返回的 SSet 是一个包含元素 >= 的 SSet x。这应该适用于所有元素，无论它们是否在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;
  }
4

1 回答 1

2

实际上，您的算法没有利用您从处理二叉搜索树这一事实中获得的效率。所以用中序遍历遍历树不是要走的路。

相反，执行二分搜索并切割连接两个节点的边，这些节点应该最终在不同的树中。在切割时，您还需要将节点重新附加到执行先前切割的位置。复杂度与向树底部的二进制搜索相同，因此为 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());
}
于 2021-11-28T10:53:24.987 回答