What happens internally when you remove an object from a treemap
I think there are two cases here 


Java Collections implementation : 
 In this case Java uses red black tree to keep the tree balanced and to maintain the order. Thus if you are removing a node in such a tree it will adjust itself without breaking anything and will form a perfect BST even after removal. Red black trees are self balancing trees so it will also arrange itself to maintain log(n) height where n is the number of nodes. Thus for sure you will not lose any data here.
Your custom implementation : 
In this case you have to do all the painful things which I have explained above. However you have an option to maintain the order or to rebalance the tree as per your requirements.