# Tree Structures Best Structures!!! Discuss.

This is a discussion on Tree Structures Best Structures!!! Discuss. within the General Discussions forums, part of the Community Boards category; Originally Posted by manasij7479 Is this a known/commonly used method of implementation? Well, considering that even the pseudocode example in ...

1. Originally Posted by manasij7479
Is this a known/commonly used method of implementation?
Well, considering that even the pseudocode example in the Wikipedia article relies on using a disjoint-set data structure, I'd say so

Disjoint sets are very, very common with graphs of all sorts.

(I initially learned of these from Data Structures and Algorithm Analysis in C by Mark Allen Weiss. I don't like the code examples, but I do like the text and illustrations.)

2. Nice to see that.

I'm studying graph theory from a book in which the pseudocode examples are given in a way that is simple to analyse mathematically and easy to comprehend at once.
( graphbook - A book on algorithmic graph theory - Google Project Hosting )
...It seems to be a nice book for me, probably because the logic is presented in a way that matches my intuition.

So, I'm somewhat unfamiliar with the implementation details and 'tricks' !
I'm going to look into a book like the one (or the one) you suggested to gain these when I'm done with the theory.

3. Omg, manasij7479 are you on Arch Linux too??? Omg, omg, omg, this is amazing! We're brothers in Linux!

4. Well, the Kruskal algorithm is traditionally implemented with a disjoint-set. In the algorithm description all the elements are there: makeset, find and union (or merge). So it's hard not to think of disjoint sets. Your major concern is going to be what to use; a linked list or a tree to represent the sets, depending on whether your data will favor fast find or fast merge.

There are a possible optimizations if you construct your trees with path compression and make unions by size or tree height.

EDIT: To the OP, I don't much favor trees. I prefer simpler data structures over trees if the opportunity presents itself. For instance, I'll always use an ordered list for an index if I know I will never need to update it. The reason for this is that trees tend to complicate code writing and maintenance. In fact, I'm known for having used arrays or hash tables when I could/should have used trees. Simply because performance wasn't a concern and somehow I could write clearer code that way. This goes in hand with the notion that one should use the best data structure for the job. It's just that we tend to forget 'best' has a broad meaning.

5. For instance, I'll always use an ordered list for an index if I know I will never need to update it.
O_o

I'm much the opposite, preferring variations on a B+Tree, but I like the you went on that path.

I tend to... think better? with those structures so my code quality is superior, and I'm perfectly willing so sacrifice a little performance for the better code in many, many places.

Soma

6. I tend towards hash tables. However, it really comes down to what the task at hand is. I have never thought of my 'favorite' data structure. Whatever data structure gets the job done on time is my favorite.

Page 2 of 2 First 12