Talk:Tree (abstract data type)/Archive 1

Archive 1

Article title

Shouldn't this page be at Tree (data structure)? -- Timwi 18:33, 21 January 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 April 2004 (UTC)

Range tree?

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

I think someone with more time should consider adding this subject here or create a page for it. — Preceding unsigned comment added by MasterT~enwiki (talk • contribs) 05:16, 3 February 2006 (UTC)

Definition

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)

One-to-one mapping

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)

Traversal

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)

levels, height, dimension, grade ...

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 (talk • contribs) 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

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)

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

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

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?

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

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)

Merging articles about node types

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)

Are children trees?

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)

Undefined definition

This is a typical computer-scientist definition: "A tree is a (possibly non-linear) data structure made up of nodes or vertices and edges without having any cycle." But none of these words (non-linear? data structure? node? vertex? edge? cycle??) is defined (earlier or through a link). This leaves much space for imagination... We can well imagine what is meant by most of these, but in particular the most crucial word "cycle" (which distinguishes the tree from other possibly non-linear data structure made up of nodes and edges, whatever this means) should be clearly defined. What's the use of adding "possibly non-linear" if nothing else is precisely defined? — MFH:Talk 20:32, 21 January 2016 (UTC)

Terminologies used in Trees

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)

Why define a child as 'The converse notion of a parent' rather than giving the actual definition? (i.e; 'A node directly connected to another node when moving toward the Root').Ryankrage77 (talk) 14:21, 24 May 2017 (UTC)

Mathematical definitions section should not appear in a CS article

As the introduction states, a tree data structure can be defined using recursion (collection of nodes), or using graph theory (directed rooted tree). Having other definitions, remotely related to the CS field, is just confusing, so I think "partial algebra" and other mathematical definitions do not belong here and should be presented in other articles.

--Basbodart (talk) 20:32, 12 September 2018 (UTC)

Merge 'Terminology used in trees' and 'Terminology' sections

Merge sections Terminology used in trees and Terminology.

Perhaps the first one makes a good Terminology summary, while the latter is a good format for Terminology details.

Dpleibovitz (talk) 22:19, 22 September 2018 (UTC)

Ordered tree: Inappropriate edit of the first paragraph

In the 893347119 revision, the following two sentences were added to the Ordered tree subsection.

In search trees the order is commonly established by the "key" or value associated with each sibling, but in many trees that is not the case. For example, XML documents, lists within JSON files, and many other structures have order that does not depend on the values in the nodes, but is itself data -- sorting the paragraphs of a novel alphabetically would lose information.

These sentences are too sloppy to be included in a Mathematical definition section. Perhaps the intended purpose is to say that in search trees, there is a correspondence between the total order of search keys associated with nodes and the total order of nodes (which is further denoted by ≤_L⁺ or ≤_L⁻). In other structures like the DOM tree, there is no such correspondence.

The most problematic term is "lists within JSON files". This is best to be removed. Otherwise, it should be explained first, how the terms "JSON" and "Ordered tree" are related. For instance, there is no mention of "tree" in the current version of the JSON page (except for one occurence in the See also section). Perhaps what is meant by "lists within JSON" is that data structures expressible by the JSON format can be seen as ordered tree structures whenever the structures do not contain the object type – which is explicitly defined as unordered collection. That is, from the only two "non-atomic" data types, array and object, only the former one is allowed. (Recall that the six primitive types are null, boolean, string, number, array and object - see the draft.)

In general, a text that would qualify for the Mathematical definition section should be more elaborated / careful than is the case of the discussed sentences.

Hundblue (talk) 18:40, 21 April 2019 (UTC)

Serializations

Shouldn't tree structure representations like JSON and XML be mentioned? --MAF-Soft (talk) 10:24, 16 February 2018 (UTC)

