紅黑樹

紅黑樹：紅黑樹是一棵二叉搜尋樹，樹中的每一個結點的顔色不是黑色就是紅色。可以把紅黑樹視為一棵擴充的二叉樹，用外部結點表示空指針。

特性1：根結點和所有外部結點的顔色是黑色。

特征2：從根節點到外部結點的途中沒有連續兩個結點的顔色是紅色。

特征3：所有從根節點到外部結點的路徑上都有相同數目的黑色結點。

從紅黑樹中任意一結點x出發（不包括結點x）,到達一個外部結點的任一條路徑上的黑結點的個數叫做x的黑高度，亦稱之為結點的階。紅黑樹的黑高度定義為根節點的黑高度。

紅黑樹中的結點：紅色結點、黑色結點、和外部結點。

結論1：設從根節點到外部結點的路徑長度（path length, pl）為該路徑上指針的個數，如果P與Q為紅黑樹中的兩條從根節點到外部結點的路徑，則有：PL(P)<=2PL(Q)。

結論2：設h是一棵紅黑樹的高度(不包括外部結點)，n是樹中内部結點的個數，r是根節點的黑高度，那麼有a、h<=2r, b、n>=2r-1, 3、h<=log2(n+1)

本文轉自NewPanderKing51CTO部落格，原文連結：http://www.cnblogs.com/newpanderking/p/3870579.html ，如需轉載請自行聯系原作者