RBTree模拟实现

一、概念

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

性质：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点 NIL结点)

问题：

如何做到最长路径<=2*最短路径？

不能连续红色+root为黑+每条路径黑结点数相同。

AVL和RBT性能对比：搜索->io

搜索/查找时：同一量级

插入/删除：

AVL树，插入删除时，因为要控制严格平衡，会进行大量旋转操作。        

二、结点的定义

三、Insert

寻找插入位置

先查找要插入的位置，_root根节点颜色默认为BLACK。

插入新结点的颜色为RED。

这是为了满足性质4，如果新结点为BLACK，会影响所有路径，相当于其它路径的黑结点数都距离目标个数缺少1个。

新结点为RED，只用满足性质3不是连续红结点即可。

则只需调整其祖先结点，并关注uncle结点颜色即可。

1、uncle存在且为红

2、uncle不存在

3、uncle存在且为黑

4、代码实现

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else return false;}cur = new Node(kv);cur->_col = RED; if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}//每次新增newnode，要初始化它的_parent指针  三叉链cur->_parent = parent;//parent为红才需要调整while (parent && parent->_col == RED){Node* ppnode = parent->_parent;//1、uncle存在且为红//2、uncle不存在//3、uncle存在且为黑if (parent == ppnode->_left){Node* uncle = ppnode->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;ppnode->_col = RED;//继续向上调整cur = ppnode;parent = cur->_parent;//没有父亲则cur为根，直接变黑即可}else if (uncle == nullptr || (uncle && uncle->_col == BLACK)){//uncle不变色，2种情况可以合成一种if (cur == parent->_left){//     pp//   p 	  //cRotateR(ppnode);parent->_col = BLACK;ppnode->_col = RED;}else{//     pp//   p 	  //		cRotateL(parent);RotateR(ppnode);cur->_col = BLACK;ppnode->_col = RED;}break;//只要旋转完就break}	}else{Node* uncle = ppnode->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;ppnode->_col = RED;//继续向上调整cur = ppnode;parent = cur->_parent;//没有父亲则cur为根，直接变黑即可}else if (uncle == nullptr || uncle && uncle->_col == BLACK){//uncle不变色，2种情况可以合成一种if (cur == parent->_right){//     pp//   u    p 	  //			cRotateL(ppnode);ppnode->_col = RED;parent->_col = BLACK;}else{//     pp//   u	  p 	  //		cRotateR(parent);RotateL(ppnode);cur->_col = BLACK;ppnode->_col = RED;}break;//只要旋转完就break}}}_root->_col = BLACK;return true;}

四、IsBalance检验是否平衡

必须在满足是红黑树的条件下，检验其所有性质。

1、若简单的计算最长路径和最短路径，可能会出现连续RED的情况，不满足。

2、遍历所有路径，统计每条路径黑结点的个数，看是否都相同，遍历过程可以检查是否存在连续RED结点。