红黑树是一张近似平衡的二叉搜索树，他最大的路径不超过最短路径的两倍，所以搜索时间复杂度仍是 O(lgn)
但是他相对于AVL平衡树，在插入一个节点的时候对于调整所需要的消耗要小，从而获得了高性能。
他的实现上及其规则相较于AVL树是复杂的，但是在实践中是高效的，能快速的进行插入删除等等操作。
1.性质：
为了实现最长路径不超过最短路径的两倍，我们需要以下几条规则来维护↓
1.结点带有颜色，红色或黑色
2..
根结点的颜色是黑色
3.没有连续的红色
4.所有路径都有相同的黑色结点数目
5.所有空结点都是黑色（这条规则无关紧要每条路径最后都一个空节点，单纯定义为黑，都加上NULL的黑色数不影响4规则）
2.用途：
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。所以在很多数据结构都用上了红黑
树，比如在计算机内核中很多红黑树，还有map和set等都用到红黑树。
3.实现：
下面来看一下红黑树的简单实现↓
#pragma once
#include
using namespace std;
enum Col
{
RED,
BLACK
};
template
struct RBTreeNode
{
RBTreeNode
* _left;
RBTreeNode
* _right;
RBTreeNode
* _parent; K _key; V _value; Col _col; RBTreeNode(K key, V value) :_key(key), _value(value), _left(NULL), _right(NULL), _parent(NULL), _col(RED) {} }; template
class RBTree { typedef RBTreeNode
Node; public: RBTree() :_root(NULL) {} void RotateR(Node* parent) { Node* grandfather = parent->_parent; Node* SubL = parent->_left; Node* SubLR = SubL->_right; SubL->_parent = parent->_parent; if (grandfather&&grandfather->_left == parent) { grandfather->_left = SubL; } else if (grandfather&&grandfather->_right == parent) { grandfather->_right = SubL; } SubL->_right = parent; parent->_parent = SubL; parent->_left = SubLR; if (SubLR) { SubLR->_parent = parent; } } void RotateL(Node* parent) { Node* grandfather = parent->_parent; Node* SubR = parent->_right; Node* SubRL = SubR->_left; SubR->_parent = parent->_parent; if (grandfather&&grandfather->_left == parent) { grandfather->_left = SubR; } else if (grandfather&&grandfather->_right == parent) { grandfather->_right = SubR; } SubR->_left= parent; parent->_parent = SubR; parent->_right = SubRL; if (SubRL) { SubRL->_parent = parent; } } bool Insert(const K& key, const V& value) { if (_root == NULL) //空树直接插入 { _root = new Node(key, value); _root->_col = BLACK; return true; } Node* parent = NULL; //非空从根结点开始 以key作比较寻找插入位置 Node* cur = _root; while (cur) { if (key == cur->_key) //找到相同的返回插入失败 { return false; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else if (key < cur->_key) { parent = cur; cur = cur->_left; } } if (key < parent->_key) { cur = new Node(key, value); cur->_parent = parent; parent->_left = cur; } else if (key > parent->_key) { cur = new Node(key, value); cur->_parent = parent; parent->_right = cur; } //调整 while (parent&&parent->_col == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) //父亲为祖父的左 { Node* uncle = grandfather->_right; if (uncle&&uncle->_col == RED) //u存在且为红 { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else //u不存在 或者 u存在为黑 { if (cur == parent->_left) //右单旋 { //右单旋 RotateR(grandfather); //先只旋转 ，以祖父为轴右旋转祖父与父亲这条线 parent->_col = BLACK; //旋转完变色 grandfather->_col = RED; if (parent->_parent == NULL) //单旋完成该子树顶端为parent指向结点，若他是新的根则赋给_root _root = parent; } else //左右双旋 { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; if (cur->_parent == NULL)//双旋旋完成该子树顶端为cur指向结点，若他是新的根则赋给_root _root = cur; break; } } } else // 父亲为祖父的右 { Node* uncle = grandfather->_left; if (uncle&&uncle->_col == RED) //同上逻辑u存在且为红 { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else //u不存在或者u为黑 { if (cur == parent->_right) //左单旋 { RotateL(grandfather); //以祖父为轴左旋转祖父与父亲这条线 parent->_col = BLACK; //变色 grandfather->_col = RED; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } } } _root->_col = BLACK; } return true; } void Print() { _printf(_root); } protected: void _printf(Node* root)//用做递归的函数 { if (root == NULL) return; _printf(root->_left); cout << root->_key << ":" << root->_value << " "; _printf(root->_right); return; } Node* _root; }; void test() { RBTree
T; cout << T.Insert(100, 'a')<
4.5种旋转原理
5.测试案例：
代码中插入顺序的过程示意：
代码运行结果
以上是我对红黑树的一些理解希望对你有用。
