目录

红黑树：基于AVL树改进

红黑树的性质

红黑树基本结构

insert基本结构

新增节点的默认颜色为红色

节点性质总结

情况一: cur为红，p为红，g为黑，u存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

insert代码实现

验证是否为红黑树

源码链接

红黑树：基于AVL树改进

AVL树控制平衡因子，严格要求左右子树高度差不超过1，所以他的效率一直都是保持在O(logN)左右，但严格要求平衡导致其需要更多次的旋转

如果不严格要求平衡，只需要达到近似平衡，保持其性能还是处于logN数量级，减少旋转次数，可提升性能（AVL树的高度平衡是因为其通过大量的旋转来完成的，所以对于经常发生删除和插入的结构，红黑树的效率会更优，并且红黑树的实现比起AVL更加容易且易于控制，所以实际中使用红黑树更多）

红黑树确保最长路径不超过最短路径的二倍，在最坏情况下，增删查改效率是O(2logN)。

红黑树概念

红黑树是一种二叉搜索树，需要在每个结点增加一个存储位表示结点的颜色，分别是Red/Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保最长路径不超过最短路径的二倍，因而接近平衡

红黑树的性质

控制住颜色的规则(满足下面的性质)，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍：

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3. 如果一个节点是红色，则它的两个孩子结点是黑色 (没有连续红节点)

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径黑色节点数量相同)

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

(性质5出题：空树也是红黑树，性质5中规定树中的空指针域为叶子节点，因此空树也有节点)

根据规则3，4可以推导出：存在最短路径一定是全黑，存在最长路径一定是一黑一红

红黑树基本结构

基本结构与AVL树相似，只是把平衡因子换成枚举标识颜色，满足性质1

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

insert基本结构

插入分为两个步骤：

1.按照二叉搜索树的特性插入

2.满足红黑树的性质调节颜色

insert基本结构，唯一需要改变的就是当root为根时，变为黑色，满足性质2

template
class RBTree
{
public:typedef RBTreeNode Node;bool insert(const pair& 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);if (parent->_kv.first > kv.first){parent->_left = cur;}else if (parent->_kv.first < kv.first){parent->_right = cur;}cur->_parent = parent;}
private:Node* _root;
};

新增节点的默认颜色为红色

如果此时插入30，新增的节点我们设置为红色，违反规则3

如果此时插入30，新增的节点我们设置为黑色，违反规则4

如果新增颜色为黑色，违反规则4，整棵树每个路径的颜色节点也都需要跟着改变，直到满足规则4，消耗巨大

如果新增颜色为红色，违反规则3，只有父亲路径颜色被影响，可以接受

插入后如果规则被影响，有两个处理规则：

1.变色(能变色就变色，不能变色再旋转+变色)

2.旋转

实例举例-处理过程

我们需要标记4个节点，新插入节点称为cur，父节点称为parent，父节点的父节点称为grandfather，父节点的兄弟节点称为uncle(为grandfather的另一个子节点)

一.

插入时，如果父亲为黑色不用处理，结束(插入后已经是红黑树)。

插入时，如果父亲为红色需要处理，先把父亲变黑(否则违反规则3)，继续下一步

二.

遇事不决看叔叔，此时分三种情况：

此时祖父一定是黑，原因在于：插入后父亲是红，祖父一定是黑。插入后父亲是黑，看过程1，不需要看叔叔直接结束

1.插入后如果叔叔存在且为红：把叔叔变黑，祖父变红。

如果祖父为根，把根变黑，结束。

否则继续下一步

2. 插入后如果叔叔存在且为黑

3.插入后如果叔叔不存在

三.

