Talk:Tree (data structure)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 

Definition[edit]

It seems better to define ordered tree as tree with ordered arrows outgoing from every node - not childs - as it gives possibility to define ordered graph, not only tree. AlexShkotin 05:49, 14 September 2006 (UTC)

Shouldn't this page be at Tree (data structure)? -- Timwi 18:33, 21 Jan 2004 (UTC)

I believe you are correct. To aleiviate this, I offer a poem, composed by a coworker:

red node,
black node,
sittin in a tree,
it's arranged in
bi - nar - y

insert a node,
rotate the tree,
nothing beats
log(N) complexity!

-- UtherSRG 17:09, 20 Apr 2004 (UTC)

Range tree?[edit]

There is a type of tree used to implement this ADT:

  • add(start, end, amount)
  • get(key)

In other words, one can add a certain amount to each index in a range, and retrieve the total for a index. For example:

add(1, 5, 1)

add(3, 10, 5)

get(2) // returns 1

get(4) // returns 6

get(9) // returns 5

A friend of mine (who taught the structure to me) said it was called a radix tree, but they seem to be different. What is it called? --대조 | Talk 22:23, 8 December 2005 (UTC)

I don't know of a name for this data structure, but it's somewhat related to the interval tree in that it stores a set of intervals. One simple way to solve the problem is to use an interval tree to look up all the intervals containing the point and then add up their associated values, but I imagine you can do something more clever. I'll see if I run across anything. Deco 22:55, 8 December 2005 (UTC)

Binary Expression Trees[edit]

I think someone with more time should consider adding this subject here or create a page for it.

One-to-one mapping[edit]

Can someone who understands "there is a one-to-one mapping between binary trees and general ordered trees " explain what it means and why it's true? It strikes me as wrong - since binary trees is a proper subset of ordered trees, a one to one mapping is impossible. -- ridiculous_fish

I agree with ridiculous_fish--if this statement is true, it should be explained in plain terms. I could not understand it either, and came into the discussion area to convey the same message. —The preceding unsigned comment was added by 202.54.85.131 (talk) 12:08, 5 January 2007 (UTC).
It's not impossible - because there are an infinite number of binary trees. This is one of the weird things about infinity. For example, there is a one-to-one mapping between the integers and the even integers: just multiply/divide by two. In the case of trees, the diagram gives an intuitive sense for the mapping - it's a bit difficult to put in words, but basically what was once "the next child of your parent" becomes "your right child". For more on this topic check out countable set. Deco 04:09, 16 February 2006 (UTC)
I read "there is a one-to-one mapping between binary trees and general ordered trees" as referring to trees storing N items. Any other interpretation doesn't make sense to me - what does it mean to map a tree of N elements to a tree of 2N elements? Where do the extra elements come from, especially if they represent something real, like elements on the Periodic Table? Thus the set-theoretic argument doesn't apply, and indeed the diagram you refer to seems to support this notion - the mapping does not change the number of nodes, only their place in the graph. There is, of course, no one to one mapping between a finite set and one of its proper subsets.
I think I found the diagram you refer to at the bottom of Binary tree. From this diagram, we have to conclude that either binary trees are not ordered trees (which contradicts the earlier part of the sentence) or this mapping is not one to one. As an example, these two two-element binary trees:
 A                A
   \             /
    B          B
both get mapped to the same binary tree under this "one to one mapping," namely:
     A
   /
 B
I think the key here is that binary trees are allowed to have null children, but ordered trees are not, so that the two trees in the domain are considered equivalent ordered trees. But then binary trees are not examples of ordered trees, since the two trees in the domain, interpreted as binary trees, definitely represent something different.
This is all true, and maybe we don't make it explicit enough, but it's consistent with how these data structures are typically implemented. A binary tree node stores nullable pointers to its two children, while an ordered tree node stores an ordered list of children, which usually doesn't include null children, since adding and deleting children is possible here. One could very well imagine an ordered tree based on dynamic arrays in which deletions are to be avoided, though, and instead children are set to null. You can still perform the same conversion in the presence of null nodes, but you end up with null internal nodes in the binary tree, which is bizarre. Maybe the whole claim should just be ripped out. :-) Deco 06:36, 16 February 2006 (UTC)

Merging articles about node types[edit]

I've redirected "child node" to this article, as it already had as good an explanation as the old child node article did, and a merge had already been proposed (although what was suggested was a merge to Node I felt here was better).

