Talk:Binary tree
From Wikipedia, the free encyclopedia
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)
Contents |
[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 
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.
