石家庄微网站建设公司哪家好,wordpress语言包更新,天津红桥网站建设,wordpress+纯静态插件目录
一、红黑树的概念
二、红黑树的性质
三、红黑树节点的定义
四、红黑树的插入
五、红黑树的验证
六、红黑树与AVL树的比较
七、完整代码 一、红黑树的概念 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可…目录
一、红黑树的概念
二、红黑树的性质
三、红黑树节点的定义
四、红黑树的插入
五、红黑树的验证
六、红黑树与AVL树的比较
七、完整代码 一、红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的 如下图就是一棵红黑树 二、红黑树的性质
红黑树有以下性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的即没有连续红色节点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点如上图的NIL节点)红黑树最优情况左右平衡全黑或每条路径都是一黑一红相间的满二叉树搜索高度 logN红黑树最差情况左右极不平衡每颗子树左子树全黑右子树一黑一红搜索高度 2*logN红黑树不追求极致的平衡AVL树则是追求极致的平衡红黑树是近似平衡红黑树这种近似平衡的结构大大减少了大量的旋转红黑树的综合性能优于 AVL树
为什么红黑树满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍
红黑树的最短路径全黑一条路径上的全是黑色节点红黑树的最长路径一黑一红相间的路径
比如 三、红黑树节点的定义 红黑树也是使用键值对即KV模型也是为了方便后序操作红黑树的结构也是三叉链即增加了指向父节点的 parent指针还增加了一个成员变量用于标识节点的颜色red or black
enum Colour
{RED,BLACK,
};//K:key, V:value
templateclass K, class V
struct RBTreeNode
{//构造函数RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}//成员变量pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:private:Node* _root nullptr;//缺省值
};注这里使用了枚举来列举颜色
为什么构造红黑树结点时默认将结点的颜色设置为红色
插入结点如果是黑色的一定破坏红黑树的性质4无论如何都必须对红黑树进行调整。插入结点如果是红色的可能破坏红黑树的性质3可能需要对红黑树进行调整 或者不需要调整
所以将节点颜色默认设置为红色
四、红黑树的插入
红黑树的插入分两步
按照二叉搜索树的方式插入新节点判断是否需要对红黑树进行调整
1插入节点
因为红黑树本身就是一棵二叉搜索树因此寻找结点的插入位置是非常简单的按照二叉搜索树的插入规则 待插入结点的key值比当前结点小就插入到该结点的左子树待插入结点的key值比当前结点大就插入到该结点的右子树待插入结点的key值与当前结点的 key 值相等就插入失败
2判断是否需要对红黑树进行调整
判断插入节点的父亲 parent 存在且为红色则需要进行调整否则不需要
然后分两种情况
Aparent在 grandfather 的左边Bparent在 grandfather 的右边注进行调整的关键是 uncle Aparent在 grandfather 的左边有三种情况 情况1uncle存在且为红uncle和parent的颜色需要修改为黑granfather 修改为红如果满足循环条件继续往上更新情况2uncle存在且为黑需要对红黑树进行旋转情况3uncle不存在需要对红黑树进行旋转情况1图如下 注情况2和情况3是一起处理的
情况2 情况3
curparentgrandfather 三个节点在一条直线上单旋处理即可对 grandfater 进行右单旋然后 parent 的颜色改为黑grandfater 的颜色改为红curparentgrandfather 三个节点是折线需要双旋处理对 parent 进行左单旋然后对 grandfater 进行右单旋然后 cur 的颜色改为黑grandfater 的颜色改为红
情况2图如下
curparentgrandfather 三个节点在一条直线上 调颜色 curparentgrandfather 三个节点是折线 调颜色 情况3图如下
curparentgrandfather 三个节点在一条直线上 调颜色 curparentgrandfather 三个节点是折线 调颜色 Bparent在 grandfater 的右边也有三种情况与左边情况完全一致只是旋转不同 情况1uncle存在且为红uncle和parent的颜色需要修改为黑grandfater修改为红如果满足循环条件继续往上更新情况2uncle存在且为黑需要对红黑树进行旋转对 grandfather 进行右单旋情况3uncle不存在需要对红黑树进行双旋转对 parent 进行左单旋然后对 grandfather 进行右单旋注情况2和情况3是一起处理的
情况2 情况3
curparentgrandfather 三个节点在一条直线上单旋处理即可对 grandfather 进行左单旋然后 parent 的颜色改为黑grandfater 的颜色改为红curparentgrandfather 三个节点是折线需要双旋处理对 parent 进行右单旋然后对 grandfather 进行左单旋然后 cur 的颜色改为黑grandfather 的颜色改为红
图就不画了左边的图反过来就是右边的图旋转在 AVL树有解释这里就不再解释
经调整后保持了红黑树的特性
插入代码如下
//插入
bool Insert(const pairK, 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;}else//cur-kv.first kv.first要插入值已经存在插入失败{return false;}}cur new Node(kv);cur-_col RED;//新节点默认为红//插入if (parent-_kv.first kv.first)//插入到parent左边{parent-_right cur;cur-_parent parent;}else//插入到parent右边{parent-_left cur;cur-_parent parent;}//进行调平衡 保持红黑树的特性即插入节点的父亲是红色需要对红黑树进行调整while (parent parent-_col RED)//parent存在且为红 进行调整{Node* grandfather parent-_parent;//1parent在grandfater的左边//2parent在grandfater的右边if (parent grandfather-_left)//parent在grandfater的左边{//情况1uncle存在且为红uncle和parent的颜色需要修改为黑grandfater修改为红如果满足循环条件继续往上更新//情况2uncle存在且为黑需要对红黑树进行旋转//情况3uncle不存在需要对红黑树进行旋转//注情况2和情况3是一起处理的Node* uncle grandfather-_right;if (uncle uncle-_col RED)//情况1{//修改颜色uncle-_col parent-_col BLACK;grandfather-_col RED;//迭代往上更新cur grandfather;parent cur-_parent;}else//情况2 情况3{if (cur parent-_left)//curparentgrandfater三个节点在一条直线上单旋处理即可{RotateR(grandfather);//右单旋parent-_col BLACK;grandfather-_col RED;}else//curparentgrandfater三个节点是折线需要双旋处理{RotateL(parent);//左单旋RotateR(grandfather);//右单旋cur-_col BLACK;grandfather-_col RED;}break;//旋转后该子树的根变成了黑色符合红黑树的特性无需继续往上处理}}else//parent在grandfater的右边{//在右边 也是上面左边的三种情况Node* uncle grandfather-_left;if (uncle uncle-_col RED)//情况1{//修改颜色uncle-_col parent-_col BLACK;grandfather-_col RED;//迭代往上更新cur grandfather;parent cur-_parent;}else//情况2 情况3{if (cur parent-_right)//curparentgrandfater三个节点在一条直线上单旋处理即可{RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else//curparentgrandfater三个节点是折线需要双旋处理{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后该子树的根变成了黑色符合红黑树的特性无需继续往上处理}}}_root-_col BLACK;//根的颜色需要变为黑原因是可能情况1会把根节点变红return true;
}
注红黑树其他接口就不实现了在面试考的花也是考查红黑树的插入即红黑树如何调平衡
五、红黑树的验证
红黑树的检测分为两步
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质
1中序检查
//中序遍历
void InOrder()
{_InOrder(_root);
}void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);
}
2检查红黑树特性
//检查红黑树特性
bool IsBalance()
{if (_root nullptr){return true;}if (_root-_col ! BLACK){cout 违反规则根节点不为黑色 endl;return false;}Node* left _root;int ref 0;//用于一条路径上记录黑色节点的数量while (left)//求一条路径的黑色节点{if (left-_col BLACK){ref;}left left-_left;}return Check(_root, 0, ref);
}//检查每条路径的黑色节点是否相等 是否出现连续红色节点
bool Check(Node* root, int blackNum, int ref)
{if (root nullptr){if (blackNum ! ref){cout 违反规则本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);
}
六、红黑树与AVL树的比较 红黑树和 AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(logN)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比 AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多
红黑树的应用
C STL库 -- map/set、mutil_map/mutil_setJava 库linux内核其他一些库
七、完整代码 RBTree.h #pragma onceenum Colour
{RED,BLACK,
};//K:key, V:value
templateclass K, class V
struct RBTreeNode
{//构造函数RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}//成员变量pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public://插入bool Insert(const pairK, 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;}else//cur-kv.first kv.first要插入值已经存在插入失败{return false;}}cur new Node(kv);cur-_col RED;//新节点默认为红//插入if (parent-_kv.first kv.first)//插入到parent左边{parent-_right cur;cur-_parent parent;}else//插入到parent右边{parent-_left cur;cur-_parent parent;}//进行调平衡 保持红黑树的特性即插入节点的父亲是红色需要对红黑树进行调整while (parent parent-_col RED)//parent存在且为红 进行调整{Node* grandfather parent-_parent;//1parent在grandfater的左边//2parent在grandfater的右边if (parent grandfather-_left)//parent在grandfater的左边{//情况1uncle存在且为红uncle和parent的颜色需要修改为黑grandfater修改为红如果满足循环条件继续往上更新//情况2uncle存在且为黑需要对红黑树进行旋转//情况3uncle不存在需要对红黑树进行旋转//注情况2和情况3是一起处理的Node* uncle grandfather-_right;if (uncle uncle-_col RED)//情况1{//修改颜色uncle-_col parent-_col BLACK;grandfather-_col RED;//迭代往上更新cur grandfather;parent cur-_parent;}else//情况2 情况3{if (cur parent-_left)//curparentgrandfater三个节点在一条直线上单旋处理即可{RotateR(grandfather);//右单旋parent-_col BLACK;grandfather-_col RED;}else//curparentgrandfater三个节点是折线需要双旋处理{RotateL(parent);//左单旋RotateR(grandfather);//右单旋cur-_col BLACK;grandfather-_col RED;}break;//旋转后该子树的根变成了黑色符合红黑树的特性无需继续往上处理}}else//parent在grandfater的右边{//在右边 也是上面左边的三种情况Node* uncle grandfather-_left;if (uncle uncle-_col RED)//情况1{//修改颜色uncle-_col parent-_col BLACK;grandfather-_col RED;//迭代往上更新cur grandfather;parent cur-_parent;}else//情况2 情况3{if (cur parent-_right)//curparentgrandfater三个节点在一条直线上单旋处理即可{RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else//curparentgrandfater三个节点是折线需要双旋处理{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后该子树的根变成了黑色符合红黑树的特性无需继续往上处理}}}_root-_col BLACK;//根的颜色需要变为黑原因是可能情况1会把根节点变红return true;}//中序遍历void InOrder(){_InOrder(_root);}//检查红黑树特性bool IsBalance(){if (_root nullptr){return true;}if (_root-_col ! BLACK){cout 违反规则根节点不为黑色 endl;return false;}Node* left _root;int ref 0;//用于一条路径上记录黑色节点的数量while (left)//求一条路径的黑色节点{if (left-_col BLACK){ref;}left left-_left;}return Check(_root, 0, ref);}
private://检查每条路径的黑色节点是否相等 是否出现连续红色节点bool Check(Node* root, int blackNum, int ref){if (root nullptr){if (blackNum ! ref){cout 违反规则本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//进行链接parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;//记录parent节点的前一个节点subR-_left parent;parent-_parent subR;if (ppNode nullptr)//即subR已经是根节点{_root subR;_root-_parent nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode-_left parent)//parent原本在 ppNode 的左边{ppNode-_left subR;}else//parent原本在 ppNode 的右边{ppNode-_right subR;}subR-_parent ppNode;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//进行链接parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppNode parent-_parent;//记录parent节点的前一个节点subL-_right parent;parent-_parent subL;if (ppNode nullptr)//即subL已经是根节点{_root subL;subL-_parent nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode-_left parent)//parent原本在 ppNode 的左边{ppNode-_left subL;}else//parent原本在 ppNode 的右边{ppNode-_right subL;}subL-_parent ppNode;}}
private:Node* _root nullptr;//缺省值
};Test.cpp #include iostream
using namespace std;
#include RBTree.hvoid TestRBTree1()
{//int arr[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint, int t;for (auto e : arr){t.Insert(make_pair(e, e));}t.InOrder();
}void TestRBTree2()
{srand(time(0));//随机数种子const size_t N 100000;RBTreeint, int t;for (size_t i 0; i N; i){size_t x rand();t.Insert(make_pair(x, x));//cout t.IsBalance() endl;}cout t.IsBalance() endl;
}int main()
{TestRBTree2();return 0;
}
----------------我是分割线---------------
文章到这里就结束了下一篇即将更新
