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; Hello All, I think tree structures are the best structures. Granted, they aren't always but when a tree is applicable, ...

  1. #1
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,086

    Tree Structures Best Structures!!! Discuss.

    Hello All,

    I think tree structures are the best structures. Granted, they aren't always but when a tree is applicable, it's better than others.

    Does anyone have examples proving otherwise or a favorite structure that they'd like to talk about?

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    It really depends on what you're doing. I find cyclical doubly-linked lists much more convenient ( and faster ) if I'm not doing any searches.
    Devoted my life to programming...

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,772
    Quote Originally Posted by MutantJohn
    Granted, they aren't always but when a tree is applicable, it's better than others.
    Counter-example: if you are implementing a mapping from a key to a value, a (balanced binary) tree is applicable. However, depending on the characteristics of the expected data and the desired performance characteristics of certain operations, a hash table implementation may be better.

    EDIT:
    Actually, your caveat effectively amends your own declaration from "tree structures are the best structures" to "tree structures are the best structures when they are applicable". You might as well amend that further to "tree structures are the best structures when they are the best for the job", but then that's not a particularly interesting reason to explain why you like them since it applies to pretty much every other data structure
    Last edited by laserlight; 09-05-2013 at 12:40 PM.
    vart and Elkvis like this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    For example simple array is mapping of integer key in the range [0-n] to value, and as such mapping could be replaced by tree. But why bother?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,086
    Fine, let's assume my claim more ignorant and biased.

    But trees have the advantage of being collapsable into a 1D or 2D array. I know most CUDA implementations of a tree use an array representation rather than the typical top-down view I picture when I draw trees.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,772
    Um, so what are you trying to say now?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    You know that arrays can basically store any data structure? If the data conforms to the heap property, it's a tree. You might use an array as a linked list if you can traverse it using data found in the contents. Arrays can contain flattened matrices, the values of a hash table, graphs, or, you know, it could just be an array.
    vart likes this.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    And RAM is just an array of bytes, after all.
    Elkvis and whiteflags like this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User
    Join Date
    Oct 2006
    Posts
    2,422
    Quote Originally Posted by oogabooga View Post
    And RAM is just an array of bytes, after all.
    or in the case of computers that use NUMA architecture, an array of arrays of bytes.
    Code:
    namespace life
    {
        const bool change = true;
    }

  10. #10
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,086
    XD

    You guys are tough to troll

    When I wrote this I was mostly thinking of trees as solutions to every problem and that no matter what, a tree is always the solution. Like, I think trie structures are a pretty neat idea and Delaunay trees are cool too. Octrees were also really popular in astrophysics simulations. And collision resolution likes them too though I think using triangles and barycentric coordinates is the superior way of solving them now so no more quadtree spatial refinement for that. And I think triangles fill space finer.

    Nevertheless, I think trees are cool and in combination with vectors, I don't really see the point of anything else, tbh.

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    John, I can say that my thread for the Octree increased your excitement very much.

    However, there is no optimal data structure. All data structures can be useful, if they are selected in the appropriate application. There is always a trade-off around them.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  12. #12
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    I love thinking about different ways to solve a particular problem. Data structures are just one tool, or component, or part, or way to approach.


    I believe the ability to overcome ones natural instincts, and seriously considering how to approach a problem using different tools rather than your currently-favourite one, is something every good developer should strive at. Not for the sake of the tools, but to keep your mind working at problems from different angles.

    That said, having interest in a specific tool -- be it code or method or algorithm or data structure or whatever -- makes it optimal, results-wise, to play with and practice that tool. The related emotions seem to enhance memory retention and deep understanding, and boost your self-esteem, too. The interest will wane over time, because we are only human. So, it's very important and efficient to play/train with things you're interested in and have fun with, rather than force yourself to work with tools you don't like.

    MutantJohn, perhaps you should have asked something along the lines of

    I really like how tree structures can be used to solve problems (perhaps noting a past thread or two as examples).

    Are there any other data structures that are similarly well suited to specific types of problems? Any favourites? Any that open up classes of solutions/problems like trees did for me?

    If you had, then someone might have mentioned hashing (or hash tables in particular) and disjoint sets.
    laserlight likes this.

  13. #13
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,086
    Ooh, what's a disjoint set?

  14. #14
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    See Disjoint set data structure at Wikipedia for details.

    Consider a problem where you have an image, and you wish to know how many areas there are in the image. You only need one function, say similar(pixel1, pixel2), which returns logical true if and only if the two neighboring pixels are in the same area.

    Initially, you create a disjoint set of each pixel in the image, with each pixel in their own set. You pass over the entire image, comparing each neighboring pixel pair only once, and if they are in the same area, join the two sets.

    The data structure tells you exactly which area each pixel belongs to. Counting the unique areas is just a pass over the disjoint data set; it will then tell you exactly how many separate areas there are in the image. In the image case, you can also calculate e.g. the centroid of each area at the same time, which is very useful.

    Typical implementation for the disjoint data set is basically a single pointer (or index) for each element, initialized to point to itself. Joining two elements is done by first traversing the chains for both elements (till they point to themselves), and set one root point to the other. (Usually a path compression step is done to optimize amortized cost, as the Wikipedia article describes.)

    Another common use is in games, where you have a number of "rooms", and you are interested in whether you can get from "room" A to "room" B. You construct and maintain the disjoint set based on neighboring rooms, updating the structure if doors are opened. You only need to probe the disjoint set entries for both rooms to find out if you can get from one to the other.

    You can also augment the disjoint set elements by approximate distance, and join and path-compress in a way that minimizes the distances. This allows you to do stuff like proper sound propagation and attenuation from a static source (the data structure needs to be regenerated if the source or any of the sources move).
    (In games, having such a structure for each room, with the player at the source, regenerating whenever player enters a new room, allows very efficient implementation of realistic (player scent, player noises) monster triggers.)

  15. #15
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Nominal Animal View Post
    That gives me a nice idea about implementing Kruskal's MST algorithm.

    I can store each subtree as disjoint sets, and adding new edges to a set if it remains a tree (easy to check E==V-1) or if the edge has its ends in two different sets (thus...'union' from the wiki article).

    This seems simpler than checking for a cycle within each iteration.

    Is this a known/commonly used method of implementation?
    If not, is there a reason this isn't feasible?
    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 !



Page 1 of 2 12 LastLast
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