Trees - Dictionary example (
Page 3 of 6 )
Let's assume you are trying to write a program for a dictionary. The program reads a word from the user, and tells him the meaning of that word. But, here is a little twist. In our dictionary, we want to allow the user to add his own definitions at runtime. At any moment, the user can ask the program to add a word; he enters the word, and the definition, and it becomes part of the dictionary. We would also love to give the user the option to show all the words that start with a certain prefix. For example, the user can enter "cat," and the program shows him all the words that start in the letters "cat."
Now, how can we implement this without causing a cat-astrophe? Where will the words be stored? If you considered a sorted array, that's a good idea, because you can then use binary search to find words very fast. However, there is a small problem. How would you add new words? This will not be an easy task. You will have to find where the word should go, and you will have to move all the subsequent elements down one location, which can become a real problem if you are dealing with millions of words.
Now, let's assume that you decide to represent the dictionary as a sorted linked list. Insertion is much easier, because you can simply create a new node, and insert it at the correct location. However, searching becomes a disaster, because you can no longer use binary search to search a linked list. You will have to search the entire linked list one by one, which again can be catastrophic if you have millions of words.
So, what is the solution to this dilemma? Neither a sorted array nor a linked list works well. Each one has an advantage and a disadvantage. Wouldn't it be great if we could put the dictionary in some sort of a data structure where both insertion and searching can be done fast enough? As surprising as it may seem, using trees can solve our problem in a simple and elegant way. But how? All we have is a list of words! It doesn't even fit in a tree. Well…actually, it does. Let me explain how this is going to work.
First, we will construct the dictionary as a binary tree in the following manner. Any node will contain two strings, the word and its meaning. We will arrange the nodes such that the root will contain a word that comes alphabetically before all the words in the right subtree, and at the same time, it come alphabetically after all the words in the left subtree.
It doesn't stop here. The rule continues recursively over every node in the tree. We will construct the tree in such a way that if you look at any node, you will find that the word in it comes alphabetically before all the words of the nodes to its right, and it comes alphabetically after all the nodes to its left. For example, look at this example…
Fig 7. A valid dictionary. If only real life dictionaries were like this!
This tree fulfills all the conditions we have just outlined. Have a look at each node. Look at all the nodes to its left (children, grand children and so on). They all come alphabetically before it. Look at those to its right. They all come after it.
But the following tree…
Fig 8. An invalid dictionary
…is not good! Why? The problem is with the word "castle." It comes alphabetically before "dean", but "castle" is to its right. It should have been on the other side of "dean." This one doesn't work.
So far so good? Great. We have just re-invented a very special kind of tree called "Binary Search Trees."
/ 20 
