Talk:Tree (data structure)

From Wikipedia, the free encyclopedia

It seems better to define odered tree as tree with odered arrows outgoing from every node - not childs - as it gives possibility to define odered 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 alleiviate 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)

Contents

[edit] 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)

[edit] Binary Expression Trees

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

[edit] 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)

[edit] 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)

[edit] 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)

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)

[edit] 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)

[edit] 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)

[edit] 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)