紅黑樹

概念

和AVL樹一樣，紅黑樹也是一種二叉搜索樹，是解決二叉搜索樹不平衡的另一種方案，他在每個(gè)節(jié)點(diǎn)上增加一個(gè)存儲位，用于表示節(jié)點(diǎn)的顏色，是Red或者Black

紅黑樹的核心思想是通過一些著色的條件限制，達(dá)到一種最長路徑不超過最短路徑的兩倍的狀態(tài)

所以說紅黑樹并不是嚴(yán)格平衡的樹，而是一種近似平衡

例如

性質(zhì)（條件限制）

紅黑樹一共有五條性質(zhì)，由此來保證最長路徑不超過最短路徑的兩倍

1. 每個(gè)節(jié)點(diǎn)都有顏色，不是黑色就是紅色
2. 根節(jié)點(diǎn)是黑色的
3. 如果一共節(jié)點(diǎn)是紅色，那么他的子節(jié)點(diǎn)一定是黑色（不會出現(xiàn)兩個(gè)紅色節(jié)點(diǎn)連接的情況）
4. 對于每個(gè)節(jié)點(diǎn)，以這個(gè)節(jié)點(diǎn)到所有后代的任意路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)
5. 每個(gè)葉子節(jié)點(diǎn)（空節(jié)點(diǎn)）是黑色的（為了滿足第四條性質(zhì)，某些情況下如果沒有第五條第四條會失效）

節(jié)點(diǎn)的定義

// 顏色
enum Color {RED,BLACK
};template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data) :_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};

我們定義顏色時(shí)，使用枚舉類型，可以方便且明了的看到顏色

除此之外我們默認(rèn)插入節(jié)點(diǎn)是紅色的，因?yàn)橐坏┎迦牍?jié)點(diǎn)是黑色，就會違反第四條規(guī)則，如果要滿足的話，就要走到每一條路徑上插入對應(yīng)的黑色節(jié)點(diǎn)，代價(jià)巨大

當(dāng)插入節(jié)點(diǎn)是紅色時(shí)，有可能會違反第三條規(guī)則，但是我們可以通過變色，旋轉(zhuǎn)等操作在局部進(jìn)行改變，這樣就能使之仍然滿足條件

紅黑樹的結(jié)構(gòu)

為了后續(xù)利用紅黑樹封裝map和set，我們對紅黑樹增加一個(gè)頭節(jié)點(diǎn)，為了和根節(jié)點(diǎn)進(jìn)行區(qū)分，我們將頭節(jié)點(diǎn)賦為黑色，并且讓頭節(jié)點(diǎn)的parent指向根節(jié)點(diǎn)，left指向紅黑樹的最小節(jié)點(diǎn)，right指向最大節(jié)點(diǎn)，如圖

紅黑樹的插入

紅黑樹插入時(shí)也是按照二叉搜索樹的規(guī)則進(jìn)行插入，并在此基礎(chǔ)上加上平衡條件，因此插入也就分為兩步

1. 按照二叉搜索樹的規(guī)則插入新節(jié)點(diǎn)
2. 插入節(jié)點(diǎn)后檢測規(guī)則是否被破壞

因?yàn)椴迦爰t節(jié)點(diǎn)時(shí)只有可能破壞第三條規(guī)則，因此我們只需要判斷父節(jié)點(diǎn)是否為紅色即可

然后我們分情況討論

為了方便敘述，我們約定cur為插入節(jié)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)

cur為紅，p為紅，g為黑，u存在且為紅

畫出來是這樣的

這時(shí)我們需要將g改為紅色，p和u改為黑色即可，這樣既能保證紅色不連續(xù)，黑色數(shù)量一致，如圖

但是如果g是是子樹，那么g一定有父節(jié)點(diǎn)，當(dāng)g的父節(jié)點(diǎn)也是紅色時(shí)，也就同樣需要向上調(diào)整了

cur為紅，p為紅，g為黑，u不存在或u為黑，插入到p對應(yīng)的一邊

