信誉好的购物网站建设,呼和浩特市城乡建设保障局网站,十大全屋整装公司排名,公共资源交易网文章目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树的插入五、代码实现一、红黑树的概念
红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上…
文章目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树的插入五、代码实现一、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的 。既最长路径长度不超过最短路径长度的 2 倍
ps:树的路径是从根节点走到空节点此处为NIL 节点才算一条路径 二、红黑树的性质 每个结点不是红色就是黑色 根结点是黑色的 如果一个结点是红色的则它的两个孩子结点是黑色的没有连续的红色结点 对于每个结点从该节点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 每个叶子结点都是黑色的此处的叶子结点指的是空节点,NIL节点如果是空树空节点也是黑色符合第一个性质
理解最长路径长度不超过最短路径长度的 2 倍 根据第三个性质红黑树不会出现连续的红色结点根据第四个性质从每个结点到所有后代结点的路径上包含相同数目的黑色结点。 极端场景最短路径上全黑一条路径黑色节点的数量最长路径上是一黑一红相间的路径 三、红黑树节点的定义
三叉链结构对比AVL数节点的定义把平衡因子替换成节点颜色采用枚举的方式
//结点颜色
enum Color
{RED,BLACK,
};templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};这里可以清楚的看到构造结点时默认设置为红色,问题来了 如果插入的是黑色结点那就是不符合第四个性质路径上均包含相同的黑色结点此时我们必须要去进行维护每条路径的黑色结点 如果插入的是红色结点那就是不符合第三个性质没有出现连续的红色结点但是我们并不一定需要调整如果根刚好为黑色就不需要进行调整。 所以如果插入为红色结点不一定会破坏结构但是如果插入黑色结点我们就必须去进行维护了 四、红黑树的插入
红黑树插入的操作部分和AVL树的插入一样
找到待插入位置将待插入结点插入到树中调整若插入结点的父结点是红色的我们就需要对红黑树进行调整
前两步大差不差
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
关键在于对红黑树进行调整为了能够展示出各种情况这里有一个基本的模型 约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
情况一cur为红p为红g为黑u存在且为红 :
cur为红p为红g为黑u存在且为红 关键看u结点根结点的颜色为黑色不能有连续的红色结点所以上面的情况已经出现连续的红色结点了此时我们需要进行调整
把p结点改为黑色同时把u结点也改为黑色符合性质四每条路径上的黑色节点数量相同最后在把g结点改为红色如果g是子树的话g一定会有双亲为了维持每条路径上黑色节点的数量g必须变红不然会多出一个黑色节点在把g结点当做cur结点继续往上调整当g为根结点时在把g置为黑色 代码实现 while (parent parent-_col RED){Node* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;//情况一u存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;cur grandfater;parent cur-_parent;}else//其他情况{}}else//parentgrandfater-_right{Node* uncle grandfater-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;cur grandfater;parent cur-_parent;}else{}}}_root-_col BLACK;情况二cur为红p为红g为黑u不存在/u为黑gpc在同一侧 此时u的情况 如果u结点不存在则cur一定是新增结点因为如果cur不是新增结点则cur和p一定有一个节点时黑色就不满足每条路径都有相同的黑色结点的性质。 如果u结点存在则其一定是黑色的那么c节点原来的颜色一定是黑色在其子树调整过程中变为了红色 如果p为g的左孩子cur为p的左孩子则进行右单旋转
如果p为g的右孩子cur为p的右孩子则进行左单旋转
同时p、g变色–p变黑g变红
以下情况u不存在cur为新增节点进行右单旋 以下情况u结点存在且为黑 情况三: cur为红p为红g为黑u不存在/u为黑gpc不在同一侧: 这时候我们就需要进行双旋了 p为g的左孩子cur为p的右孩子对p做左单旋转 p为g的右孩子cur为p的左孩子对p做右单旋转; 旋转之后则转换成了情况2在继续进行调整即可 五、代码实现
送上源码
#pragma once
#include iostream
#include assert.h
#include time.h
using namespace std;
enum Color
{RED,BLACK,
};
templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};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-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED){Node* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;//情况一u存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;//向上调整cur grandfater;parent cur-_parent;}else{//情况2if (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}//情况3else{// g// p// c RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else//parentgrandfater-_right{Node* uncle grandfater-_left;//情况1u存在且为红色if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfater-_col RED;//向上调整cur grandfater;parent cur-_parent;}else{//情况2u不存在/u存在为黑色//g// p// cif (cur parent-_right){RotateL(grandfater);grandfater-_col RED;parent-_col BLACK;}//情况3// g// p// celse{RotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}//根变黑_root-_col BLACK;return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{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-_parent subL;subL-_right parent;if (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}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);}bool Check(Node*root,int blackNum,int ref){if (root nullptr){//cout blackNum endl;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);}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}int ref 0;Node* left _root;while (left){if (left-_col BLACK){ref;}left left-_left;}return Check(_root,0,ref);}
private:Node* _root nullptr;
};void TestRBTree1()
{//int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout t.IsBalance() endl;
}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;}本篇结束…
