This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||
|
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/) ¼
-- Yes, they are the same. We should not be discussing traversal inside Binary tree but instead just point to the Tree traversal article. -- Ryuunoshounen ( talk) 18:39, 29 November 2013 (UTC)
There is nothing here on, "Strong Binary Trees", they are used in things like Astronomy for multiple star systems. http://mathworld.wolfram.com/StronglyBinaryTree.html —Preceding unsigned comment added by 91.51.125.15 ( talk) 19:20, 24 October 2008 (UTC)
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:
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)
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.
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
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)
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?
salte 14:12, 3 April 2007 (UTC)
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)
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)
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)
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)
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)
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
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)
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)
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)
Before you think me a crazy ranter, I have a Masters degree in the field and have taught data structures at the University of Virginia and done research in graph theory.
Now the non-crazy rant.
Please check this list and fix things. If you change your definition of height so that an empty tree has height 0, you will have to change your formulae for nodes-per-height.
No, I do not think you are crazy at all. Actually the article's main definition is wrong: "a binary tree is a tree data structure in which each node has at most two children". No! that does not get the main point of binary trees, where there is always a left and a right side, even if there is only a single child. Better: a binary tree is a hierarchical structure which is either empty, or consists of a node and two binary trees, called the left and right child of that node. If you do not believe me, read TACP by D. Knuth. Binary tree are not a special case of trees, they are a species of their own. Also the graph theoretical definition is not very much to the point: does it really capture the left/right issue? Jochgem ( talk) 12:13, 6 November 2009 (UTC)
As a practicing engineer, I find a few aspects of the article confusing. The biggest is the constant talk of rooted trees. What the heck is a non-rooted tree??? I have never heard of this and think that any attempt to look at a tree as a graph subset would be confusing, misleading, and most likely useless for understanding the basic data structure. Unless there is a meaningful concept of non-rooted trees that I somehow missed, that would make rooted binary trees a more obnoxious version of the classic "hot water heater" grammatical problem. Also, I think that at the very least, binary search trees should be included in the sub tree types. It and a few other types of trees are far more relevant than some of the ones listed now. —Preceding unsigned comment added by 67.183.113.131 ( talk) 03:39, 16 July 2010 (UTC)
Are we caring about advanced degrees? I have a PhD in computer science, and I strongly AGREE with OP that empty tree has height of zero. I further strongly agree that the main definition should be "A binary tree is either empty, or a node containing exactly two binary trees". Knuth is a good reference, so is How To Design Programs. What's the procedure for fixing this? Just go and make the change and then let people argue about it? This change will touch many parts of the page. Clements ( talk) 18:48, 14 April 2017 (UTC)
Self-edit: It's been pointed out to me that NIST disagrees with me, and specifies that Node(16,Null,Null) has height zero. I think this is a deeply unfortunate choice, as it reinforces the notion that Null is not a tree, but this definition is widely accepted, and much more clearly stated by the NIST [1] than it is by Knuth. Clements ( talk) 03:35, 11 May 2017 (UTC)
References
Types of binary trees .... A balanced binary tree is where the depth of all the leaves differs by at most 1. Balanced trees have a predictable depth ...
It shoukd be Balanced trees have a predictable height —Preceding unsigned comment added by 83.43.153.47 ( talk) 08:20, 29 November 2009 (UTC)
I'm Mdnahas, the author of "Many Things Wrong". I've split the article up into 3 articles, "Binary Tree", "Binary Tree (data structure)" and "Binary Tree (graph theory)". Cluebot seemed to dislike my change to Binary Tree, since it didn't realize the deletion of 15000 chars was actually a move of them into a different linked article.
Anyway, I undid the Cluebot revert. If anyone has power over Cluebot and agrees with my change, please help me fight it. (FYI, I know I'm a newbie here in how to edit these pages, but I'm an expert in the field.) —Preceding unsigned comment added by Mdnahas ( talk • contribs) 15:07, 31 December 2009 (UTC)
Isn't the classical graph, pictured here, incorrect on the Binary tree article?
The node labeled "2" (assumed to be a value of the node) has a greater value linked on the left, and a lesser value linked on the right.
However, the node labeled "7" has a lesser value (than 7) on the left, and a greater value on the right.
I looked up the Binary tree article to link from an article of mine on binary tree signatures which is proposing a project to detect randomness perturbed by determinant effects on randomness, as some algorithmically detectable deviation across multiple trees. (This paragraph is a shameless plug I suppose. Contact me if interested in a joint paper.)
Hopefully I'm not totally mistaken about the incorrect graphic, and do as you will with my scratches here... Regards -DonEMitchell (computer programmer)
This cant be right : # A balanced binary tree is where the depth of all the leaves differs by at most 1. Balanced trees have a predictable depth (how many nodes are traversed from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ..., depth). This depth is equal to the integer part of log2(n) where n is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). Example 3: balanced tree with 5 nodes, log2(5) = 2.32 (depth of tree is 2 nodes).
Here is counter example , n=7 , Node1 has left child Node2 and right child Node3 , Node2 has only one left child Node4, Node3 has left child Node5 and right child Node6 ,Node5 has only one left child Node7, so we have 7 nodes. This tree is balanced ,right ? Article suggests it should have log2(7)=2.807 , or 2 as it depth, but we can see that its depth is 3 . What gives ? —Preceding unsigned comment added by 68.46.189.142 ( talk) 04:40, 22 January 2010 (UTC)
A \ B \ C \ D \ E \ F \ G / \ H I / \ J K
0 / \ / \ / \ -1 -2 / \ \ / \ \ 0 0 1 / \ / 0 0 0
Notice the node labled with a negative 2. This demonstrates that this tree is not balanced by the recursive definition. — Preceding unsigned comment added by Pohl ( talk • contribs) 18:19, 19 December 2010 (UTC)
The article says "A (rooted) tree with only one node (the root) has a height of zero (or one[2]).", and similarly for the depth. Is this "or one" really correct? The linked external article doesn't mention neither depth nor height. Since I don't know this topic, I will not do the correction myself. -- HelgeStenstrom ( talk) 12:14, 1 November 2010 (UTC)
I propose that whatever is of value in Deletion in binary tree should be merged with this article. Malleus Fatuorum 17:05, 26 November 2010 (UTC)
I agree.
marksoe —Preceding
unsigned comment added by
150.156.195.42 (
talk) 23:53, 16 December 2010 (UTC)
I agree. The deletion page is incomplete, filled with spelling errors, and hard to follow. Chris857 ( talk) 22:33, 17 December 2010 (UTC)
The contents of the Deletion in binary tree page were merged into Binary tree. For the contribution history and old versions of the redirected page, please see its history; for the discussion at that location, see its talk page. |
Is it possible to delete a node from a binary tree that has two children? I know that its children can't just be assigned to its parent, because then the tree would be ternary. I've seen that it is possible with a binary search tree. [1] Chris857 ( talk) 04:13, 19 December 2010 (UTC)
I have been bold and removed a paragraph from Binary tree#Ahnentafel list. I'll paste it here: "A binary tree can also be represented in the form of array as well as adjacency linked list. In the case of array, each node(root,left,right) is simply placed in the index and there is no connection mentioned about the relationship between parents and children. However, in linked list representation we can find the relationship between parent and children. In array representation the nodes are accessed by calculating the index. This method is used in languages like FORTRAN which doesn't have dynamic memory allocation. We can't insert a new node into array implemented binary tree with ease, but this is easily done when using a binary tree implemented as linked list."
The reason for removal is that the information in it is already stated in the first paragraph and in a better way. If anyone disagrees, discuss. Silver hr ( talk) 21:33, 27 January 2011 (UTC)
So, i have a few questions.. if you please. 1.Who was the first to use binary trees? 2.why are binary trees are drawn from the top down.??
thanks in advance. —Preceding unsigned comment added by 85.65.108.106 ( talk) 10:47, 5 March 2011 (UTC)
LandruBek ( talk) 19:42, 28 June 2011 (UTC)
Shouldn't this article have one of those info boxes summarizing the time complexity of insert/remove/lookup operations?
See http://en.wikipedia.org/wiki/AVL_tree
Dj0nes ( talk) 17:19, 6 January 2012 (UTC)
This page has a mixture of content. Some is about the data structure and some is about the mathematical properties of that data structure. I believe a lot of the math should be split into a separate page and connected to graph theory. (FYI, I've both taught data structures and done research in graph theory.)
Apparently I tried this once upon a time, and it got rolled back. Checkout the change by mdnahas on 2009-12-30T22:24:21+00:00 — Preceding unsigned comment added by Mdnahas ( talk • contribs) 21:40, 15 February 2013 (UTC)
I am admittedly not the first one to notice this, but the definitions on this page are still seriously confusing, undeservedly for such a basic and simple notion as that of binary trees. I suggest reorganizing it by putting the binary-trees-as-inductive-type definition first (i.e., a binary tree is either the empty binary tree, or a pair of binary trees; a labelled binary tree is either the empty labelled binary tree, or a pair of labelled binary trees plus a label), with some examples and illustrations (a realization as bracketings for those unhappy with inductive definitions); and only then any relations with graph theory and data structures. The reason for this is that the inductive-type definition is the only one which can be taken at face value without additional clarifications or modifications:
It is perfectly fine for all these connections to be mentioned, but the definition should be simple and free from haze and ambiguities. -- Darij ( talk) 05:30, 27 March 2014 (UTC)
Darij ( talk) 21:33, 27 July 2014 (UTC)
“ | A tree (or rooted tree) T is a finite set of vertices such that:
a. One specially designated vertex is called the root of T , and b. The remaining vertices (excluding the root) are partitioned into m ≥ 0 disjoint nonempty sets T1, . . . ,Tm, each of which is a tree. The trees T1, . . . ,Tm are called subtrees of the root. |
” |
The definition seems to be that of a non-empty binary tree, so - if so - why not just say so? 68.183.92.186 ( talk) 21:51, 13 May 2014 (UTC)
It's actually a really confusingly written book, as far as binary trees are concerned. I'm not surprised that whoever used that as ref was unable to write a correct recursive definition of binary trees. Here's what the book has as def:
DEFINITION 4.1.1 A binary tree T consists of a set of nodes that is either empty or has the following properties:
It's hard to think of a more unclear way to say that. It's clear that whoever red that got confused into (recursively) defining binary tree as just full binary tree did so because he missed the empty set being binary tree, which is actually one of the recursion branches in the above def despite not being numbered, while the "1"-numbered clause there is just a red herring as far as the recursion is concerned. JMP EAX ( talk) 03:35, 26 July 2014 (UTC)
The obvious thing that's needed to make that formal is a partial mapping from left/right labels to outgoing edges from each node, but I wasn't able find a single source to say that explicitly. JMP EAX ( talk)
The def of "full" binary tree here doesn't match the common one in most textbooks, which define full as all leaves being on the same level. That section and the terminology throughout the article needs a fair bit of rework. JMP EAX ( talk) 03:18, 28 July 2014 (UTC)
If the goal of this article was to hide an essentially simple subject behind a cloud of confusing waffle then it has succeeded brilliantly. In my opinion the introductory paragraph beginning "from a graph theory perspective..." could be deleted entirely and it wouldn't subtract an iota from the useful content of the article. I mean, waffling on about the original meaning of terms I never even heard of in 30 years as a programmer... why? — Preceding unsigned comment added by 82.68.15.142 ( talk) 14:52, 12 September 2014 (UTC)
Thank you for your suggestion. When you believe an article needs improvement, please feel free to make those changes. Wikipedia is a
wiki, so anyone can edit almost any article by simply following the edit this page link at the top.
The Wikipedia community encourages you to
be bold in updating pages. Don't worry too much about making honest mistakes—they're likely to be found and corrected quickly. If you're not sure how editing works, check out
how to edit a page, or use the
sandbox to try out your editing skills.
New contributors are always welcome. You don't even need to
log in (although there are
many reasons why you might want to).
--
DavidCary (
talk) 03:34, 5 June 2015 (UTC)
I have to agree with the previous poster, this article is fairly typical of maths, engineering and technology/medicine articles in Wikipedia. Written by the "experts" for the "experts", with expert not meaning having communication skills in anyway. Binary trees are one of the simplest structures in the universe. How can this article be SO full of waffle that I am scratching my head with each line wondering what I must have missed. It neesds a serious clean up. Start simple, get more complex as you go on if necessary. The first paragraph shoudl not be maths shorthand. How does that help anybody? Communicate people! That is what an encyclopedia is for. Much appreciation to anybody who can clean this article up. It really needs it.
Thank you for your suggestion. When you believe an article needs improvement, please feel free to make those changes. Wikipedia is a
wiki, so anyone can edit almost any article by simply following the edit this page link at the top.
The Wikipedia community encourages you to
be bold in updating pages. Don't worry too much about making honest mistakes—they're likely to be found and corrected quickly. If you're not sure how editing works, check out
how to edit a page, or use the
sandbox to try out your editing skills.
New contributors are always welcome. You don't even need to
log in (although there are
many reasons why you might want to).
--
DavidCary (
talk) 03:34, 5 June 2015 (UTC)
In Binary_tree#Types_of_binary_trees "Physicists define a binary tree to mean a full binary tree." The source isn't web so I can't check. Is this a typo? I'm not a physicist but I can't imagine what physicists would use the concept of a binary tree for, and physics/physicists aren't mentioned anywhere else in the article. -- Padenton ( talk) 16:55, 10 March 2015 (UTC)
I removed the following sentences from the lead because they addressed a subtlety that is already addressed in the section on defining a binary tree "Using graph theory concepts". The original is preserved here in case someone wants to revert this deletion. If you do the revert, can you also please clean up the English in the mentions of k-ary trees?
-- DavidHolmes0 ( talk) 16:23, 2 July 2015 (UTC)
References
Hello fellow Wikipedians,
I have just modified one external link on Binary tree. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{
Sourcecheck}}
).
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 18 January 2022).
Cheers.— InternetArchiveBot ( Report bug) 19:38, 2 November 2016 (UTC)
Both in mathematics and in programming there are situations when empty structures or collections are considered: empty set (both in math. set theory and in programming), empty list (a sequence with no terms), empty string, empty file etc. There is sometimes also a reason to consider empty trees.
However, the recursive definition of a full tree in
Binary tree#Types of binary trees starts from a single node as a base case, which does not allow for an empty tree, whilst the primary definition does (“a tree in which every node has either 0 or 2 children” is
vacuously true for an empty set of nodes). Should we add an explicit case of an empty tree there? --
CiaPan (
talk) 12:45, 7 March 2019 (UTC)
This would be a salient question I reckon. Maybe should have its own section. — Preceding unsigned comment added by 85.76.151.104 ( talk) 13:20, 3 May 2022 (UTC)
Is there a name for algorithms and trees that maintain balancing property, but are not search trees (i.e. order of nodes do not matter), but tree is used for some aggregation of subtrees instead. (i.e. max value). These have interesting applications, but because they do not need to be ordered, might have way easier balancing strategies than BST. 81.6.34.169 ( talk) 23:00, 14 April 2024 (UTC)