【C++】学习笔记——红黑树

文章目录

十七、红黑树
- 1.红黑树的概念
- - 红黑树的性质
- 2.红黑树节点的定义
- 3.红黑树的插入
- 4.红黑树的验证
- 5.完整代码+结果演示
- 6.红黑树与AVL树的比较
未完待续

十七、红黑树

1.红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
在这里插入图片描述

红黑树的性质

每个结点不是红色就是黑色。
根节点是黑色的。
如果一个节点是红色的，则它的两个孩子结点是黑色的。（即不存在连续的两个红色节点）
对于每个结点，从该结点到其所有后代叶结点的路径上，均包含相同数目的黑色结点。（即每条路径具有相同数量的黑色节点）
每个叶子结点都是黑色的(此处的叶子结点指的是空结点 )。空节点！！

由以上性质可知：如果存在，红黑树的最短路径是全黑色节点；最长路径则是一个黑色节点一个红色节点交替，所以红黑树才能确保没有一条路径会比其他路径长出俩倍。

2.红黑树节点的定义

红黑树节点的定义与AVL树及其相似，唯二的区别就是，红黑树没有平衡因子，红黑树有颜色值。

// 枚举颜色
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;// 颜色Color _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

为什么我们构造函数将颜色值默认设置成红色？因为我们创建的节点有两个孩子，两个孩子都是空节点，都是黑色的，如果创建的节点不把原本的这个位置的黑色空节点给替换掉，那么这条路径就会比其他路径多出一个黑色，违反了红黑树的性质。因此，新创建的节点一定是红色的。

3.红黑树的插入

先打个预防针：光靠区分节点颜色无法保证红黑树的结构，红黑树的插入在特殊情况同样需要 AVL树的旋转操作。
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
Ⅰ：按照二叉搜索的树规则插入新节点。 这步就不再多说，应该都比较熟悉。

bool Insert(const std::pair<K, V>& kv)
{// 空树则创建根节点if (_root == nullptr){_root = new Node(kv);// 红黑树的根节点是黑色的_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;// 找到新节点应该插入的位置while (cur){// 比父节点小， 往左子树找if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}// 比父节点大， 往右子树找else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{// 已经存在该值， 插入失败return false;}}cur = new Node(kv);// 父节点指向新节点if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;// 新节点指向父节点cur->_parent = parent;// ------begin------//// 修正结构和颜色//// ------end------// 保证根节点是黑色的_root->_col = BLACK;// 插入成功return true;
}

Ⅱ：检测新节点插入后，红黑树的性质是否造到破坏 。这一步非常重要，算是红黑树的精华所在。红黑树中，我们需要关注叔叔节点（父亲的兄弟）。红黑树的情况复杂，因此我们要对出现的情况进行分类讨论：
约定:cur为当前节点，p为父节点，g为爷爷节点，u为叔叔节点
①cur为红，p为红，g为黑，u存在且为红。由于新插入的节点必定是红色，但是p父节点也是红色，违反了不能出现连续红色的性质，所以我们需要进行修正颜色。由于刚好u叔叔节点是红色，所以最简单的方法就是将g爷爷节点的黑色平分到它的两个孩子，p节点和u节点，然后g节点变红即可。
在这里插入图片描述
需要注意的是：由于g节点变成了红色，可能它与它的父节点违反了规则，所以我们需要循环向上判断，直到根节点。

② cur为红，p为红，g为黑，u不存在/u存在且为黑。
在这里插入图片描述

说明:u的情况有两种
1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，那么前面肯定符合红黑树，则则cur和p一定有一个节点的颜色是黑色，此时u若不存在，则两条路径黑色数量不一致，就不满足红黑树的性质，所以u不存在，则cur一定是新插入的节点。
2.如果u节点存在，且为黑色时（红色已在①中讨论），如果cur是新插入节点，则说明原本的树就不符合红黑树性质，所以cur不是新插入的节点。

此时我们可以借助AVL树的旋转来调整结构，然后修改颜色即可。
调整结构：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转；
变色：p、g变色 —> p变黑，g变红
在这里插入图片描述

