Like Tree8Likes

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. #16
    Registered User
    Join Date
    Oct 2011
    Posts
    823
    Quote Originally Posted by manasij7479 View Post
    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. #17
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  3. #18
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    996
    Omg, manasij7479 are you on Arch Linux too??? Omg, omg, omg, this is amazing! We're brothers in Linux!

  4. #19
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,403
    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.
    Last edited by Mario F.; 09-06-2013 at 05:11 PM.
    phantomotap likes this.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #20
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,145
    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
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

  6. #21
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.
    laserlight likes this.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Data structures --binary search tree
    By shikhardeep in forum C Programming
    Replies: 3
    Last Post: 09-20-2011, 04:34 PM
  2. malloc for tree structures
    By Tumbuler in forum C Programming
    Replies: 1
    Last Post: 10-31-2007, 06:43 PM
  3. Structures, passing array of structures to function
    By saahmed in forum C Programming
    Replies: 10
    Last Post: 04-05-2006, 11:06 PM
  4. Replies: 5
    Last Post: 04-11-2002, 11:29 AM
  5. Shared memory in Linux: B-TREE of structures
    By zahid in forum Linux Programming
    Replies: 3
    Last Post: 01-26-2002, 10:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21