红黑树的插入 C++

红黑树与二叉搜索树类似

它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：

1.节点是红色或黑色
2.根是黑色
3.叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
红色节点的子节点都是黑色
4.红色节点的父节点都是黑色
5.从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
6.从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

现在我们进行对红黑数的插入

enum Colour
{BLACK,RED,
};
template<class K, class V>
class RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V>_kv;Colour _col;
};template<class K, class V>
class RBtree
{typedef RBTreeNode<K, V>Node; public:bool Insert(const pair<K, V>& kv){//1.按搜索树的规则进行插入if (!_root){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first<kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right=cur;cur->_parent = parernt;}else{parent->left = cur;cur->_parent=parent;}//新增节点红的cur->_col = RED;while (parent->_col == RED){//红黑树的调节关键看父节点的另一个节点Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//情况一:uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况二：uncle不存在或为黑else{//情况三：双旋—>单旋if (cur==parent->_right){RotateL(parent);//左旋swap(parent, cur);}RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}else{Node* uncle = grandfather->_right;//情况一:uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况二：uncle不存在或为黑else{//情况三：双旋—>单旋if (cur == parent->_right){RotateR(parent);swap(parent, cur);}RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}}root->_col = BLACK;return true;}private:Node* _root = nullptr;
};