③cur为红，p为红，g为黑，u不存在/u存在且为黑。有人会说，这不跟情况②一样吗？并不是，情况②是p和cur在同侧，与u相反，而这里，p和cur并不在同侧，cur的位置偏向u，朝内的。
在这里插入图片描述
这个时候怎么办呢？当然还是借助AVL树的思想，我可以在这里进行双旋。先旋转一次，让cur朝向外侧，就变成了情况②，然后再旋转一次即可。

旋转调整结构：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转。

综上所述：我们只需要记住：
叔叔节点存在并且是红色，则不需要旋转，将爷爷节点的黑色分给父亲和叔叔，爷爷变红即可（需要向上调整)。
叔叔节点不存在或是黑色，则需要旋转。cur节点朝外就是单旋，朝内就是双旋（旋转后是不需要再向上调整的），然后进行变色处理。
最后可能会将根节点染成红色，插入结束的时候特判一下即可。
修正结构和颜色的代码：

// 修正结构和颜色
// 父亲存在且是红色
while (parent && parent->_col == RED)
{// 爷爷节点Node* grandfather = parent->_parent;// 父亲是爷爷的左if (parent == grandfather->_left){// 叔叔节点Node* uncle = grandfather->_right;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑， 叔叔节点变黑， 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 左左if (cur == parent->_left){// 右单旋 + 修正颜色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 左右else{// 左单旋父节点RotateL(parent);// 右单旋爷爷节点RotateR(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转后退出break;}}// 父亲是爷爷的右else{// 叔叔节点Node* uncle = grandfather->_left;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑， 叔叔节点变黑， 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 右右if (cur == parent->_right){// 左单旋 + 修正颜色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 右左else{// 右单旋父节点RotateR(parent);// 左单旋爷爷节点RotateL(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转后退出break;}}
}

旋转代码：

// 左左 --- 右单旋
void RotateR(Node* parent)
{// 父节点的左孩子Node* subL = parent->_left;// 父节点的左孩子的右孩子Node* subLR = subL->_right;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_left = subLR;parent->_parent = subL;// 修改父节点的左孩子的指向subL->_right = parent;subL->_parent = ppnode;// 如果父节点的左孩子的右孩子存在，则修改其指向if (subLR)subLR->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subL;else if (parent == ppnode->_left)ppnode->_left = subL;elseppnode->_right = subL;
}// 右右 --- 左单旋
void RotateL(Node* parent)
{// 父节点的右孩子Node* subR = parent->_right;// 父节点的右孩子的左孩子Node* subRL = subR->_left;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_right = subRL;parent->_parent = subR;// 修改父节点的右孩子的指向subR->_left = parent;subR->_parent = ppnode;// 如果父节点的右孩子的左孩子存在，则修改其指向if (subRL)subRL->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subR;else if (parent == ppnode->_left)ppnode->_left = subR;elseppnode->_right = subR;
}

4.红黑树的验证

我们可以根据红黑树的性质来验证我们写的红黑树代码是否有问题。红黑树的性质主要只有三个：①根节点是黑色。②没有连续的红节点。③每条路径上的黑色节点数量相同。
判断根节点颜色和找出最左侧路径的黑色节点个数：

bool IsRBT()
{// 判断根节点是否是黑色if (_root && _root->_col == RED)return false;// 计算最左路径的黑色节点数量int refBlackNum = 0;Node* cur = _root;while (cur){if(cur->_col == BLACK)refBlackNum++;cur = cur->_left;}// 检查红黑树的性质return Check(_root, 0, refBlackNum);
}

所有路径的黑色节点数量与最左侧路径比较，顺便找连续的两个红色节点：

// 检查红黑树的性质
bool Check(Node* cur, int blackNum, int refBlackNum)
{if (cur == nullptr){// 存在某条路径上黑色节点数量与最左路径的黑色节点数量不相等if (refBlackNum != blackNum){std::cout << "黑色节点的数量不相等" << std::endl;return false;}return true;}// 存在连续的红色节点if (cur->_col == RED && cur->_parent->_col == RED){std::cout << cur->_kv.first << "存在连续的红色节点" << std::endl;return false;}// 该路径黑色节点数量+1if (cur->_col == BLACK)++blackNum;// 递归子树return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);
}

中序遍历：

void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_kv.first << std::endl;_InOrder(root->_right);
}void InOrder()
{_InOrder(_root);
}

5.完整代码+结果演示

RBTree.h：

