深圳办公室装修哪家好,seo站长工具,重庆网站推广系统,做企业网站好的红黑树 红黑树的概念红黑树的性质红黑树结点的定义红黑树的插入红黑树的验证红黑树与AVL树的比较 红黑树的概念
红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上… 红黑树 红黑树的概念红黑树的性质红黑树结点的定义红黑树的插入红黑树的验证红黑树与AVL树的比较 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 从性质34可以得出一棵红黑树的最短可能路径就是全为黑结点即为N 而最长可能路径就是由一黑一红结点构成的路径该路径当中黑色结点与红色结点的数目相同即长度为2N
红黑树结点的定义
红黑树结点的定义其实和AVL树差不多只不过红黑树结点少了平衡因子多了颜色。
//枚举结点颜色
enum color
{RED,BLACK
};
template class K, class V
struct RBTreeNode
{//三叉链结构RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;//存储的键值对pairK, V _kv;//结点颜色color _col;//构造函数RBTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};为什么构造结点时默认将结点的颜色设置为红色 我们可以发现红黑树的有一条性质是所有路径黑色结点的数目都相等如果欧姆尼新插入的结点默认为黑色就会破坏这条性质我们就需要对红黑树进行调整。
如果我们插入的是红结点此时如果父结点是红结点我们就需要进行调整如果父结点是黑结点我们就不需要进行调整。
红黑树的插入
红黑树的插入步骤分为以下三步
根据二叉搜索树的性质找到待插入位置在待插入位置插入新结点如果父结点为红色就进行调整。
我们可以发现前两步其实AVL树没有区别我们只要在第三步进行调整就可以了。 那么怎么对红黑树插入结点进行调整呢 如果我们插入结点的父结点是黑色的我们就不需要进行任何调整因为这并没有破坏红黑树的性质如果我们插入结点的父结点是红结点我们就需要对红黑树进行调整了。
插入结点的父结点为红色就说明祖父结点一定存在且为黑色对红黑树的调整主要是对叔叔结点的调整。
红黑树的调整一共分为三种方式 1.cur为红p为红g为黑u存在且为红 插入结点为红父结点为红我们需要将父结点与叔叔结点都调整为黑色然后将祖父结点调整为红色如果此时g这棵树不为子树就再将祖父结点调整为黑色
对应的抽象图如下 如果g不为子树最后将g调整为黑色就完成了红黑树的调整 如果g为子树一次调整以后g还有双亲双亲如果是红色将pu改为黑g改为红然后把g当成cur继续向上调整还要继续向上调整。 2.cur为红p为红g为黑u不存在/u存在且为黑p为g的左孩子cur为p的左孩子或者p为g的右孩子cur为g的右孩子 我们均已被插入结点在根结点左侧为例
如果u节点不存在则cur一定是新插入节点因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色就不满足性质每条路径黑色节点个数相同。 此时我们只需要以p为旋转点进行右单旋然后进行颜色调整即可 当u存在且为黑时
此时一定是情况一向上调整才会出现的情况这种情况下cur不会是新插入的结点是经过前一次调整以后的结点 我们以新插入结点在a的左侧为例
此时我们以g为旋转点进行右单旋然后进行颜色调整红黑树即可平衡
同样如果被插入结点在根结点右侧我们只需要进行相应左旋在调整颜色即可实现红黑树平衡
抽象图如下
被插入结点在根结点左侧 被插入结点在根结点右侧 3.cur为红p为红g为黑u不存在/u存在且为黑p为g的左孩子cur为p的右孩子或者p为g的右孩子cur为p的左孩子 u不存在时
当u存在且为黑时我们以下面这种情况为例 我们先已p为轴点进行左单旋再以g为轴点进行右单旋最后进行颜色调整红黑树保持平衡
抽象图如下
被插入结点在根结点左侧 被插入结点在根结点右侧 代码实现
bool Insert(const pairK, V kv)
{//根结点为空if (_root nullptr){//创建根结点_root new Node(kv);//颜色变为黑_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){//如果插入key值小于根结点key值if (cur-_kv.first kv.first){parent cur;cur cur-_left;}//如果插入key值大于根结点key值else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}//相等返回falseelse{return false;}}//创建cur结点cur new Node(kv);//颜色初始化为红色cur-_col RED;//如果插入key值小于parent结点key值if (parent-_kv.first kv.first){//在左边插入parent-_left cur;}//如果插入key值大于parent结点key值else{//在右边插入parent-_right cur;}//跟父结点连接起来cur-_parent parent;while (parent parent-_col RED){//定义祖父节点Node* grandfather parent-_parent;assert(grandfather);assert(grandfather-_col BLACK);//如果父结点在祖父节点左边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);grandfather-_col RED;parent-_col BLACK;}//插入结点在父结点左边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);grandfather-_col RED;parent-_col BLACK;}//插入结点在父结点左边else{//右左双旋颜色调整RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//根结点变为黑色_root-_col BLACK;return true;
}红黑树的验证
我们可以判断每条路径的黑节点数量是否相等来判断该二叉树是否为红黑树
void InOrder()
{_InOrder(_root);cout endl;
}bool IsBalance()
{//如果根结点为空返回trueif (_root nullptr){return true;}//如果根结点为红色则返回falseif (_root-_col RED){cout 根结点不是黑色 endl;return false;}//定义一个黑色结点数量的基准值为最左边路径黑色结点数量int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK){benchmark;}cur cur-_left;}//黑色结点数量int BlackNum 0;return PrevCheck(_root, BlackNum, benchmark);
}
bool PrevCheck(Node* root, int BlackNum, int benchmark)
{//说明此时路径已经走完了if (root nullptr){//如果基准值不等于黑色结点数量返回falseif (benchmark ! BlackNum){cout 某条黑色结点数量不相等 endl;return false;}//否则返回truereturn true;}//根结点为黑色黑色结点数量if (root-_col BLACK){BlackNum;}//存在连续红色节点返回falseif (root-_col RED root-_parent-_col RED){cout 存在连续的红色结点 endl;return false;}//递归进行判断return PrevCheck(root-_left, BlackNum, benchmark) PrevCheck(root-_right, BlackNum, benchmark);
}红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单。
