0
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 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
    Commented Sep 27, 2016 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
    Commented Sep 27, 2016 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
    Commented Sep 27, 2016 at 7:20
  • 1
    $\begingroup$ This is what happens internally. $\endgroup$
    – Spotted
    Commented Sep 27, 2016 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
    Commented Sep 27, 2016 at 7:31

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.