Trees - Conclusion (
Page 6 of 6 )
Though trees seem complex at first, they are fairly powerful data structures. We have looked at two representations for trees, the array, and the linked structure. We have also covered some examples of how to use trees. The concept of a binary search tree was introduced as an alternative to storing data in an array or a linked list. Overall, I hope I could get you interested in this amazing data structure.
So, what's next? If you are still looking for more, you are in luck, because there are plenty of things you can do with trees, and plenty of material for you to read about the subject. Do you remember our first example, where we showed that, if the tree gets skewed, everything gets screwed? There are many solutions to this problem; the nicest is a special kind of binary search tree called an "AVL tree." This kind of tree rotates if it gets imbalanced, to force the tree to balance itself!
There are other kinds of trees, like BSP trees, which are similar to the trees we used for our second example. They are more complex, however, and used in 3D programs. For example, they were used in the games Doom and Quake.
Further reading
[1] We didn't mention how we can delete elements from a binary search tree. Point your browser here for more details: http://www.cs.oberlin.edu/classes/dragn/labs/avl/avl4.html. This site also explains how to do range searching in a binary search tree.
[2] As promised, here is a site about AVL trees: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/AVL.html
[3] If you are curious about how any general tree can be represented as a binary tree, look over here: http://www.nist.gov/dads/HTML/binaryTreeRepofTree.html
/ 20 
