I am wondering what happens if you remove an object in the middle of a treemap. If the treemap would look something like this:

enter image description here

So what would happen if you remove the number 30? Because 27 and 34 will disconnect from the tree.

  • 4
    $\begingroup$ Are you talking about the specific implementation in Java (TreeMap) or just in general? The short answer is you have to reattach all the disconnected nodes. $\endgroup$ – jonrsharpe Sep 27 '16 at 7:17
  • 3
    $\begingroup$ Stack Overflow isn't the place to come to for answers from the textbook. If you ask specifically about java.util.TreeMap, read about Red-Black trees and study the source code. $\endgroup$ – Marko Topolnik Sep 27 '16 at 7:19
  • 1
    $\begingroup$ According to the docs I just linked, it uses the algorithm from CLR; if you want more info, that's where to look. $\endgroup$ – jonrsharpe Sep 27 '16 at 7:20
  • 1
    $\begingroup$ This is what happens internally. $\endgroup$ – Spotted Sep 27 '16 at 7:22
  • 2
    $\begingroup$ Red-black trees are a very well-known, classical technique. The definitive explanation on how they work, including adding, removing, balancing etc. is in the book Introduction To Algorithms by Cormen, Leiserson and Rivest (shortly referred to as CLR). If you want to understand the code, you should familiarize yourself with the technique, the "coloring" of the nodes etc. Most people here don't wish to re-introduce this well-known explanation, so you should go to the source (or try Wikipedia). $\endgroup$ – RealSkeptic Sep 27 '16 at 7:31

I think there are two cases here

  1. 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.
  2. 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy