7 Replies - 768 Views - Last Post: 14 December 2017 - 09:24 PM

#1 geos59   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 87
  • Joined: 30-August 15

Why even use Trees at all?

Posted 14 December 2017 - 01:57 PM

If all Graphs are Tress (but not all Trees are Graphs), why bother using Trees at all?

What advantage is there to using a Tree with it's One Path Rule limitation, when I can just use a Graph?
Is This A Good Question/Topic? 0
  • +

Replies To: Why even use Trees at all?

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6962
  • View blog
  • Posts: 23,671
  • Joined: 05-May 12

Re: Why even use Trees at all?

Posted 14 December 2017 - 01:59 PM

I don't see how this is a C or C++ specific question. Moving into Computer Science...
Was This Post Helpful? 0
  • +
  • -

#3 geos59   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 87
  • Joined: 30-August 15

Re: Why even use Trees at all?

Posted 14 December 2017 - 02:00 PM

@Skydiver, sorry I'm used to asking C++ questions that I didn't even know about a CS section.

This post has been edited by geos59: 14 December 2017 - 02:01 PM

Was This Post Helpful? 0
  • +
  • -

#4 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15106
  • View blog
  • Posts: 60,397
  • Joined: 12-June 08

Re: Why even use Trees at all?

Posted 14 December 2017 - 02:39 PM

At the root I would think the implied ordering that comes part and parcel with a tree data structure.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12616
  • View blog
  • Posts: 45,770
  • Joined: 27-December 08

Re: Why even use Trees at all?

Posted 14 December 2017 - 03:14 PM

I'm not sure I entirely understand the question. Are you asking why one would implement a tree data structure instead of using an existing Graph class? Certainly one could use a Graph class, but a specific Tree class would have specific nuances. For example, a Red-Black Tree or an AVL Tree would have additional rules for inserting and removing nodes to ensure the BST is balanced. Tree data structures also support other data structures. Heaps support priority queues, and Red-Black Trees often back LinkedHashSets.

Unrooted trees are also important. Look at the minimum spanning tree problem. The story is this. Given a city during a snowstorm, what is the minimum amount of plowing the city has to do in order to ensure everyone can get between any two points? The acyclic and connected properties of a tree are important here.

Trees also come up a lot in bioinformatics. Phylogenetic trees are one example. One problem in bioinformatics is to add edges between the leaves of two phylognetic trees, and to examine the crossing numbers. See tanglegrams.
Was This Post Helpful? 3
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6962
  • View blog
  • Posts: 23,671
  • Joined: 05-May 12

Re: Why even use Trees at all?

Posted 14 December 2017 - 03:25 PM

If you know you have a tree (rooted or otherwise) versus a graph, it makes you reconsider how to represent it in memory. Where an adjacency matrix may make sense for a graph, the nature of the tree make make it such that you'll use memory more efficiently if you use an adjacency list instead.
Was This Post Helpful? 2
  • +
  • -

#7 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12616
  • View blog
  • Posts: 45,770
  • Joined: 27-December 08

Re: Why even use Trees at all?

Posted 14 December 2017 - 03:27 PM

Quote

Where an adjacency matrix may make sense for a graph, the nature of the tree make make it such that you'll use memory more efficiently if you use an adjacency list instead.


An adjacency matrix for a graph doesn't make sense, unless you are planning on using certain algorithms like the Floyd-Warshall algorithm or unless you are planning on doing certain algebraic manipulations (e.g., computational spectral graph theory). An adjacency matrix is still more memory intensive than an adjacency list.

This post has been edited by macosxnerd101: 14 December 2017 - 03:32 PM

Was This Post Helpful? 1
  • +
  • -

#8 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11573
  • View blog
  • Posts: 19,688
  • Joined: 19-March 11

Re: Why even use Trees at all?

Posted 14 December 2017 - 09:24 PM

Let's go even tighter - why use a linked list, why not just make a graph? Or, if you want to make it really obviously ridiculous, why would you design a language with any data structure except graphs? You can always represent a single piece of data as the data part of the single node of a graph with just one node, right? So why not make everything be graphs? Answer that and then follow the trail back to your original question.

Hint: think about restrictions and the benefits they bring.
Was This Post Helpful? 3
  • +
  • -

Page 1 of 1