畫出來是這樣的

u的情況有兩種

1. u節(jié)點(diǎn)不存在，說明cur一定是新插入的節(jié)點(diǎn)，因?yàn)橐ＷC左右兩個(gè)路徑的黑色節(jié)點(diǎn)的數(shù)量相同
2. u節(jié)點(diǎn)存在，說明cur節(jié)點(diǎn)是由下至上調(diào)整的紅色，原因也是左右路徑的黑色節(jié)點(diǎn)要相同

對于這兩種情況的調(diào)整方法是相同的，如果p是g的左節(jié)點(diǎn)，cur為p的左節(jié)點(diǎn)，則右單旋，如果p是g的右節(jié)點(diǎn)，cur為p的右節(jié)點(diǎn)，則左單旋

同時(shí)p要變成黑色，g要變成紅色

變成如下狀態(tài)

那么因?yàn)樽钌厦娴母?jié)點(diǎn)顏色沒有變化，也就不需要繼續(xù)向上調(diào)整了

cur為紅，p為紅，g為黑，u不存在或u存在且為黑，插入到與p相反的一邊

如圖

這種情況需要針對p進(jìn)行單旋，如果p為g的左節(jié)點(diǎn)，cur為p的右節(jié)點(diǎn)，則對p左單旋，反之則為右單旋，此時(shí)就會變成第二種情況，再繼續(xù)處理即可

第一次處理的結(jié)果如下

示例代碼

