Home arrow Practices arrow Trees

Trees

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

In this article, I am going to give an introduction to trees. Trees are unique data structures that are used to store data in a tree-like shape. They have many useful applications, which include 3D programs, data compression, Web browsers and even dictionaries. All in all, trees are wonderful data structures. Let's get started.

What are trees?

As I said, trees are a kind of data structure. If the phrase "data structure" is new to you, don't worry. It just means the way you represent data in the memory of a computer. So, trees are no more than a method for storing data in the memory of a computer. Which type of data? And when should we use trees? This is what we are going to discuss in a moment.

Trees look like the following diagram. First we have a root node which contains one item of data. The root node has some children,  and each one contains one item of data. Each one of the children, in turn, has some children, and so on...

In essence, it looks something like this:

 
Fig.1 An example of a tree

Now, you may find this pretty weird. Why would someone want to represent data that way? Let's assume we have a list of n numbers; what is the point of putting them in a tree? As we are about to see, there are some good reasons to do so. Additionally, in real life, there are several applications where trees are just the natural way to represent data.

First, before we go too far, let's look at some theory. Any tree can be represented by a tree where each node has a maximum of two children. This is called a "binary tree". A famous method to accomplish this is called "Left child, right sibling," but this is quite outside the scope of this article; check the further reading at the end of the article if you really need to know how to do it.

A binary tree looks something like this:

 
Fig 2. An example of a binary tree

Why did I introduce this? It has a very important implication. We don't need to study general trees in depth, since any tree can be represented as a binary tree. It makes sense then that, from now on, we will only focus on binary trees. As I said, we are not limiting ourselves, because any tree can be represented by a binary tree.

First, let's examine this fundamental problem: how can we represent a tree inside the computer memory?



 
 
>>> 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: