java - Change binary search tree to balance

Question

I have just learnt how to create a binary search data structure, which is going to be used to store thousands of words from a dictionary. The problem that I am getting is that it is taking a long time to count add and remove data. Usually 199263ms or 200 seconds for 100000 words to count. I was told that having a tree that can self balance will improve the efficiency and make the operations faster.

My question is how can I make my tree auto balance so to make it efficient. I have made slight improvements by eliminating duplicate words to make the height of the tree to be shorter.

If someone can give me advice on how i can make the tree efficient and how I can implement balancing tree in java will be helpful.

Answer 1

You should look into red/black trees, which are self balancing. The nodes store a color in addition to an element, and every time the tree is modified, you rebalance the tree so that it meets the properties of a red/black tree:

(From Wikipedia:)

1. Each node is either red or black.

2. The root is black.

3. All leaves (NIL) are black.

4. If a node is red, then both its children are black.

5. Every?path?from a given node to any of its descendant NIL nodes contains the same number of black nodes.

To get started implementing a red black tree, I recommend looking at this example implementation on github, and reading this explanation of red black trees.