“Binary Tree”的概念、定义、习题解题方法及翻译-数学辞典

单词

Binary Tree

释义

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

Partial balancing of an arbitrary tree into a so-called AVL binary search tree can improve search speed.

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.

See also B-Tree, Quadtree, Quaternary Tree,Red-Black Tree, Stern-Brocot Tree, Weakly Binary Tree

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.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。