Namespaces
Variants
Actions

Difference between revisions of "Binary tree"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link oeis)
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
A (planar) rooted tree for which every node has a left child, a right child, neither, or both. Three examples are:
+
{{TEX|done}}{{MSC|05C05}}
  
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/b110530a.gif" />
+
A (planar) [[rooted tree]] for which every node has a left child, a right child, neither, or both. Three examples are:
  
Figure: b110530a
+
<gallery>
 +
File:Binary tree 1.svg
 +
File:Binary tree 2.svg
 +
File:Binary tree 3.svg
 +
</gallery>
  
 
These three are all different.
 
These three are all different.
  
The number of binary trees with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105301.png" /> nodes, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105302.png" /> left children, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105303.png" /> right children (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105304.png" />) is
+
The number of binary trees with $n$ nodes, $p$ left children, $q$ right children ($p+q=n-1$) is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105305.png" /></td> </tr></table>
+
$$\frac{1}{n}\binom{n}{p}\binom{n}{p+1} = \frac{1}{n}\binom{n}{p}\binom{n}{q}.$$
  
The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105306.png" /> are called Runyon numbers or Narayama numbers.
+
The numbers $\frac{1}{n}\binom{n}{p}\binom{n}{p+1}$ are called Runyon numbers or Narayana numbers ({{OEIS|A001263}}).
  
A complete binary tree is one in which every node has both left and right children or is a leaf (i.e., has no children). E.g., there are two complete binary trees with five nodes:
+
A complete binary tree is one in which every node has both left and right children or is a leaf (''i.e.'', has no children). ''E.g.'', there are two complete binary trees with five nodes:
  
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/b110530b.gif" />
+
<gallery>
 +
File:Complete binary tree left.svg
 +
File:Complete binary tree right.svg
 +
</gallery>
  
Figure: b110530b
+
A complete binary tree has an odd number of nodes, say $2k+1$, and then the number of leaves is $k+1$. Label the $k+1$ leaves from left to right with symbols $x_1,\dotsc,x_{k+1}$. Then the various complete binary trees with their $k+1$ leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word $x_1\cdots x_{k+1}$, each way corresponding to a computation of the product by successive multiplications of precisely two factors each time. The number of ways of doing this, and hence the number of binary trees with $k+1$ nodes, is the Catalan number
  
A complete binary tree has an odd number of nodes, say <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105307.png" />, and then the number of leaves is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105308.png" />. Label the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b1105309.png" /> leaves from left to right with symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053010.png" />. Then the various complete binary trees with their <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053011.png" /> leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053012.png" />, each way corresponding to a computation of the product by successive multiplications of precisely two factors each time. The number of ways of doing this, and hence the number of binary trees with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053013.png" /> nodes, is the Catalan number
+
$$\frac{1}{k+1}\binom{2k}{k},k=1,2,\dotsc$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053014.png" /></td> </tr></table>
+
which is {{OEIS|A000108}}.
  
The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 [[#References|[a1]]].
+
The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 {{Cite|a1}}.
  
The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053015.png" /> and the [[Free magma|free magma]] on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110530/b11053016.png" />.
+
The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set $X$ and the [[Free magma|free magma]] on $X$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Catalan,  "Note sur une équation aux différences finies"  ''J. Math. Pures Appl.'' , '''3'''  (1838)  pp. 508–516</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Comtet,  "Advanced combinatorics" , Reidel  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I.M. Gessel,  R.P. Stanley,  "Algebraic enumeration"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovacz (ed.) , ''Handbook of Combinatorics'' , '''II''' , Elsevier  (1995)  pp. 1021–1062</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.P. Stanley,  "Enumerative combinatorics" , Wadsworth and Brooks/Cole  (1986)</TD></TR></table>
+
* {{Ref|a1}} E. Catalan,  "Note sur une équation aux différences finies"  ''J. Math. Pures Appl.'' , '''3'''  (1838)  pp. 508–516
 +
* {{Ref|a2}} L. Comtet,  "Advanced combinatorics" , Reidel  (1974) {{ZBL|0283.05001}}
 +
* {{Ref|a3}} I.M. Gessel,  R.P. Stanley,  "Algebraic enumeration"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovacz (ed.) , ''Handbook of Combinatorics'' , '''II''' , Elsevier  (1995)  pp. 1021–1062
 +
* {{Ref|a4}} R.P. Stanley,  "Enumerative combinatorics" , Wadsworth and Brooks/Cole  (1986)

Latest revision as of 08:31, 12 November 2023

2020 Mathematics Subject Classification: Primary: 05C05 [MSN][ZBL]

A (planar) rooted tree for which every node has a left child, a right child, neither, or both. Three examples are:

These three are all different.

The number of binary trees with $n$ nodes, $p$ left children, $q$ right children ($p+q=n-1$) is

$$\frac{1}{n}\binom{n}{p}\binom{n}{p+1} = \frac{1}{n}\binom{n}{p}\binom{n}{q}.$$

The numbers $\frac{1}{n}\binom{n}{p}\binom{n}{p+1}$ are called Runyon numbers or Narayana numbers (OEIS sequence A001263).

A complete binary tree is one in which every node has both left and right children or is a leaf (i.e., has no children). E.g., there are two complete binary trees with five nodes:

A complete binary tree has an odd number of nodes, say $2k+1$, and then the number of leaves is $k+1$. Label the $k+1$ leaves from left to right with symbols $x_1,\dotsc,x_{k+1}$. Then the various complete binary trees with their $k+1$ leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word $x_1\cdots x_{k+1}$, each way corresponding to a computation of the product by successive multiplications of precisely two factors each time. The number of ways of doing this, and hence the number of binary trees with $k+1$ nodes, is the Catalan number

$$\frac{1}{k+1}\binom{2k}{k},k=1,2,\dotsc$$

which is OEIS sequence A000108.

The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 [a1].

The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set $X$ and the free magma on $X$.

References

  • [a1] E. Catalan, "Note sur une équation aux différences finies" J. Math. Pures Appl. , 3 (1838) pp. 508–516
  • [a2] L. Comtet, "Advanced combinatorics" , Reidel (1974) Zbl 0283.05001
  • [a3] I.M. Gessel, R.P. Stanley, "Algebraic enumeration" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovacz (ed.) , Handbook of Combinatorics , II , Elsevier (1995) pp. 1021–1062
  • [a4] R.P. Stanley, "Enumerative combinatorics" , Wadsworth and Brooks/Cole (1986)
How to Cite This Entry:
Binary tree. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Binary_tree&oldid=18931
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article