#pragma once#include <iostream>
// 枚举颜色
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;std::pair<K, V> _kv;// 颜色Color _col;RBTreeNode(const std::pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const std::pair<K, V>& kv){// 空树则创建根节点if (_root == nullptr){_root = new Node(kv);// 红黑树的根节点是黑色的_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;// 找到新节点应该插入的位置while (cur){// 比父节点小， 往左子树找if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}// 比父节点大， 往右子树找else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{// 已经存在该值， 插入失败return false;}}cur = new Node(kv);// 父节点指向新节点if (kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;// 新节点指向父节点cur->_parent = parent;// 修正祖先的颜色while (parent && parent->_col == RED){// 爷爷节点Node* grandfather = parent->_parent;if (parent == grandfather->_left){// 叔叔节点Node* uncle = grandfather->_right;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑， 叔叔节点变黑， 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 左左if (cur == parent->_left){// 右单旋 + 修正颜色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 左右else{// 左单旋父节点RotateL(parent);// 右单旋爷爷节点RotateR(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// 叔叔节点Node* uncle = grandfather->_left;// 叔叔节点存在且为红色if (uncle && uncle->_col == RED){// 父节点变黑， 叔叔节点变黑， 爷爷节点变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上修正cur = grandfather;parent = cur->_parent;}// 叔叔节点不存在或为黑色else{// 右右if (cur == parent->_right){// 左单旋 + 修正颜色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 右左else{// 右单旋父节点RotateR(parent);// 左单旋爷爷节点RotateL(grandfather);// 修正颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 保证根节点是黑色的_root->_col = BLACK;// 插入成功return true;}// 左左 --- 右单旋void RotateR(Node* parent){// 父节点的左孩子Node* subL = parent->_left;// 父节点的左孩子的右孩子Node* subLR = subL->_right;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_left = subLR;parent->_parent = subL;// 修改父节点的左孩子的指向subL->_right = parent;subL->_parent = ppnode;// 如果父节点的左孩子的右孩子存在，则修改其指向if (subLR)subLR->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subL;else if (parent == ppnode->_left)ppnode->_left = subL;elseppnode->_right = subL;}// 右右 --- 左单旋void RotateL(Node* parent){// 父节点的右孩子Node* subR = parent->_right;// 父节点的右孩子的左孩子Node* subRL = subR->_left;// 父节点的父节点Node* ppnode = parent->_parent;// 修改父节点的指向parent->_right = subRL;parent->_parent = subR;// 修改父节点的右孩子的指向subR->_left = parent;subR->_parent = ppnode;// 如果父节点的右孩子的左孩子存在，则修改其指向if (subRL)subRL->_parent = parent;// 修改父节点的父节点的指向if (parent == _root)_root = subR;else if (parent == ppnode->_left)ppnode->_left = subR;elseppnode->_right = subR;}// 中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_kv.first << std::endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}// 检查红黑树的性质bool Check(Node* cur, int blackNum, int refBlackNum){if (cur == nullptr){// 存在某条路径上黑色节点数量与最左路径的黑色节点数量不相等if (refBlackNum != blackNum){std::cout << "黑色节点的数量不相等" << std::endl;return false;}return true;}// 存在连续的红色节点if (cur->_col == RED && cur->_parent->_col == RED){std::cout << cur->_kv.first << "存在连续的红色节点" << std::endl;return false;}// 该路径黑色节点数量+1if (cur->_col == BLACK)++blackNum;// 递归子树return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);}bool IsRBT(){// 判断根节点是否是黑色if (_root && _root->_col == RED)return false;// 计算最左路径的黑色节点数量int refBlackNum = 0;Node* cur = _root;while (cur){if(cur->_col == BLACK)refBlackNum++;cur = cur->_left;}// 检查红黑树的性质return Check(_root, 0, refBlackNum);}
private:Node* _root = nullptr;
};void TestRBTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t;for (auto e : a){t.Insert(std::make_pair(e, e));}t.InOrder();std::cout << t.IsRBT() << std::endl;
}

test.cpp：

#include "RBTree.h"
#include <iostream>int main()
{TestRBTree1();return 0;
}

结果演示：
在这里插入图片描述

6.红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( $log_2 N$ )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。总而言之：红黑树插入效率更高，AVL树查找效率更高。