如果还是子树一部分，把祖父变为cur(虽然不是新增，但是从黑变成红）此时整棵树黑色节点数量继续保持不变，不违反规则4，继续向上调整颜色

如果父亲为红，重复第二步。如果父亲为黑，不违反规则，结束。

继续重复二，三步，直到不满足条件结束

节点性质总结

1.新节点的默认颜色是红色

2.如果新插入节点的父节点颜色是黑色，没有违反红黑树任何性质，则不需要调整，直接结束；

3.如果新插入节点的父节点颜色为红色，违反了性质3不能有连续的红色，需要向上继续调整

4.祖父一定是黑，原因：插入后如果父亲是红，祖父一定是黑。插入后如果父亲是黑，不需要找祖父

这里代称：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

而此时，cur为红，p为红，g为黑情况已经固定，只需要看u即可

我们可以通过检测新节点插入后，红黑树的性质是否造到破坏来维护红黑树：

情况一: cur为红，p为红，g为黑，u存在且为红

 cur为红，p为红，g为黑，u存在且为红隐含意思：最长路径并没有超过最短路径2倍，不需要变色

a/b/c/d/e子树有无数种情况排列存在，cur有可能是新增，也有可能是由其他情况变成红色。处理结果都是p,u变黑，g变红(如果g是子树，变红保持子树黑色节点数量不变，不违反第四点)。把g当成cur，g不是根，继续向上调整；g是根，在把g变为黑色。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

如果u不存在， cur就是新增。原因在于：如果cur不是新增节点，则cur和p之间一定有一个为黑色，则不满足性质4：每条路径黑色节点数量相同。此时单纯变色无法满足红黑树性质

解决方法：对g位置右单旋+p变黑，g变红

如果u存在且为黑色，则此时的cur是红色的原因可能是下面的子树在进行变色处理时，将cur从原本的黑色变为了红色。（否则不满足路径黑节点数量相同的性质）如果只变色p为黑色，左子树比右子树多一个黑色节点，不满足性质4，此时单纯变色无法满足红黑树性质，需要旋转+变色

解决方法：对g位置右单旋+p变黑，g变红

和AVL树一样，因为父亲和孩子呈直线状态，所以只需要单旋即可。
如果p是g的左孩子，cur是p的左孩子，此时g进行右单旋
如果p是g的右孩子，cur是p的右孩子，此时g进行左单旋。

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

如果u存在且为黑色，新增节点在b/c中，则此时的cur是红色的原因可能是下面的子树在进行变色处理时，将cur从原本的黑色变为了红色。（否则不满足路径黑节点数量相同的性质）单纯变色无法满足红黑树性质，需要双旋+变色(cur变黑，g变红)

如果p是g的左孩子，cur是p的右孩子，p为轴点此时进行左单旋，g再进行右单旋。
如果p是g的右孩子，cur是p的左孩子，p为轴点此时进行右单旋，g再进行左单旋。

双旋之后，cur变为黑色，parent和grandparent为红色。

insert代码实现

其中左右单旋介绍在此博客数据结构【AVL树】_北方留意尘的博客-CSDN博客

enum Color
{RED,BLACK
};template
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;Color _col;pair _kv;RBTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(BLACK){}
};template
class RBTree
{
public:typedef RBTreeNode Node;bool insert(const pair& 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;//破坏规则3if (parent->_kv.first > kv.first){parent->_left = cur;}else if (parent->_kv.first < kv.first){parent->_right = cur;}cur->_parent = parent;//情况一可能持续往上更新,是根才结束,所以用whilewhile (parent && parent->_col == RED){Node* grandfather = parent->_parent;assert(grandfather && grandfather->_col == BLACK);//关键看叔叔if (grandfather->_left == parent){Node* uncle = grandfather->_right;//情况一不关注左右，因为不需要旋转if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;//变色后继续向上处理cur = grandfather;parent = cur->_parent;}//情况二+三(uncle不存在 or 存在为黑)else{if (cur == parent->_left)//情况二，右单旋+变色，因为父亲也是祖父的左，呈直线//    g//  p    u //c{RotaR(grandfather);parent->_col = BLACK;grandfather->_col = RED; }else if (cur == parent->_right)//情况三，p是g的左孩子，cur是p的右孩子，p为轴点此时进行左单旋，cur再进行右单旋{RotaL(parent);RotaR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//不需要判断了}}else//(grandfather->_right == parent){Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;//变色后继续向上处理cur = grandfather;parent = cur->_parent;}else{//    g//  u    p //         cif (cur == parent->_right)//情况二，左单旋+变色，因为父亲也是祖父的右，呈直线{RotaL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else if (cur == parent->_left)//情况三，p是g的右孩子，cur是p的左孩子，p为轴点此时进行右单旋，g再进行左单旋。{RotaR(parent);RotaL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//不需要判断了}}}//如果parent不存在，说明grandfather是根_root->_col = BLACK;return true;}void InOrder(){PrintBST(_root);cout << endl;}private:void PrintBST(Node* root){if (root == nullptr)return;PrintBST(root->_left);cout << root->_kv.first << ":" << root->_kv.second << "  ";PrintBST(root->_right);}void RotaL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;//1if (subRL != nullptr){subRL->_parent = parent;//2}subR->_left = parent;//3subR->_parent = pparent;//4parent->_parent = subR;//5if (pparent){if (pparent->_left == parent){pparent->_left = subR;//6}else{pparent->_right = subR;//6}}else//root == nullptr,此时subR为根{_root = subR;//6}}void RotaR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_left = subLR;//1if (subLR)subLR->_parent = parent;//2subL->_right = parent;//3parent->_parent = subL;//4subL->_parent = pparent;//5if (pparent){if (pparent->_left == parent){pparent->_left = subL;//6}else{pparent->_right = subL;//6}}else{_root = subL;//6}}Node* _root = nullptr;
};

验证是否为红黑树

 验证其是否为红黑树，只需要对5条性质都验证即可，违反任意规则都不是红黑树

	bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)//检查规则2{cout << "根节点不是黑色" << endl;return false;}Node* cur = _root;int benchmark = 0;//基准值，一条最左路径的黑色节点数量和所有路径黑色节点都相等while (cur){if(cur->_col == BLACK)benchmark++;cur = cur->_left;}return _IsBalance(_root,0,benchmark);//检查规则4}private:bool _IsBalance(Node* root,int balance,int benchmark){if (root == nullptr){if (benchmark == balance)//查看是否违反规则4{return true;}cout << "每个路径黑色节点数量不同" << endl;return false;}if (root->_col == BLACK)++balance; if (root->_col == RED && root->_parent->_col == RED)//查看是否违反规则3，反着查{cout << "不能有连续红节点" << endl;return false;}return _IsBalance(root->_left, balance, benchmark) && _IsBalance(root->_right, balance, benchmark);//返回true/false的是给上一层的}

源码链接

刷题+代码: 刷题+代码 - Gitee.com