I've also proposed merges of Parent node and Root node, which also add little that isn't already in here. I haven't proposed a merge of Leaf node as that article actually contains useful amounts of information, including on a subject that is only tangentially related to this one. I don't want to do these merges unless other people agree with them, though.

Opinions? JulesH 20:06, 12 May 2006 (UTC)

I agree upon merging the Parent and Root node articles with this one. Make sure you make references to this page though. --Bernard François 15:03, 3 June 2006 (UTC)
I also agree, along with Internal node and Subtree MagiMaster 11:11, 10 July 2006 (UTC)
Also bringing in leaf node, nothing not covered in parse tree, graph theory tree, or here. Chris857 (talk) 02:54, 26 September 2011 (UTC)

levels, height, dimension, grade ...[edit]

I would like to see more information about this on the page. I was unsure if levels start counting from zero, so I checked this page (but I didn't find the answer). The height of a tree h would be the number of levels (but I'm not sure about that as well). --Bernard François 15:03, 3 June 2006 (UTC)

Hi...the root is given level 0, and then each generation has one level more than its predecessor. Also, the depth of tree is one more than the max level (i.e. level of the path having max nodes) (Schaum series coursebook) —Preceding unsigned comment added by Gopal1035 (talkcontribs) 10:50, 28 February 2009 (UTC)

Another term which is not explained on this page is the dimension of a tree, which I read about in the page about Exponential trees. Strangely, that article said something about nodes having different dimensions (then it would rather be the dimension of a node instead of the dimension of a tree). I added something on the talk page of that article...

In a Dutch coursebook I read about the grade of a node (it was about B-trees). I don't know if this exists in English, but it was the number of children a node has. This seems to be somehow to be similar to the dimension of a tree. --Bernard François 16:52, 3 June 2006 (UTC)

It's a mistranslation: degree is nl:graad in Dutch. Rp (talk) 18:05, 28 September 2009 (UTC)

Implementation[edit]

A binary tree should be implemented on this page in Java or C++. If no one else goes to it I may very well end up creating a sub-section with actual code segments.

Why? That would be suited to the WikiTextbook project Michael.Urban (talk) 14:19, 29 January 2008 (UTC)
I think it would be a good addition to the page--Nothing is free in this world (talk) 10:52, 28 February 2009 (UTC)
I agree with Michael that it's too much detail. Rp (talk) 18:06, 28 September 2009 (UTC)

Traversal[edit]

The discussion of tree traversals is under the heading for Forests, but individual trees are traversed in the manners listed. So, traversal should be a separate section. Michael.Urban (talk) 14:21, 29 January 2008 (UTC)

Q: Is there special traversion algorithms for non-binary trees?[edit]

Pre/in/postorder - they refer to binary trees. How about according algorithms for non-binary trees? —Preceding unsigned comment added by 84.136.209.135 (talk) 09:46, 31 January 2008 (UTC)

gsh —Preceding unsigned comment added by 124.106.25.36 (talk) 05:33, 27 December 2008 (UTC)

How are they specific to binary trees? Rp (talk) 10:51, 27 January 2010 (UTC)

Binary Trees As Ordered Trees[edit]

I am slightly concerned about the assertion that binary trees are necessarily ordered. The definition in the header says "at most two children" for every node, this does not imply an ordering. It's incorrect to say that one is "left" and the other "right" until you DRAW the tree, which is to say that every _embedded_ binary tree is ordered, but, then, _every_ embedded tree is ordered. So perhaps the distinction should be drawn between trees and embedded trees. —Preceding unsigned comment added by 137.111.240.148 (talk) 23:26, 7 September 2009 (UTC)

The point is that most uses of binary trees as data structures in algorithms essentially rely on the children being ordered. For instance, the heapsort algorithm becomes nonsensical if you can't speak of left and right children. It's not a property of diagrams of such trees, but of the structures themselves. Rp (talk) 10:56, 27 January 2010 (UTC)

Is a tree a tree?[edit]

The introduction sais that Mathematically, it is not a tree, but an arborescence, while the article arborescence tells us that an arborescence is a directed, rooted tree. I would conclude that a tree (data structure) is, even mathematically, a tree, even if it is a special kind of tree (directed, rooted tree). Maybe the introduction should be something like: The tree data structure is more specific than a mathematical tree, because it is a directed, rooted tree, which is called arborescence in mathematics. --Prauch (talk) 22:55, 26 January 2010 (UTC)

