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

DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

Comments On: Trees

· This article is difficult to follow and seems poorly organized for the first three...    · Dear David, Thank you very much for reading the article, and for having the time...    · I did not dislike the article necessarily - there were just a lot of things in it...    · While it is true that all tree data -can- be represented as a binary tree, there are...   >>> Post your comment now!