I use a self-balancing binary search tree (currently it is an AVL tree but can be substituted with another one). I noticed that there are distinct periods when only certain operation is performed: large deletion or insertion batches are executed rarely while most of the time it is immutable search tree. Will there be any perfomance gain if i postpone rebalancing to the end of the batch?
For batch insertions, insert the new items into a separate AVL tree, and then merge the two trees as described in http://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/. Merging the trees is an O(m+n) operation, where m and n are the sizes of the two trees. This approach should be much faster when the number of new items is small compared to the number of items in the existing tree.
For batch deletions, mark the items in the AVL tree as deleted. Then, do an inorder traversal of the tree, building a new AVL tree from the non-deleted nodes. See http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ for an example. Building a new tree from a sorted list of nodes is an O(n) operation.