一、红黑树概念

1.概念

红黑树也是一种二叉搜索树，在每个结点上增加一个存储位，来表示该节点的颜色，节点要么是红色要么是黑色。

2.性质

红黑树具有以下性质：

（1）每个结点不是红色就是黑色

（2）根节点是黑色的

（3）没有连续的红色节点

（4）每条路径上都包含相同数目的黑色节点

由于（3）和（4）互相控制，因此满足以上性质就能保证：最长路径中节点个数不会超过最短路径节点个数的2倍。

最短路径：全部由黑色节点构成

最长路径：由一黑一红构成，且红色节点数量等于黑色节点数量。

假设黑色节点有N个，最短路径长度为 最长路径长度为2* 。但是在红黑树中，不一定有最短路径和最长路径。

二、红黑树定义

1.红黑树节点定义

红黑树节点相比于AVL树，多了一个颜色，因此需要一个成员变量来存储节点颜色。AVL树用高度严格控制平衡。红黑树近似平衡，所以不需要平衡因子。

但是红黑树节点的构造函数在初始化节点时，肯定要初始化节点颜色的，那么颜色需要一开始初始化成红色，因为初始化成红色，可能破坏规则（3），影响不大。但是假如将节点初始化成黑色，一定会破坏规则（4）。

（1）将新插入节点置为红色

假如将新插入节点置为红色，会有以下两种情况：

①当父亲是黑色时，没有破坏规则（3），也没有破坏规则（4）

②当父亲是红色时，破坏了规则（3），但是只需要改变一下颜色即可

（2）将新插入节点置为黑色

但是假如将新节点初始化成黑色，不管父亲是黑色还是红色，一定会破坏规则（4），并且影响其他路径，影响范围广。

①当父亲是黑色时，破坏了规则（4）

②当父亲是红色时，也破坏了规则（4）

因此节点要初始化成红色。

1. //红黑树节点颜色
2. enum Colour
3. {
4.  RED,
5.  BLACK,
6. };
7. 
8. //红黑树节点定义
9. template<class K,class V>
10. struct RBTreeNode
11. {
12.   RBTreeNode<K, V>* _left;//节点的左孩子
13.   RBTreeNode<K, V>* _right;//节点的右孩子
14.   RBTreeNode<K, V>* _parent;//节点的父亲
15. 
16.   pair<K,V> _kv;//节点的值
17.   Colour _col;//节点颜色
18. 
19.   RBTreeNode(const pair<K, V>& kv)
20.     :_left(nullptr)
21.     ,_right(nullptr)
22.     ,_parent(nullptr)
23.     ,_kv(kv)
24.     ,_col(RED)//节点初始化成红色
25.   {}
26. };

2.红黑树定义

1. template<class K,class V>
2. class RBTree
3. {
4.  typedef RBTreeNode<K, V> Node;
5. 
6. //构造函数
7. RBTree()
8.    :_root(nullptr)
9.  {}
10. 
11. private:
12.   Node* _root;
13. };