Delete a range of keys in a binary search tree in better than $O(n\lg n)$?

Question

Obviously, the brute force method of:

DeleteRange(root, low, high)
    for n = low to high
        if n == root.key // key found
            return DeleteNode(root) // O(lg n) to delete
        elseif n < root.key // in left sub-tree
            root.left = DeleteRange(root.left, n, high) // recur into left sub-tree
        elseif n > root.key // in right sub-tree
            root.right = DeleteRange(root.right, n, high) // recur into right sub-tree
        else // root.key == null, key not found
            return null
   return root

would take $O(n\lg n)$ time. So is there any "smarter" way of deletion that would do the same thing with less complexity, perhaps pruning entire sub-trees at once? Assume that the deleted nodes are not needed and the only concern is with returning the root of a binary search tree where the nodes between the range of two keys are deleted.

Answer 1

You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in $O(k + \log n)$ time, where $n$ is the initial number of items in the tree and $k$ is the number of items deleted (and returned to the caller). Full disclosure: I am the author.

I have to emphasize that the data structure does not support the insert operation, but is optimized for clone and delete_range. I have written up an informal description of the algorithm. With all the optimizations the code is now significantly different from that document, but it should be enough to grasp the idea.