红黑树 学习笔记

目录

1.红黑树的概念

1.1红黑树的规则

1.2红黑树的效率

2.红黑树的实现

2.1红黑树的大致结构

2.2红黑树的插入

2.2.1红黑树插入的大致过程

2.2.2情况1：变色

2.2.3情况2：单旋＋变色

2.2.4情况3：双旋+变色

2.3红黑树的查找

---

1.红黑树的概念

红黑树是一颗搜索二叉树，相比于搜索二叉树，红黑树中的每个节点增加了一个存储位置来表示节点的颜色，可以是红色或黑色。通过对于任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因此红黑树也算比较平衡的树。

1.1红黑树的规则

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

2.根节点是黑色的

3.如果一个节点是红色的，那么该节点的两个孩子节点必须为黑色，也就是说红黑树中，任何路径都不会包含连续的红色节点。

4.对于任意一个节点，从该节点到其所有的NULL节点的简单路径上，均包含相同数量的黑色节点。

例如：

1.2红黑树的效率

假设N是红黑树中的节点数量，h为红黑树中最短路径的长度，对于 - 1 <= N <  -1， 由此可推出，红黑树增删查改最坏的情况也就是走  ，那么时间复杂度也就为 O()。

例如：

2.红黑树的实现

2.1红黑树的大致结构

enum COLOUR
{RED,BLACK
};//COLOUR 来控制每个节点的颜色template<class K, class V>
struct RBTreeNode
{pair<K, V> _value;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;COLOUR _col;//    RED/BLACKRBTreeNode(const pair<K, V>& value):_value(value), _left(nullptr), _right(nullptr), _parent(nullptr),_col(RED) // 默认为红色，因为黑色会改变路径节点数量相等规则，较为麻烦{}
};template<class K, class V>
class RBTree
{using Node = RBTreeNode<K,V>;
public://... ...
private:Node* _root = nullptr;size_t num = 0;//记录节点数量
};

2.2红黑树的插入

2.2.1红黑树插入的大致过程

1. 插入一个新节点时，按照二叉搜索树的规则进行插入，插入之后我们只需要判断是否符合红黑树的4条规则。
2. 如果是空树插入，新增加的节点为黑色节点(也就是根节点)。如果是非空树插入，新增节点必须为红色节点。因为插入黑色节点，对于红黑树的每条路径黑色节点数量均相同的规则，我们很难处理。
3. 非空树插入后，新增节点必须是红色的，如果父节点为黑色，则不违反规则，插入结束。
4. 非空树插入后，若父节点为红色节点，则违反规则，因为不能出现连续的红色节点。进一步分析为以下几种情况：

2.2.2情况1：变色

例如上述的一种情况，x节点是我们的新插入节点，很明显，x和6构成了连续的红色节点，并且此时的g为黑，u存在且为红。我们如果想要红黑树符合规则，必须将6的颜色变为黑色，但是在18->10->6->x这条路径上，就会多一个黑色节点，又会破坏规则。那么我们这么想：对于一个黑色节点，如果把该节点变为红色，同时把该节点的两个左右节点变为黑色，那么其实不会改变每一条路径上的黑色节点数量。例如：

我们将10变为红色，将6，15变为黑色。这样既满足了x与6不为连续的红色，也满足了每条路径上的黑色节点数量不变。

以上只是变色中的一种情况，同AVL树一样，如果我们将抽象图画出来，其实本质还是一样，不断往上变色，直到符合红黑树的规则即可。该情况的代码如下：

bool _Insert(const pair<K,V>& value)
{if (_root == nullptr){_root = new Node(value);_root->_col = BLACK;num++;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (value < cur->_value){parent = cur;cur = cur->_left;}else if (cur->_value < value){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(value);if (cur->_value < parent->_value){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;    //节点已经被插入，下面考察是否符合红黑树规则while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//找到父节点的父亲if (parent == grandfather->_left)//如果父亲在grandfather的左边{Node* uncle = grandfather->_right;//那么uncle就在grandfather右边if (uncle && uncle->_col == RED)//如果uncle存在并且为红色，一直往上变色即可{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//... ...

2.2.3情况2：单旋＋变色

该情况下，肯定c和p为两个连续的红色节点，但此时g为黑，u不存在或者u存在且为黑。如果u存在且为黑，那么c一定不是新插入节点，否则就会所有路径黑色节点数量不同，如果u不存在，则c一定是新插入节点。

分析：和情况1一样，这里的p必须变为黑色，才能解决连续红色节点的问题，u不存在或者存在且为黑，这里单纯的变色就无法解决问题，因此我们需要旋转＋变色。

对于上方左右两种情况，因为g为黑，因此我们进行单旋之后，g就会变成p的子树，此时我们把g变红，把p变黑即可解决问题。并且我们不需要继续向上更新，因为p已经变成这棵子树的根，且为黑色节点，一定不会和上方产生矛盾。

先看上方的图，如果c为新插入的节点，且u存在为黑，那么c左右都为空，红黑树规则就会被打破。所以c之前为黑，然后从下方子树一直往上变为红。

如果u不存在，那么c一定是新插入的节点。如果c不是新插入的节点，那么就说明插入之前就存在红黑树符合规则，所以c和p不连续为红，此时就不符合所有路径黑色节点数量相等，因为g的右边为空，所以假设不成立，c一定是新插入的节点。

然后我们再看旋转+变色之后的结果，都符合了红黑树的规则。左单旋与上面类似。

代码如下：

if (parent == grandfather->_left)
{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//情况1{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left)//情况2{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}else//情况3{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}
}

2.2.4情况3：双旋+变色

情况3还是，c，p为红，g为黑，u不存在或者存在且为黑。u不存在，c一定是新增节点，u存在且为黑，c一定不是新增节点。

这里和情况2类似，我们只考虑左边的情况(右边逻辑类似)：

我们学过AVL树都知道，尽管不变色，对于这种 < 类型的树，我们必须进行双旋，才能解决问题，< 进行 左右双旋，然后根据结果来看，我们只需要将c变为黑色，将p，g变为红色即可。

之后就是当p为g的右边，逻辑只是和上面的相反，这里就之间展示整个插入的代码：

bool _Insert(const pair<K,V>& value)
{if (_root == nullptr){_root = new Node(value);_root->_col = BLACK;num++;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (value < cur->_value){parent = cur;cur = cur->_left;}else if (cur->_value < value){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(value);if (cur->_value < parent->_value){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//插入完毕，准备检查是否为规则红黑树while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left)//如果p在g的左边{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不存在或者存在且为黑{if (cur == parent->_left)//c为p的左，右单旋+变色{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}else//c为p的右，左右双旋+变色{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}}//      g//   u     p//       c//else//p为g的右{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不存在或者存在且为黑{if (cur == parent->_right)//c为p的右，左单旋+变色{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}else//c为p的左，右左双旋+变色{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;break;}}}}_root->_col = BLACK;//无论如何，根节点都为黑色num++;//统计红黑树的节点数量return true;
}

2.3红黑树的查找

红黑树的查找和AVL树类似，查找效率为O()，代码如下：

Node* find(const K& key)
{Node* cur = _root;while (cur){if (key < cur->_value.first){cur = cur->_left;}else if (key > cur->_value.first){cur = cur->_right;}else{return cur;}}return nullptr;
}

以上内容若有错误，欢迎批评指正！