1.  //插入
2.  pair<Node*, bool> Insert(const pair<K, V>& kv)
3.  {
4.    if (_root == nullptr)
5.    {
6.      _root = new Node(kv);
7.      _root->_col = BLACK;
8.      return make_pair(_root, true);
9.    }
10. 
11.     //1.先看树中，kv是否存在
12.     Node* parent = nullptr;
13.     Node* cur = _root;
14.     while (cur)
15.     {
16.       if (cur->_kv.first < kv.first)
17.       {
18.         //kv比当前节点值大，向右走
19.         parent = cur;
20.         cur = cur->_right;
21.       }
22.       else if (cur->_kv.first > kv.first)
23.       {
24.         //kv比当前节点值小，向左走
25.         parent = cur;
26.         cur = cur->_left;
27.       }
28.       else
29.       {
30.         //kv和当前节点值相等，已存在，插入失败
31.         return make_pair(cur, false);
32.       }
33.     }
34. 
35.     //2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了
36.     Node* newNode = new Node(kv);
37.     newNode->_col = RED;
38.     if (parent->_kv.first < kv.first)
39.     {
40.       //kv比parent值大，插入到parent的右边
41.       parent->_right = newNode;
42.       cur->_parent = parent;
43.     }
44.     else
45.     {
46.       //kv比parent值小，插入到parent的左边
47.       parent->_left = newNode;
48.       cur->_parent = parent;
49.     }
50.     cur = newNode;
51. 
52.     //如果父亲存在，且父亲颜色为红就要处理
53.     while (parent && parent->_col == RED)
54.     {
55.       //关键看叔叔
56.       Node* grandfather = parent->_parent;
57.       if (parent == grandfather->_left)//父亲是祖父的左子树
58.       {
59.         Node* uncle = grandfather->_right;
60.         //情况一：叔叔存在且为红
61.         if (uncle->_col == RED)
62.         {
63.           parent->_col = uncle->_col = BLACK;
64.           grandfather->_col = RED;
65. 
66.           //继续向上调整
67.           cur = grandfather;
68.           parent = cur->_parent;
69.         }
70.         else//情况二+情况三：叔叔不存在或叔叔存在且为黑
71.         {
72.           //情况二：单旋
73.           if (cur == parent->_left)
74.           {
75.             RotateR(grandfather);
76.             parent->_col = BLACK;
77.             grandfather->_col = RED;
78.           }
79.           else//情况三：双旋
80.           {
81.             RotateL(parent);
82.             RotateR(grandfather);
83.             cur->_col = BLACK;
84.             grandfather->_col = RED;
85.           }
86.           break;//插入结束
87.         }
88.       }
89.       else//父亲是祖父的右子树
90.       {
91.         Node* uncle = grandfather->_left;
92.         //情况一：叔叔存在且为红
93.         if (uncle && uncle->_col == RED)
94.         {
95.           parent->_col = uncle->_col = BLACK;
96.           grandfather->_col = RED;
97. 
98.           //继续往上调整
99.           cur = grandfather;
100.          parent = grandfather->_parent;
101.        }
102.        else//情况二+情况三：叔叔不存在或叔叔存在且为黑
103.        {
104.          //情况二：单旋
105.          if (cur == parent->_right)
106.          {
107.            RotateL(grandfather);
108.            parent->_col = BLACK;
109.            grandfather->_col = RED;
110.          }
111.          else//情况三：双旋
112.          {
113.            RotateR(parent);
114.            RotateL(grandfather);
115.            cur->_col = BLACK;
116.            grandfather->_col = RED;
117.          }
118.          break;//插入结束
119.        }
120.      }
121. 
122.    }
123.    _root->_col = BLACK;
124. 
125.    return make_pair(newNode, true);
126.  }

1.  //查找
2.  Node* Find(const K& key)
3.  {
4.    Node* cur = _root;
5.    while (cur)
6.    {
7.      if (cur->_kv.first < key)//key比当前节点小，就向右查找
8.      {
9.        cur = cur->_right;
10.       }
11.       else if (cur->_kv.first > key)//key比当前节点大，就向左查找
12.       {
13.         cur = cur->_left;
14.       }
15.       else//找到了
16.       {
17.         return cur;
18.       }
19.     }
20.     return nullptr;//空树，直接返回
21.   }

1.  bool _CheckBalance(Node* root, int blackNum, int count)
2.  {
3.    if (root == nullptr)
4.    {
5.      if (count != blackNum)
6.      {
7.        cout << "黑色节点数量不相等" << endl;
8.        return false;
9.      }
10.       return true;
11.     }
12. 
13.     if (root->_col == RED && root->_parent->_col == RED)
14.     {
15.       cout << "存在连续红色节点" << endl;
16.       return false;
17.     }
18. 
19.     if (root->_col == BLACK)
20.     {
21.       count++;
22.     }
23. 
24.     return _CheckBalance(root->_left, blackNum, count)
25.       && _CheckBalance(root->_right, blackNum, count);
26.   }
27. 
28.   //检查是否平衡
29.   bool CheckBlance()
30.   {
31.     if (_root == nullptr)
32.     {
33.       return true;
34.     }
35. 
36.     if (_root->_col == RED)
37.     {
38.       cout << "根节点为红色" << endl;
39.       return false;
40.     }
41. 
42.     //找最左路径做黑色节点数量参考值
43.     int blackNum = 0;
44.     Node* left = _root;
45.     while (left)
46.     {
47.       if (left->_col == BLACK)
48.       {
49.         blackNum++;
50.       }
51.       left = left->_left;
52.     }
53. 
54.     int count = 0;
55.     return _CheckBlance(_root, blackNum, count);
56.   }

1.  //遍历
2.  void _InOrder(Node* root)
3.  {
4.    if (root == nullptr)
5.    {
6.      return;
7.    }
8. 
9.    _InOrder(root->_left);
10.     cout << root->_kv.first << ":" << root->_kv.second << endl;
11.     _InOrder(root->_right);
12.   }
13. 
14.   void InOrder()
15.   {
16.     _InOrder(_root);
17.     cout << endl;
18.   }

1. #include "RedBlackTree.h"
2. 
3. void TestRBTree()
4. {
5.  //,1,3,5,15,7,16,14
6.  int a[] = { 4,2,6,1,3,5,15,7,16 };
7.  RBTree<int, int> t;
8.  for (auto e : a)
9.  {
10.     t.Insert(make_pair(e, e));
11.   }
12. 
13.   t.InOrder();
14.   //cout << t.CheckBalance() << endl;
15. }
16. 
17. int main()
18. {
19.   TestRBTree();
20.   return 0;
21. }