主题
Search

红黑树

RedBlackTree

一个扩展的有根二叉树，满足以下条件

1. 每个节点都有两个子节点，每个节点都被着色为红色或黑色。

2. 每个树叶节点都被着色为黑色。

3. 每个红色节点的两个子节点都被着色为黑色。

4. 从根到树叶的每条路径都包含相同数量（“黑高度”）的黑色节点。

设 n 为红黑树的内部节点数。那么，对于 n=1, 2, ... 红黑树的数量分别是 2, 2, 3, 8, 14, 20, 35, 64, 122, ... (OEIS A001131)。根节点为黑色和红色的树的数量分别由 OEIS A001137 和 OEIS A001138 给出。

设 T_h 为黑高度为 h 的红黑树的生成函数，其索引为树叶的数量。则

T_(h+1)(x)=[T_h(x)]^2+[T_h(x)]^4,
(1)

其中 T_1(x)=x+x^2。如果 T(x) 是红黑树数量的生成函数，则

T(x)=x+x^2+T(x^2(1+x)^2)
(2)

（Ruskey）。设 rb(n) 为有 n 个树叶的红黑树的数量，r(n) 为根节点为红色的树的数量，以及 b(n) 为根节点为黑色的树的数量。这三个量都满足以下递推关系

R(n)=sum_(n/4<=n<=n/2)(2m; n-2m)R(m),
(3)

其中 (n; k) 是一个二项式系数，rb(1)=1，rb(2)=2 对于 R(n)=rb(n)，r(1)=r(3)=0，r(2)=1 对于 R(n)=r(n)，以及 b(1)=1 对于 R(n)=b(n)（Ruskey）。

另请参阅

B树, 有根树

使用 Wolfram|Alpha 探索

参考文献

Bayer, R. "对称二叉B树：数据结构和维护算法。" Acta Informat. 1, 290-306, 1972.Binstock, A.; and Rex, J. 程序员实用算法。 Reading, MA: Addison-Wesley, 1995.Cormen, T.; Leiserson, C.; and Rivest, R. 算法导论。 Cambridge MA: MIT Press, 1990.Guibas, L. and Sedgewick, R. "平衡树的二色框架。" In Proc. 19th IEEE Symp. Foundations of Computer Science, pp. 8-21, 1978.Rivest, R. L.; Leiserson, C. E.; and Cormen, R. H. 算法导论。 New York: McGraw-Hill, 1990.Ruskey, F. "关于红黑树的信息。" http://www.theory.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.Skiena, S. S. 算法设计手册。 New York: Springer-Verlag, pp. 177 and 179, 1997.Sloane, N. J. A. 整数序列在线百科全书"中的序列 A001131、A001137 和 A001138。Wood, D. 数据结构、算法与性能。 Reading, MA: Addison-Wesley, 1993.

在 Wolfram|Alpha 中被引用

红黑树

请引用为

Weisstein, Eric W. “红黑树。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Red-BlackTree.html

主题分类