template<class K, class T, class KeyOfT>
class RBTree {typedef RBTreeNode<T> Node;
public:pair<Node*, bool> Insert(const T& data) {// 插入根節(jié)點(diǎn)直接返回if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;// 平衡二叉樹找到插入位置while (cur) {if (kot(cur->_data) < kot(data)) {parent = cur;cur = cur->_right;} else if (kot(cur->_data) > kot(data)) {parent = cur;cur = cur->_left;} else {return make_pair(cur, false);}}// 新建節(jié)點(diǎn)cur = new Node(data);Node* newnode = cur;cur->_col = RED;// 連接父節(jié)點(diǎn)if (kot(parent->_data) < kot(data)) {parent->_right = cur;cur->_parent = parent;} else {parent->_left = cur;cur->_parent = parent;}// 如果父節(jié)點(diǎn)存在且父節(jié)點(diǎn)為紅色則需要調(diào)整while (parent && parent->_col == RED) {Node* grandfather = parent->_parent;if (parent == grandfather->_left) {//     g//   p   u// c // 判斷u是否存在和他的顏色Node* uncle = grandfather->_right;// 如果存在且為紅色if (uncle && uncle->_col == RED) {// 變色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上調(diào)整cur = grandfather;parent = cur->_parent;} else {// 如果不存在或u為黑色，需要判斷同側(cè)還是異側(cè)// 如果是同側(cè)if (cur == parent->_left) {//     g//   p// cRotateR(grandfather); // 右旋// 調(diào)整顏色parent->_col = BLACK;grandfather->_col = RED;} else {//    g//  p//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}} else { // p = g->rNode* uncle = grandfather->_left;//     g//   u   p//         c// 判斷u是否存在和他的顏色// 如果存在且為紅色if (uncle && uncle->_col == RED) {// 變色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上調(diào)整cur = grandfather;parent = cur->_parent;} else {if (cur == parent->_right) {RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;} else {//     g//   u   p //     c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;else {if (parentParent->_left == parent) {parentParent->_left = subR;} else {parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) {_root = subL;subL->_parent = nullptr;} else {if (parentParent->_left == parent) {parentParent->_left = subL;} else {parentParent->_right = subL;}subL->_parent = parentParent;}}
private:Node* _root = nullptr;
};

紅黑樹的驗(yàn)證

紅黑樹要驗(yàn)證需要驗(yàn)證兩個(gè)部分

1. 檢測是否中序遍歷是有序序列
2. 檢測是否滿足紅黑樹的性質(zhì)

這里我們就不講紅黑樹的刪除了，完成紅黑樹的驗(yàn)證之后就算作已經(jīng)完成了任務(wù)，接下來會使用紅黑樹模擬實(shí)現(xiàn)map和set

紅黑樹與AVL樹的比較

紅黑樹和AVL樹都是高效的平衡二叉樹，但是紅黑樹不追求絕對的平衡，降低了插入和旋轉(zhuǎn)的次數(shù)，因此性能比AVL更優(yōu)，而且紅黑樹比AVL樹的實(shí)現(xiàn)更加簡單，所以實(shí)際中運(yùn)用紅黑樹更多

完整代碼

#pragma once
#include<utility>
#include<iostream>
using namespace std;
// 顏色
enum Color {RED,BLACK
};template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) {}
};template<class K, class T, class KeyOfT>
class RBTree {typedef RBTreeNode<T> Node;
public:pair<Node*, bool> Insert(const T& data) {if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;// 平衡二叉樹找到插入位置while (cur) {if (kot(cur->_data) < kot(data)) {parent = cur;cur = cur->_right;} else if (kot(cur->_data) > kot(data)) {parent = cur;cur = cur->_left;} else {return make_pair(cur, false);}}// 新建節(jié)點(diǎn)cur = new Node(data);Node* newnode = cur;cur->_col = RED;// 連接父節(jié)點(diǎn)if (kot(parent->_data) < kot(data)) {parent->_right = cur;cur->_parent = parent;} else {parent->_left = cur;cur->_parent = parent;}// 如果父節(jié)點(diǎn)存在且父節(jié)點(diǎn)為紅色則需要調(diào)整while (parent && parent->_col == RED) {Node* grandfather = parent->_parent;if (parent == grandfather->_left) {//     g//   p   u// c // 判斷u是否存在和他的顏色Node* uncle = grandfather->_right;// 如果存在且為紅色if (uncle && uncle->_col == RED) {// 變色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上調(diào)整cur = grandfather;parent = cur->_parent;} else {// 如果不存在或u為黑色，需要判斷同側(cè)還是異側(cè)// 如果是同側(cè)if (cur == parent->_left) {//     g//   p// cRotateR(grandfather); // 右旋// 調(diào)整顏色parent->_col = BLACK;grandfather->_col = RED;} else {//    g//  p//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}} else { // p = g->rNode* uncle = grandfather->_left;//     g//   u   p//         c// 判斷u是否存在和他的顏色// 如果存在且為紅色if (uncle && uncle->_col == RED) {// 變色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上調(diào)整cur = grandfather;parent = cur->_parent;} else {if (cur == parent->_right) {RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;} else {//     g//   u   p //     c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;else {if (parentParent->_left == parent) {parentParent->_left = subR;} else {parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) {_root = subL;subL->_parent = nullptr;} else {if (parentParent->_left == parent) {parentParent->_left = subL;} else {parentParent->_right = subL;}subL->_parent = parentParent;}}void InOrder() {_InOrder(_root);cout << endl;}void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << ' ';_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int refVal) {if (root == nullptr) {if (blacknum != refVal) {cout << "存在黑色節(jié)點(diǎn)數(shù)量不相等的路徑" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED) {cout << "存在連續(xù)的紅節(jié)點(diǎn)" << endl;return false;}if (root->_col == BLACK) {++blacknum;}return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);}bool IsBalance() {if (_root == nullptr)return true;if (_root->_col == RED)return false;int refVal = 0; // 參考值Node* cur = _root;while (cur) {if (cur->_col == BLACK) {++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}int Height() {return _Height(_root);}int _Height(Node* root) {if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH + rightH;}size_t Size() {return _Size(_root);}size_t _Size(Node* root) {if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}Node* Find(const K& key) {Node* cur = _root;while (cur) {if (cur->_data < key) {cur = cur->_right;}else if (cur->_data > key) {cur = cur->_left;}else {return cur;}}return nullptr;}private:Node* _root = nullptr;
};