主題
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樹, 有根樹

使用 探索

參考文獻

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.

在 中被引用

紅黑樹

請引用為

Weisstein, Eric W. “紅黑樹。” 來自 Web 資源。 https://mathworld.tw/Red-BlackTree.html

主題分類