C++语法（20）---- 模拟红黑树
C++语法（19）---- 模拟AVL树_哈里沃克的博客-CSDN博客
https://blog.csdn.net/m0_63488627/article/details/130229501?spm=1001.2014.3001.5501
目录
1.红黑树介绍
2.模拟实现
1.枚举红黑颜色
2.节点的定义
3.树类框架
4.插入
5.检查
3.代码实现
1.红黑树介绍
最长路径不超过最短路径的两倍，近似平衡
最短：全黑
最长：一半黑一半红
1.每个节点不是红色就是黑色
2.根节点是黑色
3.如果一个节点是红色，它的两个孩子节点是黑色
4.每条路径都有相同数量的黑色节点
5.叶子节点(NIL节点)是黑的
满二叉树：全黑，或者每条路径一黑一红
较优情况：越均衡即越平衡
最差红黑树：左边全黑，右边一黑一红
较差情况：越不均衡
对比起AVL树，其实红黑树没有那么的较劲平衡，AVL的平衡得益于它不断的旋转。但是红黑树为了一些性能牺牲了平衡，减少了旋转的情况。
2.模拟实现
1.枚举红黑颜色
enum Color
{Black,Red,
};2.节点的定义
template<class K, class V>
struct BRTreeNode
{pair<K, V> _kv;BRTreeNode* _left;BRTreeNode* _right;BRTreeNode* _parent;Color _col;BRTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(Red){}
};定义一个节点时要注意其颜色：不过黑红的地位有所不同，选择决定后续的执行是否简单
选择红色：违背红色不能连续出现
选择黑色：违背整体路径黑色数量一致
我们认为选择红色更好，因为红色调节节点即可，黑色调节整个路径
3.树类框架
template<class K, class V>
class BRTree
{
private:Node* _root = nullptr;
};
4.插入
1.插入的头节点为根节点，根节点的颜色为黑色
2.普通插入的逻辑和搜索二叉树的逻辑一致
3.到这里就需判断是否两个红色节点连续，下面的问题就是调节双红色问题
调节双红色问题
情况一
插入红色节点其父节点和叔叔节点都是红色，那么我们要调整父节点和叔叔节点为黑色，不过如果只是调整这一步，那么这条树的分支就比别的树黑色节点多一个，所以我们还要更新祖父节点为红色，但是祖父为红不能保证它的父节点是黑的，所以我们仍然要往上判断
情况二
单旋加变色
叔叔节点是黑色或者不存在，如果只是把父节点变黑是不够的，因为高度超了，所以我们要用到左右旋。
情况三
双旋加变色
这样就变成了情况二
bool Insert(const 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 (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}//走到这cur就是要插入的位置//cur要连接parent，parent也要连接cur---判断靠kv的大小cur = new Node(kv);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent && parent->_col == Red){Node* grandparent = parent->_parent;//parent分在grandparent左右if (grandparent->_left == parent){//关键是看uncle节点不存在/红色/黑色的情况Node* uncle = grandparent->_right;//1.uncle红//parent和uncle变黑，grandparent变红//grandparent变红需要往上判断if (uncle && uncle->_col == Red){grandparent->_col = Red;parent->_col = uncle->_col = Black;cur = grandparent;parent = cur->_parent;}else //uncle不存在/黑色{//2.cur也是parent的左边，uncle不存在/黑色//右旋grandparents，parent变黑，if (cur == parent->_left){_RotateR(grandparent);parent->_col = Black;grandparent->_col = Red;}//3.cur是parent的右边，uncle不存在/黑色//左旋parent再右旋grandparents,cur变黑，grandparents变红else{_RotateL(parent);_RotateR(grandparent);cur->_col = Black;grandparent->_col = Red;}//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环break;}}else{Node* uncle = grandparent->_left;//1.uncle红//parent和uncle变黑，grandparent变红//grandparent变红需要往上判断if (uncle && uncle->_col == Red){grandparent->_col = Red;parent->_col = uncle->_col = Black;cur = grandparent;parent = cur->_parent;}else //uncle不存在/黑色{//2.cur也是parent的右边，uncle不存在/黑色//左旋grandparents，parent变黑，if (cur == parent->_right){_RotateL(grandparent);parent->_col = Black;grandparent->_col = Red;}//3.cur是parent的右边，uncle不存在/黑色//右旋parent再左旋grandparents,cur变黑，grandparents变红else{_RotateR(parent);_RotateL(grandparent);cur->_col = Black;grandparent->_col = Red;}//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环break;}}}_root->_col = Black;return true;
}5.检查
inspect函数
1.空树返回true
2.根节点是否是红的
3.先遍历最左边，得到这个分支的黑色节点数作为参考
check函数
1.传入参考黑色节点个数
2.计数每一分支的黑色节点数，递归到底部，可对照节点数是否满足
3.递归遍历看看有没有连续的红色节点
private:
bool check(Node* root, size_t& reference, size_t num)
{if (root == nullptr){if (num != reference){cout << "路径长度有问题" << endl;return false;}return true;}if (root->_col == Red && root->_parent && root->_parent->_col == Red){cout << "节点连续红色" << endl;return false;}if (root->_col == Black)num++;return check(root->_left, reference, num) && check(root->_right, reference, num);
}bool _Inspect(Node* root)
{//空树也是红黑树if (_root == nullptr)return true;//检测根节点是否为黑色if (_root->_col != Black){cout << "根节点是红色的" << endl;return false;}size_t leftNum = 0;Node* cur = _root;while (cur){if (cur->_col == Black)leftNum++;cur = cur->_left;}//检测所有路径黑色节点的数量是否一样//检测相邻节点是不是都是红色的return check(_root, leftNum, 0);
}3.代码实现
#pragma once
#include<iostream>
#include<assert.h>
#include <stdlib.h>
#include<time.h>
using namespace std;enum Color
{Black,Red,
};template<class K, class V>
struct BRTreeNode
{pair<K, V> _kv;BRTreeNode* _left;BRTreeNode* _right;BRTreeNode* _parent;Color _col;BRTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(Red){}
};template<class K, class V>
class BRTree
{
public:typedef BRTreeNode<K, V> Node;bool Insert(const 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 (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}//走到这cur就是要插入的位置//cur要连接parent，parent也要连接cur---判断靠kv的大小cur = new Node(kv);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent && parent->_col == Red){Node* grandparent = parent->_parent;//parent分在grandparent左右if (grandparent->_left == parent){//关键是看uncle节点不存在/红色/黑色的情况Node* uncle = grandparent->_right;//1.uncle红//parent和uncle变黑，grandparent变红//grandparent变红需要往上判断if (uncle && uncle->_col == Red){grandparent->_col = Red;parent->_col = uncle->_col = Black;cur = grandparent;parent = cur->_parent;}else //uncle不存在/黑色{//2.cur也是parent的左边，uncle不存在/黑色//右旋grandparents，parent变黑，if (cur == parent->_left){_RotateR(grandparent);parent->_col = Black;grandparent->_col = Red;}//3.cur是parent的右边，uncle不存在/黑色//左旋parent再右旋grandparents,cur变黑，grandparents变红else{_RotateL(parent);_RotateR(grandparent);cur->_col = Black;grandparent->_col = Red;}//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环break;}}else{Node* uncle = grandparent->_left;//1.uncle红//parent和uncle变黑，grandparent变红//grandparent变红需要往上判断if (uncle && uncle->_col == Red){grandparent->_col = Red;parent->_col = uncle->_col = Black;cur = grandparent;parent = cur->_parent;}else //uncle不存在/黑色{//2.cur也是parent的右边，uncle不存在/黑色//左旋grandparents，parent变黑，if (cur == parent->_right){_RotateL(grandparent);parent->_col = Black;grandparent->_col = Red;}//3.cur是parent的右边，uncle不存在/黑色//右旋parent再左旋grandparents,cur变黑，grandparents变红else{_RotateR(parent);_RotateL(grandparent);cur->_col = Black;grandparent->_col = Red;}//抽象树的头被设置为黑色，对上面没有影响，所以不需要进行循环break;}}}_root->_col = Black;return true;}void Print(){_Print(_root);cout << endl;}bool Inspect(){return _Inspect(_root);}private: bool check(Node* root, size_t& reference, size_t num){if (root == nullptr){if (num != reference){cout << "路径长度有问题" << endl;return false;}return true;}if (root->_col == Red && root->_parent && root->_parent->_col == Red){cout << "节点连续红色" << endl;return false;}if (root->_col == Black)num++;return check(root->_left, reference, num) && check(root->_right, reference, num);}bool _Inspect(Node* root){//空树也是红黑树if (_root == nullptr)return true;//检测根节点是否为黑色if (_root->_col != Black){cout << "根节点是红色的" << endl;return false;}size_t leftNum = 0;Node* cur = _root;while (cur){if (cur->_col == Black)leftNum++;cur = cur->_left;}//检测所有路径黑色节点的数量是否一样//检测相邻节点是不是都是红色的return check(_root, leftNum, 0);}void _Print(Node*& cur){if (cur == nullptr)return;_Print(cur->_left);cout << cur->_kv.first << " ";_Print(cur->_right);}void _RotateL(Node*& parent){Node* pparent = parent->_parent;Node* SubR = parent->_right;Node* SubRL = SubR->_left;if (pparent == nullptr){_root = SubR;SubR->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = SubR;elsepparent->_right = SubR;SubR->_parent = pparent;}parent->_parent = SubR;SubR->_left = parent;parent->_right = SubRL;if (SubRL != nullptr)SubRL->_parent = parent;}void _RotateR(Node*& parent){Node* pparent = parent->_parent;Node* SubL = parent->_left;Node* SubLR = SubL->_right;if (pparent == nullptr){_root = SubL;SubL->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = SubL;elsepparent->_right = SubL;SubL->_parent = pparent;}parent->_parent = SubL;SubL->_right = parent;parent->_left = SubLR;if (SubLR != nullptr)SubLR->_parent = parent;}Node* _root = nullptr;
};
