Home arrow Practices arrow Page 6 - Trees

Conclusion - Practices

Trees are remarkably useful and powerful data structures, with many applications. Mohamed El Dawy explains.

TABLE OF CONTENTS:
  1. Trees
  2. Representation
  3. Dictionary example
  4. Putting it Together
  5. Internet Browser
  6. Conclusion
By: Mohamed Saad
Rating: starstarstarstarstar / 23
February 01, 2005

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement


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



 
 
>>> More Practices Articles          >>> More By Mohamed Saad
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: