红黑树的插入

一、红黑树

二、红黑树节点的定义

三、红黑树的插入

3.1按照二叉搜索的树规则插入新节点

3.2检测新节点插入后红黑树的情况

3.3红黑树插入代码总体实现

四、红黑树的验证

五、红黑树和AVL树的比较

一、红黑树

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质：

每个节点不是红色就是黑色
根节点和叶子节点（指空叶子节点）都是黑色
红节点的左右孩子节点一定为黑色，也就是说不存在连续的红节点
从根到每一个叶子结点的每一条路径上黑节点的数量是相同的
以上的4个性质保证了红黑树的最长路径不超过最短路径的两倍

二、红黑树节点的定义

enum Colour
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};

红黑树的节点要默认给成红色，因为我们在插入一个新节点时该新节点必须为红节点。如果插入的是黑节点，那么该黑节点所在的路径上黑色节点的数量就会改变，但是红黑树必须保证每一跳路径上黑色节点的数量相同，插入黑节点会影响红黑树的所以路径。

三、红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

3.1按照二叉搜索的树规则插入新节点

    bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;......}

3.2检测新节点插入后红黑树的情况

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；
但当新插入节点的双亲节点颜色为红色时，就违反了性质3：不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，parent为父节点，grandparent为祖父节点，uncle为叔叔节点

1.当uncle存在且为红节点

调整规则：parent和uncle变为黑节点，grandparent变为红节点，cur更新到grandparent的位置；如果cur的parent为红，继续向上调整更新；如果cur的parent为黑节点，调整结束，如果cur为根结点，cur变黑，结束调整
注意：图中的树可能是一棵完整的树，也可能是树的一部分子树

2.uncle不存在

cur一定为新插入的节点，如果cur不是新插入的节点，那么cur和parent就一定会有一个黑色节点，那就不满足每条路径上黑色节点数量相同的规则了
uncleb不存在的时候，假定parent为grandparent的左孩子，调整步骤分为旋转+变色，旋转+变色也存在两种不同情况：

如果插入位置在parent的左边，grandparent、parent、cur都在一条直线上，此时只需要进行右单旋，再将parent变黑，grandparent变红即可
如果插入位置在parent的右边，grandparent、paren、cur是一条折线，此时需要先以parent为旋转点进行左单旋，再以cur为旋转点进行右单旋，旋转后将cur变黑，grandparent变红即可

uncleb不存在的时候，假定parent为grandparent的右孩子，分析过程同parent为左孩子的过程相同，只是旋转方向发生了变化

3uncle存在且为黑

cur的原始颜色为黑节点，经过向上调整变色后变为红节点
uncleb存在且为黑的时候，假定parent为grandparent的左孩子，uncle为右孩子，调整步骤分为旋转+变色，旋转+变色也存在两种不同情况：

如果cur在parent的左边，grandparent、parent、cur都在一条直线上，此时只需要进行右单旋，再将parent变黑，grandparent变红即可
如果cur在parent的右边，grandparent、paren、cur是一条折线，此时需要先以parent为旋转点进行左单旋，再以cur为旋转点进行右单旋，旋转后将cur变黑，grandparent变红即可

uncleb存在且为黑的时候，假定parent为grandparent的右孩子，uncle为左孩子，分析过程同parent为左孩子uncle为右孩子的过程相同，只是旋转方向发生了变化

3.3红黑树插入代码总体实现

bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//调整树的平衡while (parent&& parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//uncle存在且为红if (uncle&& uncle->_col == RED){//变色parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;//继续向上调整cur = grandparent;parent = cur->_parent;}//uncle不存在 或者 存在且为黑else{//右单旋if (parent->_left == cur){RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//左右双旋else{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else{Node* uncle = grandparent->_left;//uncle存在且为红if (uncle&& uncle->_col == RED){//变色parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;//继续向上调整cur = grandparent;parent = cur->_parent;}//uncle不存在 或者 存在且为黑else{//左单旋if (parent->_right == cur){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//右左双旋else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;}

四、红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质

①如果有连续的红节点，一定不满足红黑树的性质，返回false
②验证每一条路径上黑色节点的数量是否都相同
③先计算其中一条路径上黑色节点的数量作为基准值（代码中计算的是最左侧路径上黑色节点的数量），再计算其他路径上黑色节点的数量，判断是否与基准值一样，一样返回true，不一样返回false

bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;//连续红节点if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << ":有连续红节点" << endl;return false;}//基准值Node* cur = root;int bechmark = 0;while (cur){if (cur->_col == BLACK)bechmark++;cur = cur->_left;}return checkcolour(root, 0, bechmark);}bool checkcolour(Node* root, int blacknum, int bechmark){if (root == nullptr){if (blacknum != bechmark){return false;}return true;}if (root->_col == BLACK)blacknum++;return checkcolour(root->_left, blacknum, bechmark) && checkcolour(root->_right, blacknum, bechmark);}