Talk:Binary tree

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B rated as B-Class on the assessment scale
Top rated as top-importance on the assessment scale


Contents

[edit] level vs breadth first

Isn't level and breadth search the same? (http://tekpool.wordpress.com/2006/11/04/binary-tree-traversal-breadth-first-aka-width-first-aka-level-order/) ¼

[edit] tree

Under "types" of binary trees, I think it would be appropriate to add "extended binary tree" (http://mathworld.wolfram.com/ExtendedBinaryTree.html) --Hughitt1 02:31, 4 April 2006 (UTC)

let T be binary tree with height h and n nodes show that log(n+1)-1<=h<=(n-1)/2 for which values of n and h can be above lower upper bounds of h be attained equally

The article says:

Graph theorists use the following definition. A binary tree is a connected acyclic graph such that the degree of each vertex is no more than 3.

This appears to be incorrect. Consider the graph with four vertices A, B, C, and X, where X is attached to A, B, and C. This is a connected acyclic graph where every vertex has degree no more than 3, but it is not a binary tree.

I believe that the definition of a binary tree in graph-theoretic terms will require that the graph be a directed acyclic graph. Then we might require that every node have outdegree at most 2, that the root node have indegree 0, and that every other node have indegree 1.

Dominus 14:40, 17 Feb 2004 (UTC)

I think the current definition is actually correct. A binary tree does not require each node to have either zero or two children, so simply choose some node with degree <= 2 as the root (which must exist; in fact we must have a vertex of degree 1) and then assign all adjacent nodes not yet assigned as its children. Repeat this for each new node added, and you establish all parent-child relationships. The directed interpretation is convenient, but less general, because it fixes the root. This might deserve mention in the article.

As for X,A,B,C, you can follow the above procedure, assigning A as the root, X as its unique child, and B,C as the children of X.

Derrick Coetzee 04:26, 18 Feb 2004 (UTC)


Perhaps, but I don't think anyone ever does define it that way. You could also define a binary tree geometrically, in terms of line segments in the cartesian plane, but nobody does that either. Is there a source for this definition? Or is it just the product of some wikipedian's imagination? Dominus 16:34, 18 Feb 2004 (UTC)
In a few books I have handy, binary trees are defined with respect to a particular root node. One defines it as either being empty or being partitioned into a root node, a left subtree, and a right subtree. Another defines it as a rooted tree where each node has at most two children, where a rooted tree is defined by the procedure I gave above. I imagine some source might use the definition in the article, but you're right that in general most people think of a binary tree as having a specific root and a specific order on children.
Derrick Coetzee 15:20, 20 Feb 2004 (UTC)

I also don't see the point of defining a binary tree as an undirected graph, since you're going to have to infer directions on it anyway.

Also, a question: can a binary tree have a right child and no left child? I came to this article to look that up, and the article doesn't make it clear.

RSpeer 22:27, Mar 12, 2005 (UTC)

I have seen this definition used in graph theory books. I can get a real reference. The only other definition I've seen is a recursive one: a binary tree is either a vertex or a vertex with two edges going out to binary trees. I'll throw this in. Deco 23:51, 12 Mar 2005 (UTC)

A node can have zero, one (either side), or two children. Also, the definition about no node having degree greater than three is correct, as long as one restriction is placed: the number of nodes with degree three is exactly two less than the number of nodes of degree three. Lastly, binary trees are not ordered; binary search trees are. I corrected the article on that point.

Dominus, your counterexample does not prove anything; choose any node except X as root, and no conflict exists.

You may be misunderstanding the meaning of "ordered" in this context. This simply means that there are distinguishable left and right children, not that the elements are ordered. Binary trees need not be ordered trees, I suppose, but in nearly all implementations a left-right child order is naturally imposed, largely because unordered lists (sets) aren't a common language feature. There are of course many applications where this order is irrelevent, like binary heaps. Deco 07:09, 7 May 2005 (UTC)

[edit] duplicates

As far as I know, duplicates are allowed in binary trees. Should this be added to the article, or is it even relevant? Meonkeys 18:47, May 16, 2005 (UTC)

RSPeer: yes, a binary tree can have a right child and no left child. Node "5" in Image:Binary_tree.png has a right child and no left child. Meonkeys

Hmm, duplicates allowed. That would be good to mention - really I should have had duplicates in the diagram. I'll fix this sometime. Please be bold. Deco 08:50, 19 May 2005 (UTC)

[edit] Counting binary trees

Should we also include the formula for counting binary trees somewhere? This is used when you want to do stastical analysis of insertion and deletion of nodes in the tree.

Somehow I think the formula k = \frac1{2n+1}{2n+1 \choose n} should be mentioned somewhere. Preferably with a reference to where the formula is derived. In the formula, k is the number of trees that has exactly n nodes. So for example there are 5 binary trees with 3 nodes. This is also related to the fact that you can write three parenthesis in 5 different ways on a line: ((())), (()()), (())(), ()(()), ()()().

Of course, imposing further structure on the tree (Red black trees, AVL trees etc) would also influence the likelyhood of a given tree appearing and prohibit some. Speaking of variants, we should perhaps add a little reference to red black trees, avl trees and n-ary trees (binary trees is a special case where n=2), as well as many other trees that are used as ways of structuring data.

salte 12:54, 14 December 2006 (UTC)

[edit] Examples

The article so far seems to be only a discussion of implementation methods and operating rules. I have noticed no mention of advantages/disadvantages of using binary trees over more conventional programming structures. Also, can someone provide some real world applications where a binary tree could be used to solve a problem more easily or efficiently than other methods?

  • Binary trees are superior to for example linked lists to hold a collection of items. Also, because they are binary you generally have few tests before determining where to go after visiting a given node. For example if you visit a node A and you have determined that this is not the node you are looking for, you also often typically know if you should check the left or the right branch after when searching for a node. Looking through a set of n nodes will take an order of O(log(n)) time while in a linked list it is of the order O(n) and as log(n) < n (base is larger than 1) and for large n the difference is large you can gain much speed. For example I once had a program that used a linked list and it took a long time to run, I then aborted it after an hour when it was still not done, rewrote to use a binary tree and the program took 8 minutes to run before it completed. For example in C if you use strcmp(skey,nkey) to compare the search key with the node key you first check if the return value was 0 - if it was 0 it means the keys were equal and you have found the node, if the return value was negative it means the node key was later in the sort and so you check out the left branch. Thus, all the nodes on the right branch are already known to be too large and can be skipped in the search. If the return value was positive you know you can skip the left branch and only check the right branch for the same reason.

salte 14:12, 3 April 2007 (UTC)

[edit] the degree of a node in a rooted tree

the degree of a node in a rooted tree is the number of children - the edge from its parent node does not count. Charieshane 04:00, 7 March 2007 (UTC)

It sounds like you're talking about the out-degree (considering the tree to be a directed graph). Your definition would be inconsistent with the definition of degree for graphs in general.

Now, in applied contexts like computer science, the out-degree is the useful measure, and it can be referred to as just the "degree". But I think the only place the degree is mentioned in the article is the formal graph theory definition, so it should stay consistent with graph theory.

rspeer / ɹəədsɹ 08:19, 7 March 2007 (UTC)

[edit] car, cdr, and lots of parens?

Could this article be amended to mention that trees may be encoded as strings, by using parenthesis? In mathematics, binary trees are known as free magmas, and the encoding as a string is important for algebra e.g. for free objects, and also for the foundations of syntax. The string encoding is also used by lisp (programming language), scheme (programming language) and prolog. Should also mention that the standard names for navigating a binary tree are CAR and CDR. Also, the encoding at the bottom of the article is wrong; the internal node labels (cons) were left out.linas 02:37, 9 April 2007 (UTC)

[edit] Encoding n-ary trees as binary trees

The diagram in this section is confusing because there are two distinct nodes labeled "G". Muddle-headed Wombat 18:04, 9 April 2007 (UTC)


The Line between M and N should be blue 77.56.110.121 (talk) 15:57, 26 March 2008 (UTC)

[edit] Nodes/Vertices

Is there a difference between the node of a graph and the vertices of a graph? If not, wouldn't it be better to use just a single word throughout the article? Taemyr 19:49, 12 May 2007 (UTC)

[edit] special cases of depth-first traversal

I think there is something wrong to say Pre-order, in-order, and post-order traversal are all special cases of this(depth-first traversal)

In-order and post-order traversals visit child nodes before visiting their parents, which breaks the caveat that it must be a child of a node we have already visited. --71.159.61.221 03:00, 28 June 2007 (UTC)

[edit] Lisp-style structures are not binary trees

A lisp-style node can point to left and right nodes, but if it does then the node cannot store a value. This makes it fundamentally different to a binary tree (assuming a binary tree node must be able to store a value). If so, then should the "encoding n-ary trees" section be moved/removed?

Also, the "combinatorics" section mentions "car" and "cdr" and talks about trees as (a b) where a and b are subtrees but not, say, (a x b) where x is the node value. --2007-07-20

Actually cons-based data structures are binary trees, but they can only store data in leaves. Conventionally they almost always store data in each cons's left child and sublists in each cons's right child (which makes the tree a degenerate list). You can represent arbitrary trees as well: for example, using dotted cons notation, (((1 . 2) . 3) . (4 . 5)) could be a valid binary tree storing some numbers. This is somewhat uncommon but is used. Dcoetzee 08:20, 21 July 2007 (UTC)

[edit] Graph

This is not true at all. Duplicates were included to illustrate that a general labelled binary tree can include duplicate labels, and they were placed out of order to illustrate that generally they don't require order. Dcoetzee 19:45, 10 August 2007 (UTC)

[edit] Definition in graph theory: glitch?

The current definition,

Another way of defining binary trees is a recursive definition on directed graphs. A binary tree is either:

  • A single vertex.
  • A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree.

makes the tree

  A
 /
B

an invalid binary tree, as it cannot be formed by combining two smaller binary trees. Does anyone have a more correct definition than this? Zetawoof(ζ) 00:01, 17 September 2007 (UTC)

The definition depends on whether or not you consider the leaves to contain values, or whether they're "null" leaves. The current definition is correct in the latter case, while to permit the definition you'd need something more complicated that's difficult to describe with a recursive definition. I prefer the more structural definition that it's just a directed acyclic graph of maximum degree 3. Dcoetzee 02:43, 17 September 2007 (UTC)

[edit] Heaps?

Maybe we should mention that a complete binary tree is often referred to as a heap in computer science. This seems relevant to me as the opening statement refers to computer science. Though somewhat irrelevant it might also be useful to mention that complete trees can be implemented using an array as opposed to a linked structure which is mentioned in the other sections. Only in the array implementation a parent n can reach it's children at with something like left = 2n + 1 and right = 2n + 2, assuming a 0 indexed array. —Preceding unsigned comment added by Cldoyle (talk • contribs) 02:04, 12 January 2008 (UTC)

Binary heaps are mentioned (and linked) in the introduction. Do note that a complete binary tree is not the same thing as a heap! The binary tree property (left < parent < right) is quite different from the heap property (parent < child). Zetawoof(ζ) 06:28, 12 January 2008 (UTC)
I completely agree with you,Zetawoof! Visame (talk) 17:35, 18 May 2008 (UTC)

[edit] Repeated Definitions

There are two definitions for almost complete binary trees which pretty much state the same thing. Should these be merged or should one be deleted? I think the lower one more clearly represents an almost complete binary tree. —Preceding unsigned comment added by 99.225.178.225 (talk) 14:22, 14 April 2008 (UTC)