Thread: Tree Structures Best Structures!!! Discuss.

  1. #16
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    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
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    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. #18
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    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
    Ireland
    Posts
    8,446
    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.
    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
    5,108
    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
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

  6. #21
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

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, 11:15 PM