红黑树的概念
红黑树是一种二叉搜索树 但在每个结点上增加一个存储位表示结点的颜色 可以是Red或Black
通过对任何一条从根到叶子的路径上各个结点着色方式的限制 红黑树确保没有一条路径会比其他路径长
出两倍 因而是接近平衡的
红黑树的性质
红黑树有以下五点性质
1根节点是黑色的
2每个节点不是黑色就是红色
3如果一个节点是红色的 那么它的两个子节点就是黑色的
4对于每个节点 从该节点到其所有后代节点的简单路径上 均包含相同数目的黑色节点
5每个叶子节点都是黑色的 （这里的叶子节点指的是空节点）
6了解了上面这五条性质之后我们这里抛出一个问题
红黑树是如何确保 没有一条路径会比其他路径长出两倍 这个性质的呢？
下面是关于这个问题的解答
根据红黑树的性质三 我们可以推断出不会有连续存在的红节点
根据红黑树的性质四 我们可以推断出每一条路径上的黑色节点数目相同
结合我们的推断一 和 推断二 我们可以得出以下的结论
红黑树的最短路径一定是全黑的
红黑树的最长路径一定是红黑相间的
再根据上面的结论一和结论二 我们假设最短路径的长度是N 那么最长路径的长度就是2N
所以我们现在就能得出结论 没有一条路径会比其他路径长出两倍
红黑树节点的定义
我们这里实现KV模型三叉链结构的红黑树 此外增加一个成员变量颜色来控制红黑
关于颜色的成员变量 我们可以使用之前学过的枚举来解决
enum Colour { RED, BLACK };
那么接下来我们只需要定义一个枚举变量来控制颜色就好了
红黑树节点类的定义如下
template<class K,class V> class RBTreeNode { public: // 三叉链 RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; // 默认插入颜色为红 至于为什么 后面会解释 Colour _col; // 储存键值对 pair<K, V> _kv; RBTreeNode(const pair<K,V>& kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv) { } private: };
那么再这里我们再详细解释一下这句代码 也就是为什么_col默认设置为红
_col(RED)
首先 我们回顾下红黑树的性质四
对于每个节点 从该节点到其所有后代节点的简单路径上 均包含相同数目的黑色节点
也就是说 假如我们插入的是黑色的节点
那么势必会造成插入的节点路径上的黑色节点变多了
那么根据上面的性质四 我们就要更新所有路径上的黑色节点数目以保持红黑树的性质
其次 我们来回顾下红黑树的性质三
如果一个节点是红色的 那么它的两个子节点就是黑色的
也就是说 假设我们插入的是红色的节点
如果它的父节点是黑色 那么插入之后仍然满足红黑树的性质
如果它的父节点是红色 那么此时我们需要调整整颗树使其满足红黑树的性质
综上所述 我们在选择默认插入节点为红色的时候 需要调整的次数较少 插入较为方便 故而插入节点默认选红
红黑树的插入
红黑树的插入逻辑总共分为三步
1按照二叉搜索树的插入规则找到待插入节点
2将待插入节点插入到树中
3如果插入节点的父节点为红色 则执行调整操作 若为黑色 则无需操作
前面两点和二叉搜索树的插入操作相同 所以说我们插入操作的关键在如何实现第三点
我们来看具体的情况
假设插入节点的父节点为黑色
那么我们找到位置之后直接插入红色节点即可 因为插入红色节点之后不会破坏红黑树的性质
假设插入节点的父节点为红色
那么这个时候就有点复杂了 因为根据红黑树的性质三 我们可以推断出 是不可能存在两个连续的红色节点的
所以说这个时候我们必须要对红黑树进行调整 来让这棵树继续满足红黑树的性质
至于红黑树应该怎么调整 这里分为三种情况来讨论
情况一
插入节点的叔叔节点存在 且插入节点的叔叔节点的颜色为红色
注： 我们将插入节点称为cur
将其父节点称为 p
将与其父节点平辈的节点称为 u
将其父亲的父亲节点称为 g
示例图如下
此时 为了避免连续的红色节点 我们将cur的父亲和叔叔节点都变成黑色
这时候还没有完 由于我们将父亲节点和叔叔几点都变成了黑色 此时这条路径上的黑色节点多了一个
要变成原来的黑色节点个数 我们必须要减少一个黑色节点的数量
此时 我们只需要将它的爷爷节点变成红色就可以
但是这种情况下又会出现一种问题
在爷爷节点并不是根节点的情况下 有可能爷爷节点的父节点还是红色
这样就破坏了 红黑树的性质三
所以说此时我们需要将爷爷节点当作是新插入的节点 再根据不同的情况继续向上调整
情况二
插入节点的叔叔节点存在 并且插入节点的叔叔节点的颜色为黑色
我们首先来看示例图
假设cur是新增节点
如图 我们选择了两条路线对于这两条路线来说 根节点走到爷爷节点之前 由于走的是同一条路线
所以说黑色节点的数目都是相同的 而当我们从爷爷节点开始找黑色节点
则左边一定是只有两个黑色节点 （爷爷节点和最后的空节点）
而右边由于叔叔节点的存在一定是大于等于三个黑色节点的
所以说此时不满足性质四
所以我们可以得出结论cur一定不是新增节点
那么既然cur不是新增节点 那么就只有一种可能了 cur是由我们的情况一变换而来
此时的这种情况 我们通过变色操作已经处理不了了 只能通过旋转
如果说祖孙三代在同一条直线上 则我们只需要执行单旋操作就可以
操作图如下
当然 如果祖孙三在右边就执行左单旋操作
如果祖孙三代是一条折线就执行双旋操作
就像下面这样子
如果出现这种情况就执行左右双旋
图片表示如下
这里我们是不是发现和上面右单旋的情况类似了 之后只要执行下右单旋 然后变色就行了
当然 如果祖孙三代的折线方向与上面相反就执行右左双旋操作
情况三
插入节点的叔叔不存在
此时一定是新增节点而出现的情况
因为如果是由情况一变化而来 则下面父亲节点下面必定有黑色节点 此时不满足红黑树的性质四
在这种情况我们还是一样 分为直线和折线情况讨论
像上面这张图一样的偏左直线则我们执行右单旋然后变色
当然 如果祖孙三在右边就执行左单旋操作
如果出现这种折线情况则指向左右双旋操作
这里我们是不是发现和上面右单旋的情况类似了 之后只要执行下右单旋 然后变色就行了
当然 如果祖孙三代的折线方向与上面相反就执行右左双旋操作
完整的红黑树插入代码如下
//右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* parentParent = parent->_parent; //建立subLR与parent之间的联系 parent->_left = subLR; if (subLR) subLR->_parent = parent; //建立parent与subL之间的联系 subL->_right = parent; parent->_parent = subL; //建立subL与parentParent之间的联系 if (parentParent == nullptr) { _root = subL; _root->_parent = nullptr; } else { if (parent == parentParent->_left) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } } //左右双旋 void RotateLR(Node* parent) { RotateL(parent->_left); RotateR(parent); } //右左双旋 void RotateRL(Node* parent) { RotateR(parent->_right); RotateL(parent); } pair<Node*, bool> Insert(const pair<K, V>& kv) { // 先考虑空树的情况 if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; // 因为我们默认插入节点的颜色是红色 而根节点是黑色 所以说要特殊处理 return make_pair(_root, true); } // 如果不是空树则按照二叉搜索树的方法找到待插入的位置 //1、按二叉搜索树的插入方法，找到待插入位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (kv.first < cur->_kv.first) //待插入节点的key值小于当前结点的key值 { //往该节点的左子树走 parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) //待插入节点的key值大于当前结点的key值 { //往该节点的右子树走 parent = cur; cur = cur->_right; } else //待插入节点的key值等于当前节点的key值 { return make_pair(cur, false); //插入失败 // 唯一需要注意的一点 我们要返回插入失败位置的迭代器 } } // 将待插入的节点插入到树中 cur = new Node(kv); Node* newnode = cur;// 记录新插入的节点 if (kv.first < parent->_kv.first) //新节点的key值小于parent的key值 { //插入到parent的左边 parent->_left = cur; cur->_parent = parent; } else //新结点的key值大于parent的key值 { //插入到parent的右边 parent->_right = cur; cur->_parent = parent; } // 如果父节点是红色 则开始对红黑树进行处理 while (parent && parent->_col == RED) { Node* grandfather = parent->parent; // 因为parent是红色 所以说它一定存在父节点 if (parent == grandfather->_left) // parent是grandfather的左 { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) // 对应情况一 { // 颜色调整 parent->_col == BLACK; uncle->_col == BLACK; grandfather->_col = RED; // 继续往上处理 cur = parent; parent = cur->_parent; } else // 对应情况二和情况三 { if (cur == parent->_left) { RotateR(grandfather); // 右单旋 // 颜色调整 grandfather->_col = RED; parent->_col = BLACK; } else { RotateLR(grandfather); // 左右双旋 // 颜色调整 grandfather->_col = RED; cur->_col = BLACK; } } break; } else //parent是grandfather的右孩子 { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) // 对应情况一 { parent->_col = BLACK; uncle->_col = RED; cur = parent; parent = cur->_parent; } else { if (cur == parent->_left) { RotateRL(grandfather); // 颜色调整 cur->_col = BLACK; grandfather->_col = RED; } else { RotateL(grandfather); // 颜色调整 grandfather->_col = RED; parent->_col = BLACK; } break; } } _root->_col = BLACK; // 根节点有可能被情况一改成红色 以防万一 return make_pair(newnode, true); //插入成功 } }
红黑树的验证
红黑树首先一棵二叉搜索树 所以说我如果我们中序遍历之 则其是有序的
代码如下
void _Inorder(Node* root) { // 先考虑中止条件 Node* cur = _root; if (cur == nullptr) { return; } _Inorder(cur -> _left); cout << cur->_kv.first << " : " << cur->_kv.second << endl; _Inorder(cur->_right); }
此外它还需要满足红黑树的所有性质 验证代码如下
bool ISRBTree() { if (_root == nullptr) { return true; } if (_root->_col == RED) { cout << "error：根结点为红色" << endl; return false; } // 找出最左路径的黑色节点作为参考值 Node* cur = _root; int balckcount = 0; while (cur) { if (cur->_col == BLACK) { count++; } cur = cur->_left; } int count = 0; return _ISRBTree(_root, count, balckcount); } bool _ISRBTree(Node* root, int count, int blackcount) { if (root == nullptr) { return count == blackcount; } if (root->_col == RED && root->_parent == RED) { return false; } if (root->_col ==BLACK) { count++; } return _ISRBTree(root->_left, count, blackcount) && _ISRBTree(root->right, count, blackcount); }
红黑树的查找
红黑树的查找和二叉搜索树的查找类似
1如果查找的树是空树 则查找失败
2如果key值小于当前节点的值 则向左查找
3如果key值大于当前节点的值 则向右查找
4如果key值等于当前节点的值 则返回当前节点指针
代码如下
//查找函数 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key < cur->_kv.first) //key值小于该结点的值 { cur = cur->_left; //在该结点的左子树当中查找 } else if (key > cur->_kv.first) //key值大于该结点的值 { cur = cur->_right; //在该结点的右子树当中查找 } else //找到了目标结点 { return cur; //返回该结点 } } return nullptr; //查找失败 }
红黑树的删除
红黑树的删除满足下面几个步骤
1遵循二叉搜索树的删除原则 找到待删除位置
2找到删除位置之后 删除节点
3看看删除后的二叉树是否是红黑树 如果不是调整之
红黑树的删除并不是我们学习的重点内容 这里也是和AVL树一样跳过
红黑树与AVL树的比较
红黑树和AVL树都是很高效的AVL树 它们增删查改的时间复杂度都是Log（N）
但是它们实现控制二叉树平衡的方式不同
AVL树通过平衡因子来实现二叉搜索树的严格平衡
红黑树通过颜色来实现二叉搜索树的近似平衡
比起AVL树 红黑树的插入需要更少的旋转操作 所以说来经常增删的场景中红黑树更优
而由于它们查找的效率都很高 所以说AVL树优的查找的那一点优势并不算什么
所以说实际场景中红黑树用的更多一点
