红黑树

红黑树是一个相对的平衡，减少了旋转的消耗

1. 一个节点不是红的就是黑的
2. 根节点是黑的
3. 一个节点是红的，孩子是黑的（没有连续的红色节点）
4. 对于每个节点，从该节点到后代节点的简单路径，都包含相同的黑色（黑色节点的数量相等）
5. 每个叶子节点都是黑色的（null节点）

最长路径不超过最短路劲的2倍
最短路径：全黑
最长路径: 一黑一红
假设每条路径黑节点是N，
n<=random path<=2n
路径要数到空位置
左右两边没那么均衡:整体的高度
假设红黑树中一中路径黑色节点=x
高度2x>=h>=x
全黑 一黑一红
2^x-1<=N<=22x-1:N为节点个数

X>=logx(N),x<=log(N)/2

添加节点

添加节点主要是添加红色节点
以父亲为祖父的左节点为例

1. 叔叔存在且为红色

   把父亲和叔叔都改成黑色
   把祖父改成红色

2. 叔叔不存在或为黑色

   1. 我为父亲的左节点，进行一个右单旋，并把父亲改成黑色，把祖父改成红色
   2. 我为父亲的右节点，进行一个左右双旋，把我改黑，祖父改红

父亲为祖父的右节点与之相反

#pragma once
#include <iostream>
using namespace std;enum Color
{RED,BLACK
};
template <class K, class V>struct RBTreeNode
{RBTreeNode *_left;RBTreeNode *_right;RBTreeNode *_parent;pair<K, V> _kv;Color _col; //控制颜色RBTreeNode(const pair<K, V> &kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)//一开始的颜色给红色{}
};template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;private:Node *_root;private:void _InOrder(Node *root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}void RotateR(Node *parent){//右单旋转Node *subL = parent->_left;           //子节点Node *subLR = subL->_right;           //子节点的右节点Node *parentparent = parent->_parent; //出问题节点的父节点parent->_left = subLR;subL->_right = parent;parent->_parent = subL;if (subLR)subLR->_parent = parent;//和父节点的父节点连接if (parent == _root){//要旋转的节点已经是根//更新根_root = subL;_root->_parent = nullptr; //更新顶部}else{//父节点上面还有节点if (parentparent->_left == parent){//是左节点subL->_parent = parentparent;parentparent->_left = subL;}else{subL->_parent = parentparent;parentparent->_right = subL;}}}void RotateL(Node *parent) //左单旋{Node *subR = parent->_right;Node *subRL = subR->_left;Node *parentparent = parent->_parent;parent->_parent = subR;subR->_left = parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parentparent->_right == parent){parentparent->_right = subR;subR->_parent = parentparent;}else{parentparent->_left = subR;subR->_parent = parentparent;}}}public:RBTree(): _root(nullptr){}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->_left;}else if (cur->_kv.first < kv.first) //比他大，在右边{parent = cur;cur = cur->_right;}else{return false;}}//走到这里，就可以链接上cur = new Node(kv);cur->_col = RED; //新增节点颜色给红色cur->_parent = parent; //链接上父亲if (parent->_kv.first > kv.first){//比他小，在左边parent->_left = cur;}else{parent->_right = cur;}//插入之前一定是红黑树//这里就要控制平衡，通过颜色//插入黑节点（影响路径），还是红节点（只影响自己的，不影响其他区域）//往上调整//我为红，父亲如果为红，爷爷一定是黑色// 1.叔叔存在且为红while (parent && parent->_col == RED) //往上处理,父亲颜色为红色，就要处理，黑色就不要处理,为红，就不是根{Node *grandparent = parent->_parent;if (parent == grandparent->_left){Node *uncle = grandparent->_right; //叔叔就是在右边//叔叔存在且为红if (uncle && uncle->_col == RED){//叔叔存在，且为红//变色，继续向上处理parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent; //继续迭代往上操作parent = cur->_parent;}//叔叔不存在else //不存在，或存在且为黑{//不存在,进行旋转//旋转+变色if (cur == parent->_left){RotateR(grandparent); //进行右单旋转//变色parent->_col = BLACK;grandparent->_col = RED;}else{//双旋//左右双旋// p进行右单旋，g左单旋，g变红藕，cur变黑，RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else //父亲是祖父的右边{Node *uncle = grandparent->_left; //叔叔就是在右边//叔叔存在且为红if (uncle && uncle->_col == RED){//叔叔存在，且为红//变色，继续向上处理parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent; //继续迭代往上操作parent = cur->_parent;}//叔叔不存在else //不存在，或存在且为黑{//不存在,进行旋转//旋转+变色if (cur == parent->_right){RotateL(grandparent); //进行右单旋转//变色parent->_col = BLACK;grandparent->_col = RED;}else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK; //根的一定是黑色return true;}bool IsBalance(){if(_root&&_root->_col==RED){cout<<"根节点是黑色"<<endl;return false;}int basevalue=0;//基准值Node* left=_root;while(left){if(left->_col==BLACK){basevalue++;}left=left->_left;}//用最左路径黑色节点的数量，做基准值int blacknum=0;//每个节点的黑色个数return _IsBalance(_root,basevalue,blacknum);}void InOrder() //不能验证是不是AVL树{_InOrder(_root);}private:bool _IsBalance(Node* root,int basevalue,int blacknum){//根节点是黑的//红色，孩子是黑色,没有连续的红节点//每个路径含有相同的黑色if(root==nullptr){//一条路径走完了if(basevalue!=blacknum){//每条路劲都有blacknumcout<<"存在黑色节点数量不相等"<<endl;return false;}return true;}if(root->_col==RED&&root->_parent->_col==RED)//红节点{//检查它的父亲,一定有  cout<<"出现连续的红节点"<<endl;return false;}if(root->_col==BLACK){blacknum++;}return _IsBalance(root->_left,basevalue,blacknum)&&_IsBalance(root->_right,basevalue,blacknum);//没有用引用，下面的加加，不会影响下面}
};void test()
{RBTree<int, int> rbt;int a[]={16,3,7,11,9,26,18,14,15};// int a[] = {4,2,6,1,3,5,15,7,16,14};for (auto e : a){rbt.Insert(make_pair(e, e));}cout<<rbt.IsBalance()<<endl;rbt.InOrder();
}