Tree Data Structure

[rayofdawn]

Hi,

I would like to know what is so special about tree structure in programming ? I am a beginner in programming and I have never use tree structure before. Can someone explain to me regarding this ? I know it seems a bit stupid to ask this kind of question but I really want to know it.

Thank you.

[Zachm]

What is so special about an array or a linked-list or any other data structure for that matter ? they're just a form of representing information, good for some things and bad for others, nothing special.

Generally speaking, when you look at what defines a data-structure, then I would have to say that it is three things (at least):
1. Which operations can be done on the data-structure ?
2. What is the runtime of those operations ?
3. How much space(memory) does the data-structure need ?

A tree data structure is no different. It has its operations and usages. Operations runtime and the data-structure memory usage are usually determined by the tree type (there are many different tree data-structures - binary tree, B-tree, balanced trees etc.), and implementation.

Regards,
Zachm

[rayofdawn]

Thanks for your reply.

I have another questions. In what circumstances this structure should be used ? Generally, its strengths as well as weaknesses ?

I had been searching for it since few days back and what I got is rather confusing to me.

Thank you.

[Zachm]

I cannot give a general answer as to the circumstances, as there are many different tree types. I can say that the choice of data-structure (any) is based on it's usage profile and another consideration is a trade-off between memory consumption and runtime performance.

For example, an AVL tree is a self balancing binary search tree which has the following propeties:

	   Worst case
Space	O(n)
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

So you know that you can search/insert/delete an element in O(log n) - this is useful, if those operations types are used frequently. You can compare it to a linked list, for instance:

	   Worst case
Space	O(n)	
Search	O(n)
Insert	O(1)	
Delete	O(1) (given that you have the list node in hand)

As you can see - insertion and deletion in a linked list are very fast - O(1), but searching is relatively slow - O(n), even if the list is sorted.
If my typical usage is that I do a lot of insertions and no searches, then a linked-list is a much better choice than an AVL tree.
If, however, I perform searches as frequently as I perform insertions, an AVL tree will be a better choice on average, in terms of runtime performance.

Regards,
Zachm

[tatjana]

Please,

can anyone answer on this question: Which are examples of programs who are using tree data structures?

Thanks.