Given a self-balancing binary search tree of size $n$, I want to perform the following operations:
InsertInOrderSequentialBatch
an ordered sequence of $k$ values (specialized $k \in \{2, 3, 4\}$ or generalized $k \in N $) which are guaranteed to be sequential in an in-order tree traversal immediately after insertion.For example, insert $[310, 320, 330, 340]$ into a balanced tree containing $[100, 200, 500]$.
Future insertions might still be between the inserted nodes' values.
DeleteRange
all of $k$ nodes (likewise specialized or generalized) between 2 values in the BST.
For both operations, I want the tree to remain balanced.
With a Red-Black or AVL tree, I can achieve both operations through a sequence of $k$ insertions/deletions in $\mathcal{O}(k \log n)$, but wonder if a data structure (e.g. AVL/RB tree variant) could achieve $\mathcal{O}(\log n + k \log k)$ time for a real-world performance gain (e.g. traverse tree for insertion point, insert balanced tree into insertion point, perform one auto-balance pass)?
My needs are less theoretical and more in terms of wall-time & memory pressure for an implementation of Fortune's Algorithm - an algorithm with high constant-time multipliers is unfortunately not useful. My insertion sequence is biased & frequently multimodal (modes not known prior) with long streaks of insertions/deletions within modes. My tree size is anywhere from 100 to 3000 nodes.