Binary Tree

A Tree with two Branches at each Fork and with one or two Leaves at theend of each Branch. (This definition corresponds to what is sometimes known as an ``extended'' binary tree.)The height of a binary tree is the number of levels within the Tree. For a binary tree of height with nodes,

These extremes correspond to a balanced tree (each node except the Leaves has a left and rightChild, and all Leaves are at the same level) and a degenerate tree (each node has only one outgoingBranch), respectively. For a search of data organized into a binary tree, the number of search steps neededto find an item is bounded by

The number of binary trees with internal nodes is the Catalan Number (Sloane's A000108), and thenumber of binary trees of height is given by Sloane's A001699.

References

Lucas, J.; Roelants van Baronaigien, D.; and Ruskey, F. ``Generating Binary Trees by Rotations.'' J. Algorithms 15, 343-366, 1993.

Ranum, D. L. ``On Some Applications of Fibonacci Numbers.'' Amer. Math. Monthly 102, 640-645, 1995.

Ruskey, F. ``Information on Binary Trees.'' http://sue.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html.

Ruskey, F. and Proskurowski, A. ``Generating Binary Trees by Transpositions.'' J. Algorithms 11, 68-84, 1990.

Sloane, N. J. A. SequencesA000108/M1459and A001699/M3087in ``An On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

• Divided Difference
• Divine Proportion
• Divisibility Tests
• Divisible
• Division
• Division Algebra
• Division Lemma
• Division Ring
• Divisor
• Divisor Function
• Divisor Theory
• Dixon-Ferrar Formula
• Dixon's Factorization Method
• Dixon's Random Squares Factorization Method
• Dixon's Theorem
• D-Number
• Dobinski's Formula
• Dodecadodecahedron
• Dodecagon
• Dodecagram
• Dodecahedral Conjecture
• Dodecahedral Graph
• Dodecahedral Space
• Dodecahedron
• Dodecahedron 2-Compound