@MAF-Soft: I know that XML always has a tree structure, but, as I understand it, that is not also true of JSON. The first sentence of the Wikipedia article on JSON associates it with "data objects consisting of attribute–value pairs and array data types (or any other serializable value)", and XML § Criticism says: "Mapping the basic tree model of XML to type systems of programming languages or databases can be difficult, especially when XML is used for exchanging highly structured data between applications, which was not its primary design goal", and for that reason alternatives such as JSON are preferable for the relevant data types. In other words, JSON's primary purpose is representing these data types (which are not necessarily tree structures), and XML's primary purpose is representing documents in a tree structure (but it can also be used to represent the data types that are typically represented in JSON). I could be wrong, but that is my current understanding. I don't think it is necessary to explain all that in this article. Biogeographist (talk) 15:05, 16 February 2018 (UTC)

I think you are wrong indeed; or, at the least, confused.

• JSON has every bit as much of a tree structure as XML. Both data serialization formats use bracketing ({ and } in JSON, and opening and closing tags in XML) and hence, JSON and XML documents represent trees.
• At first sight, JSON does seem a more natural choice than XML for representing data structures: it literally is JavaScript data structures denoted in JavaScript. However, JSON is only a subset of JavaScript's syntax for data structures and it cannot denote all types of JavaScript data (see JSON#Unsupported_native_data_types), let alone all data structures in other languages. Besides, it can be argued that for typed data, when you want to annotate the data with its type, XML is a better fit.
• Neither JSON nor XML can express data types. For instance, there is no way to say in JSON or XML: the value I'm writing down here is an integer, or a floating point number. XML has standards for describing data structure types (DTDs and XML Schema), but these have ridiculous limitations in expressive power. Many perfectly reasonable document structure types cannot be described in DTDs or XML Schemas at all. Also, there is no way to express the difference between, for instance, an ordered list, an unordered list and a set.
• For JSON, there is JSON Schema (see JSON#JSON_Schema), which I haven't studied; I'm sure it is a lot saner and more expressive than XML Schema, but it's only a draft and I don't know how widely it has been adopted.
• Neither JSON nor XML can represent arbitrary data structures without a mechanism to express object references. Such a mechanism was always present in XML (ID and IDREF) and another is present in XML Schema (key and keyref). No such mechanism is in JSON, although a draft standard for one exists (see JSON#Object_references).

Rp (talk) 15:30, 18 March 2018 (UTC)

@Rp: I've never used JSON, so you may be correct. I don't see anything incorrect in what you've written, so I've struck the section of my comment that was "wrong indeed; or, at the least, confused" (to borrow your phrase). Your response doesn't answer MAF-Soft's original question though: should JSON and XML be mentioned in the article? Thanks, Biogeographist (talk) 15:54, 18 March 2018 (UTC)

I'm not sure how. It might be mentioned that many document formats and serialization formats such as HTML, XML and JSON are based on trees, owing to trees being serializable without the introduction of a reference mechanism, but I'm not sure what to write on this that is strictly about trees and that doesn't degenerate into original research. Rp (talk) 22:23, 18 March 2018 (UTC)

I added mention of XML, HTML, DOM, JSON, and YAML in the "Common uses" section. -- Beland (talk) 16:16, 10 August 2020 (UTC)

Depth vs. Level

In the list of definitions, these two definitions appear:

Depth

The distance between a node and the root.

Level

1 + the number of edges between a node and the root, i.e. (Depth + 1)

However, in researching a source for this definition, I have found several books and articles that say that depth and level are the same, and only one article (which cites this very wiki page) that claims level and depth are different. Is this actually a disputed definition, or did somebody just make a mistake somewhere along the way which led to an erroneous definition for "level"? --ΨΦorg (talk) 01:11, 5 May 2020 (UTC)

I agree, source is equivalent to level, however they are defined somewhat differently. Depth is the distance between the node and the root while level is the set of all nodes with the same depth, and the level of a node is the name of the set that contains it.

Markt1331 (talk) 14:09, 13 August 2020 (UTC)