再回首資料結構—紅黑樹（一）

紅黑樹與AVL樹一樣同為二分搜尋樹，紅黑樹又稱為是保持“黑平衡”的二叉樹，紅黑樹最大高度為：2logn，紅黑樹由這麼幾個獨特的特征：

　　1、每個節點或黑或紅

　　2、根節點為黑色

　　3、每個葉子節點（最後的空節點）都為黑色

　　4、如果一個節點為紅色，則他孩子節點全為黑色

　　5、從任意節點到葉子節點，經過的黑色節點為一樣多的

　　6、所有紅色節點都向左傾斜

　　在之前的二叉搜尋樹中我們在實作的節點結構中定義了用于存儲元素的e、用于存放左子樹的left、用于存放右子樹的right等對象，而在AVL樹中比二叉搜尋樹有所不同由于AVL需要維護左右子樹的節點高度是以多了一個元素height用于存放節點的高度；

　　紅黑樹也是基于之前二叉搜尋樹變體而來的，在紅黑樹中節點也隻比二叉搜尋樹多一個元素，二叉搜尋樹的節點由以下元素組成：

　　e ：用于存儲節點元素

　　left： 用于存儲左子樹

　　right：用于存儲右子樹

　　color：用于标志節點顔色，節點是紅色或黑色

紅黑樹的代碼定義：

type RBT struct {
    root    *RBTNode
    size    int
    compare Comparable
 }

 type RBTNode struct {
    e     interface{}
    left  *RBTNode
    right *RBTNode
    color bool
 }
           

根據紅黑樹的特性、定義可知：

　　1、大小為N的紅黑樹其高度不超過2logN

　　2、最壞情況下插入、查找元素的時間複雜度為：2logN

　　3、平均情況下插入、查找元素的平均複雜度為：logN

　　這裡隻簡單介紹了紅黑樹的相關概念，下面将從代碼實作的角度具體分析紅黑樹的實作；