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

单词

Red-Black Tree

释义

Red-Black Tree

An extended Binary Tree satisfying the following conditions:

: 1. Every node has two Children, each colored either red or black.
: 2. Every Leaf node is colored black.
: 3. Every red node has both of its Children colored black.
: 4. Every path from the Root to a Leaf contains the same number (the ``black-height'') of black nodes.

Let

be the number of internal nodes of a red-black tree. Then the number of red-black trees for

, 2, ... is 2,2, 3, 8, 14, 20, 35, 64, 122, ... (Sloane's A001131). The number of trees with black roots and red roots are given bySloane's A001137 and Sloane's A001138, respectively.

Let be the Generating Function for the number of red-black trees of black-height indexed by the number ofLeaves. Then

(1)

where

. If

is the Generating Function for the number of red-black trees, then

(2)

(Ruskey). Let

be the number of red-black trees with

Leaves,

the number ofred-rooted trees, and

the number of black-rooted trees. All three of the quantities satisfy the RecurrenceRelation

(3)

where

is a Binomial Coefficient,

for

, and

for

(Ruskey).

See also B-Tree

References

Beyer, R. ``Symmetric Binary -Trees: Data Structures and Maintenance Algorithms.'' Acta Informat. 1, 290-306, 1972.

Rivest, R. L.; Leiserson, C. E.; and Cormen, R. H. Introduction to Algorithms. New York: McGraw-Hill, 1990.

Ruskey, F. ``Information on Red-Black Trees.'' http://sue.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.

Sloane, N. J. A. Sequences A001131,A001137, andA001138in ``An On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html.

随便看

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