二元搜尋樹是一種基本資料結構，但如果樹變得不平衡，其效能可能會受到影響。紅黑樹是一種平衡的二元搜尋樹，它使用一組規則來保持平衡，確保插入、刪除和搜尋等操作的對數時間複雜度，無論樹的初始形狀如何。紅黑樹是自我平衡的，使用簡單的顏色編碼方案在每次修改後調整樹。

紅黑樹是一種自平衡的二元搜尋樹，其中每個節點都有一個附加屬性：顏色，可以是紅色或黑色。這些樹的主要目標是在插入和刪除過程中保持平衡，確保高效的資料檢索和操作。

紅黑樹的屬性
紅黑樹具有以下屬性：

• 節點顏色：每個節點要么是紅色，要么是黑色。
• 根屬性：樹的根始終是黑色的。
• 紅色屬性：紅色節點不能有紅色子節點（任何路徑上都沒有兩個連續的紅色節點）。
• 黑色屬性：從節點到其後代空節點（葉子）的每條路徑都有相同數量的黑色節點。
• 葉屬性：所有葉（NIL 節點）都是黑色的。

#define RED        0    
#define BLACK    1    

typedef int Type;

// 紅黑樹節點
typedef struct RBTreeNode{
    unsigned char color;        
    Type   key;                    
    struct RBTreeNode *left;    // 左孩子
    struct RBTreeNode *right;    // 右孩子
    struct RBTreeNode *parent;    // 父
}Node, *RBTree;

// 紅黑樹根
typedef struct rb_root{
    Node *node;
}RBRoot;