目录

概念

结构 

插入 

父亲为红，叔叔存在且为红 

父亲为红，叔叔不存在或者为黑 

单旋 

双旋  

红黑树的验证 

红黑树删除 

红黑树性能分析

概念

红黑树是一种二叉平衡搜索树，以颜色标记每一个节点，通过对颜色的限制，确保没有一条路径长度路径长度的两倍，所以是近似平衡的。

性质 

1.每个节点不是红就是黑

2.根节点是黑色

3.如果一个节点是红色的，那么它的两个孩子节点是黑色的

4.每条路径黑色节点数目相等

5.每个叶子节点都是黑色的，此处指的是空节点。

结构 

enum Color
{RED,BLACK
};
template
struct RBNode
{RBNode* _left;RBNode* _right;RBNode* _parent;pair _kv;Color _col;RBNode(const pair& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};
template
class RBTree
{typedef RBNode Node;
public:RBTree():_root(nullptr){}
private:Node* _root;
};

插入 

 红黑树插入的新节点颜色为红。

插入分为两步：

1.按二叉搜索树规则插入

2.调整颜色

• 父亲为黑，此时不需要调整
• 父亲为红，叔叔存在且为红，此时父亲和叔叔变黑，祖父变红，从祖父开始继续向上调整
• 父亲为红，叔叔不存在或者为黑，此时需要旋转处理 

父亲为红，叔叔存在且为红 

解决方法：p，u变黑，g变红，从g开始继续向上调整 

父亲为红，叔叔不存在或者为黑 

单旋 

void RoateL(Node* parent){//更改链接关系Node* parentparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parentparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parentparent->_left == parent){parentparent->_left = subR;subR->_parent = parentparent;}else{parentparent->_right = subR;subR->_parent = parentparent;}}}void RoateR(Node* parent){//更改链接关系Node* parentparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parentparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parentparent->_left == parent){parentparent->_left = subL;subL->_parent = parentparent;}else{parentparent->_right = subL;subL->_parent = parentparent;}}}

双旋  

解决办法：

左边高：先对p左旋，再对g右旋，cur变黑，g变红

右边高： 先对p右旋，再对g左旋，cur变黑，g变红

bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;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 = parent;}else{parent->_left = cur;cur->_parent = parent;}//开始调整while (parent && parent->_col==RED)//当父亲为红才需要调整{Node* grandfather = parent->_parent;//grandfather一定存在if (grandfather->_left == parent){Node* uncle = grandfather->_right;//1.uncle存在且为红，p，u变黑，g变红，向上调整if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//2.uncle不存在或为黑，此时进行旋转else{Node* uncle = grandfather->_right;//单纯左边高//     g//  p//cur//此时对g进行右旋，p变黑，g变红if (parent->_left == cur){RoateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//   g//p//   cur//此时先对p进行左旋，再对g进行右旋//cur变黑，g变红else{RoateL(parent);RoateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//1.uncle存在且为红，p，u变黑，g变红，向上调整if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//2.uncle不存在或为黑else{//单纯右边高//   g//      p//        cur//对g进行左旋，g变红，p变黑if (parent->_right == cur){RoateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}////   g//      p//   cur// 此时先对p进行右旋，再对g进行左旋，cur变黑，g变红else{RoateR(parent);RoateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

红黑树的验证 

1.查看根节点是否为黑

2.查看是否有连续红节点

3.走到空就比较当前路径黑色节点数的参照值是否相等，不相等返回false 

选取最左路径当参照值 

bool _isBanlance(Node* root, int banchmark, int blacknum){if (root == nullptr){if (banchmark != blacknum){cout << "有路径中黑节点数量不相等"<_col == RED && root->_parent->_col == RED){cout << "出现连续红节点" << endl;cout << root->_kv.first << endl;return false;}if (root->_col == BLACK){++blacknum;}return _isBanlance(root->_left, banchmark, blacknum) &&_isBanlance(root->_right, banchmark, blacknum);}
bool isBanlance(){if (_root && _root->_col == RED){cout << "根节点不为红" << endl;return false;}Node* cur = _root;int banchmark = 0;while (cur){if (cur->_col == BLACK){banchmark++;}cur = cur->_left;}int blacknum = 0;return _isBanlance(_root, banchmark, blacknum);}

红黑树删除 

删除本篇不做讲解，如有兴趣，参考算法导论。 

红黑树性能分析

 红黑树和AVL树查找效率都为logn，但是红黑树不追求绝对平衡，保证最长路径不超过最短路径的二倍，达到近似平衡，减少了旋转的次数，所以在增删结构中红黑树更优，并且红黑树实现比AVL树简单，因此运用红黑树较多，map和set底层也是采用红黑树实现的。