No, it is not, mathematically, a tree - follow that link! However I do agree that this should be formulated much more clearly and I don't know how. Rp (talk) 10:59, 27 January 2010 (UTC)
It really is a tree (in a graph-theory sense) as it's both cycle-less and connected. It being a more specific type of thing doesn't stop it being the general case of that thing. Anon - Today. —Preceding unsigned comment added by 137.222.235.35 (talk) 20:29, 27 May 2010 (UTC)
It is only connected if every node has a pointer to its parent, otherwise there might be two nodes such that no directed path exists from one node to the other one. So whether it is a tree in the mathematical sense depends on the implementation. – Adrianwn (talk) 05:40, 28 May 2010 (UTC)
Adrianwn, I disagree. First: Implementation technical details are irrelevent to which mathematical concept the data structure represents; for your example even if each node contains a pointer to its daughters (but not to its parent) it can still be connected to its parent such as by a method that searches down from the root and tracks to the node; in a high level language there is no reason for the programmer to even know which implementation is being used in every circumstance. Second: Mathematically, a rooted tree is characterised by directed links (naturally radiating not directionless), so strictly it is less appropriate if each node has an explicit pointer back to its parent. Cesiumfrog (talk) 11:02, 5 October 2010 (UTC)
It really depends on how you look at the edges on a semantic level: are they directed edges from parents to children, or are they undirected but have an implicit orientation?
  • In case the former is true: a mathematical tree is a connected, acyclic, undirected simple graph, so a tree data structure (which is a directed graph) is not a mathematical tree (because the set of directed and the set of undirected graphs are disjoint), and hence also not a rooted tree, because a rooted tree is a mathematical tree. A tree data structure is a directed tree, which, despite its name, is not a tree (because it is a directed graph, not an undirected one); note that not every directed tree is also a tree data structure.
  • In case the latter is true: then a tree data structure is in fact a mathematical tree (a rooted tree, to be more precise).
Remark: I used the definitions from Tree (graph theory).
So it actually depends on how you model the edges in a tree data structure. I seriously doubt that there exists a concensus in academic literature on whether they are directed or undirected (with an implicit orientation). In my opinion, it would be best to cite some sources for each of the two point of views, since, frankly, it really is a subjective choice. – Adrian Willenbücher (talk) 15:08, 5 October 2010 (UTC)

Tree description[edit]

Hello,

I think this is not quite right "where each node has zero or more children nodes and at most one parent node. Furthermore, the children of each node have a specific order." A tree can be "root"-ed by any node in an acyclic graph -- this is a computational problem, not a mathematical one. The root is simply the arbitrarily (mathematically speaking) chosen entry point for the tree. It can only be chosen once. The "at most one parent node" is a property of acyclic-ness. The statement about the children of each node having a specific order is again nothing to do with graph theory, and is usually referring to the layout of the graph during a traversal, and is more comptuationally concerned than anything else 129.67.86.189 (talk) 19:31, 6 March 2011 (UTC)

Right, and this page is concerned with computation. You want Tree (graph theory). --Cybercobra (talk) 20:48, 6 March 2011 (UTC)
But the sentence begins with "Mathematically, it is...."? I think its fine to have the computational aspect, but I think its not clear that this is not a mathematical consideration. (sorry, double negative) 129.67.86.189 (talk) 22:13, 6 March 2011 (UTC)
Of course it is a mathematical consideration: a tree with a fixed root is not, mathematically, a tree, but something else; and this is exactly why I wrote: "Mathematically, it is not a tree, but an arborescence". Later someone removed the not. Rp (talk) 16:47, 7 March 2011 (UTC)

Terminologies used in Trees[edit]

Missing something rather obvious, aren't we? It ain't much of a tree without children.

Also, an internal node sure looks a lot like a parent. 68.183.92.186 (talk) — Preceding undated comment added 20:49, 13 May 2014 (UTC)

...not any longer.
Is there any reason to separate the section "Terminologies used in Trees" from "Terminology", where the same notions are explained again? - Jochen Burghardt (talk) 13:05, 22 June 2014 (UTC)

Are children trees?[edit]

The article says "As a data type, a tree has a value and children, and the children are themselves trees". I thought the children of a node were nodes. Once upon a time this article said "where each node has zero or more children nodes and at most one parent node."

It would be really good if this article defined the concept of child. Maybe graph theorists use a different definition than computer scientists using trees as datatypes?

It would also be good to give a more precise definition of tree!!!

John Baez (talk) 10:43, 11 July 2014 (UTC)