如何实现按给定值拆分二叉搜索树的O(h)时间复杂度高效算法？

首先利用二叉搜索树（BST）的有序性质，无需遍历所有节点，仅沿着根到叶子的单条路径调整节点指针即可完成分割，时间复杂度严格为O(h)（h为树高，平衡树场景下h=logn），核心逻辑如下：

• 所有值小于x的节点保留在当前树，所有值大于等于x的节点归入返回的新树
• 拆分过程中仅调整节点的父/子引用，不新增或删除节点，避免重复的add/remove开销

public BinarySearchTree<Node,T> chop(T x) {
    Node sample = super.newNode();
    BinarySearchTree<Node,T> other = new BinarySearchTree<Node, T>(sample);
    // 两个哑节点分别挂载拆分后的两个子树
    Node leftDummy = super.newNode(); // 挂载当前树（<x的节点）
    Node rightDummy = super.newNode(); // 挂载other树（>=x的节点）
    Node leftTail = leftDummy;
    Node rightTail = rightDummy;
    Node curr = this.root;

    while (curr != null) {
        int cmp = c.compare(curr.data, x);
        if (cmp < 0) {
            // 当前节点及左子树全属于<x的部分，接到当前树的尾部右节点
            leftTail.right = curr;
            leftTail = curr;
            // 继续处理可能存在>=x节点的右子树
            curr = curr.right;
        } else {
            // 当前节点及右子树全属于>=x的部分，接到other树的尾部左节点
            rightTail.left = curr;
            rightTail = curr;
            // 继续处理可能存在<x节点的左子树
            curr = curr.left;
        }
    }

    // 断开尾部的多余引用，避免残留无效子树
    leftTail.right = null;
    rightTail.left = null;

    // 更新两棵树的根节点
    this.root = leftDummy.right;
    other.root = rightDummy.left;

    // 更新两棵树的大小，若你的BST类的size是O(1)维护的字段，需按如下方式更新
    // 若节点已维护子树大小属性，直接取对应root的size即可，无需遍历
    this.size = countNodes(this.root);
    other.size = countNodes(other.root);

    return other;
}

// 辅助统计子树节点数的方法，若节点本身维护size属性可省略该方法
private int countNodes(Node node) {
    if (node == null) return 0;
    return 1 + countNodes(node.left) + countNodes(node.right);
}

• 该实现自动覆盖x是否存在于树中的所有场景，和原slowChop的行为完全一致
• 若你使用的平衡BST（如AVL、红黑树）的节点维护了子树大小字段，可直接替换countNodes逻辑为读取根节点的size属性，整体时间复杂度可稳定保持O(h)
• 所有节点仅修改引用指向，没有重复的插入删除操作，性能远高于O(n)的原实现

内容的提问来源于stack exchange，提问作者Nihal Modaress