Ok, I did some quick tests and as predicted since the tree height is bounded logarithmically when inserting not rebalancing on deletion doesn't seem to be a big problem in most use cases, so I don't think I'm going to continue on that path. Francesco.