网站改版301是什么意思,杭州免费自助建站模板,招生网站开发,怎么查楼盘预售许可证前言#xff1a; 上篇文章我们一起学习了AVL树比模拟实现#xff0c;我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题#xff0c;在构建AVL树中我们也付出了不小的代价#xff0c;频繁的旋转操作导致效率变低。为了解决这个问题#xff0c…前言 上篇文章我们一起学习了AVL树比模拟实现我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题在构建AVL树中我们也付出了不小的代价频繁的旋转操作导致效率变低。为了解决这个问题我们本章将迎来更为实用的红黑树他在提高查找效率的同时也相对AVL树提高了构建树的效率他的应用将更加广泛比如map、set的底层实现就是红黑树
目录
一红黑树的概念
1、概念
2、特性
二红黑树的模拟实现
1、结点的定义
2、结点的查找实现Find
3、结点的插入实现Insert*重点
3.1前序问题
3.2具体流程
情况一叔叔存在且为红——变色处理
情况二叔叔不存在or叔叔存在且为黑——旋转变色 情况三叔叔不存在or叔叔存在且为黑——双旋变色区别于情况二
4、具体代码FindInsert
三验证红黑树
1、中序遍历
2、验证红黑树几大特性
3、测试用例
四项目完整代码 一红黑树的概念
1、概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black所以叫红黑树。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 2、特性
每个结点不是红色就是黑色根节点是黑色的 如果一个节点是红色的则它的两个孩子结点是黑色的 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 思考 为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点 个数的两倍 这里我们从路径最短的情况和最长的情况分析 我们假设该红黑树每条路径黑色结点数是3 路径最短的情况 这条路径没有红色结点如下图 路径最长的情况 这条路径一个黑色节点接着一个红色节点交相出现 这时我们发现最短路径时一条路径上有三个结点(情况一)最长路径时一条路径上有五个节点情况二。所以可以保证其最长路径中节点个数不会超过最短路径节点个数的两倍。 二红黑树的模拟实现
1、结点的定义
我们还是沿用AVL树节点的三叉链定义方法颜色我们用枚举来实现 ps这里一开始结点定义为红色的原因我们在后文插入的时候会详细讲解。 2、结点的查找实现Find
在红黑树中的Find查找操作和之前二叉搜索树和AVL树实现方法一样这里我们简单带过。
结点存的值比当前结点小就向左找比当前结点大就向右找最后遇到空节点表示没找到。 3、结点的插入实现Insert*重点
3.1前序问题
首先我们解答上面留下的那个问题
为什么新插入的结点要默认给红色的
假设我们默认给新增的结点黑色那么一定违反上面红黑树的特性4对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 。这样我们还要对其他路径进行修改黑色结点的数量。但是如果默认给红色我们则是可能违反特性3如果一个节点是红色的则它的两个孩子结点是黑色的 。为什么说是可能因为如果他的父亲节点是黑色则不违反。就算违反了。每条路径黑色结点的数量还是一样的我们只需要调整所在的那一条路径即可代价相对小了许多。 3.2具体流程
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
分别对应parentgrandfatheruncle的意思
插入几大流程
按照搜索二叉树的查找方法找到要插入的位置将新增结点插入到待插入位置如果需要调整则调整红黑树
其中需不需要调整主要是看叔叔颜色的情况。
下面具体分析
我们先给出一个基本的图示 这里的三角形就相当于AVL树中的小长方形代表了一部分子树。 情况一叔叔存在且为红——变色处理
cur为红p为红g为黑, u存在且为红
解决方式:将pu改为黑g改为红然后把g当成cur继续向上调整。 首先我们知道红黑树调整主要看叔叔第一步我们将父亲变成黑色为了维护性质4我们也要将叔叔的颜色变成黑色同时也要将祖父结点的颜色变成红色因为我们此时处理的不一定是整棵树有可能是某个子树如果此时不是子树就需要将根节点变成黑色。这样我们就在局部调整颜色并保证了不破坏规则。 调整的部分可能是一整棵树也可能是某一棵子树
如果g是根节点调整完成后需要将g改为黑色如果g是子树g一定有双亲且g的双亲如果是红色需要继续向上调整 情况一的情景下我们只关心颜色的调整就可以在不破坏规则的情况下插入结点 情况二叔叔不存在or叔叔存在且为黑——旋转变色 情况二可能就是从情况一调整变化得到的情况。
具体情况 1
当叔叔不存在时 我们调整颜色总会破坏规则此时结合上面长路径不会超过短路径二倍的特性我们分析英爱使用到了和AVL树相似的旋转处理。 此时是左边高了我们对图示树进行右单旋这里的旋转和AVL树中旋转的方式如出一辙可以拿过来直接复用。同样的道理如果是右边高了我们就可以进行左单旋旋转的方法也和AVL树中的如出一辙也可拿过来直接复用。这里我们就不像AVL树那样详细解释了实现方法是一样的如果读者不太了解可以看上一篇文章 具体情况 2
当叔叔存在且为黑时
按照上文说明这种情况必定是由情况一变化而来的。
此时也是旋转变色 这样子才能保护好红黑树的结构。 情况三叔叔不存在or叔叔存在且为黑——双旋变色区别于情况二
同样是 叔叔不存在 or 叔叔存在且为黑为啥分为情况二和情况三呢
上述旋转的情况都是单边的情况也就是说cur、p、g在一条线上的情况若是出现了这三者不在一条直线的时候单旋就解决不了问题了。
区别:
p是g的左cur是p的左那么是情况二 —— 单旋p是g的左cur是p的右那么是情况三 —— 双旋
此时我们就引入了双旋
这里我们可以结合上一篇AVL树来区别单旋和双旋 先以p为旋转点再以g为旋转点先变到情况二的样子再根据情况二来继续变
其实看完情况二和三有些人就会有疑问了看上去每条路径上黑色结点树不一样啊为什么要这样旋转变色
再此之前我们推测过当叔叔存在且为黑时一定是由情况一变来的所以cur一开始是黑的这个树并不违反性质子树由情况一变化之后的子树结点的颜色也相应变化了只是没有显示出来而已。
4、具体代码FindInsert
Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}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){ 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);if (parent-_kv.firstkv.first){parent-_left cur;}else if (parent-_kv.first kv.first){parent-_right cur;}cur-_parent parent;//调整颜色while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent)//u存在且为红{Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//u不存在或者为黑,旋转加变色{if (cur parent-_left){// g// p u//cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//grandfather-_right parent{Node* uncle grandfather-_left;if (uncle uncle-_col RED){// g// u p// cuncle-_col BLACK;parent-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else// u不存在/u存在且为黑旋转变色{if (cur parent-_right){// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}三验证红黑树
老样子我们在上一章模拟实现AVL树后用了几个函数来验证我们构建的树是否是AVL树这里我们也要验证一下我们构建的这棵树是否是红黑树。
几个验证要点
这棵树是否是二叉搜索树根结点是否是黑色结点红色结点的子结点是否是黑色结点每条路径黑色结点树是否一样
满足这几个要点也就是红黑树的特性那么这棵树1就是红黑树了。
1、中序遍历
一棵树是红黑树的前提就是他必须是二叉搜索树二叉搜索树的特点就是中序遍历是有序的。
void InOrder(){return _InOrder(_root);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}
ps为了符合用户的使用习惯我们还是采取嵌套的方式大家不明白的可以看一下上一篇文章验证处有说明哦 2、验证红黑树几大特性
相对AVL树验证红黑树是更加麻烦的几个要点
首先判断根结点是否是黑色判断每条路径黑色结点数我们思路是先取一条路径黑色结点数量为基准值然后递归统计其他路径的数目遇到空结点再比较遇到红色结点我们如果判断他的孩子结点是否是黑色如果是要跳过代码不好写不如换个思路遇到一个红色结点就判断双亲是否是红色如果是存在连续红色结点返回false。 bool IsBalance(){if (_root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if(cur-_colBLACK)benchmark;cur cur-_left;}return _Check(_root, 0, benchmark);}private:bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}
通过递归的方式将每条支路都走了一遍和基准值比较并且将红黑树的性质全都验证了。
3、测试用例 void Test_RBTree1()
{//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 };RBTreeint, int t1;for (auto e : a){/* if (e 14){int x 0;}*/t1.Insert(make_pair(e, e));//cout e 插入 t1.IsBalance() endl;}t1.InOrder();cout endl;cout t1.IsBalance() endl;
}void Test_RBTree2()
{srand(time(0));const size_t N 5000000;RBTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));//cout t.IsBalance() endl;}//t.Inorder();cout t.IsBalance() endl;cout t.Height() endl;
}
精检验没有问题 四项目完整代码
#pragma once
#includeiostream
#includeassert.husing namespace std;enum Colour
{RED,BLACK,
};templateclass K,class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};templateclass K,class V
struct RBTree
{typedef RBTreeNodeK, V Node;void Destroy(Node* root){_Destroy(root);root nullptr;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}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){ 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);if (parent-_kv.firstkv.first){parent-_left cur;}else if (parent-_kv.first kv.first){parent-_right cur;}cur-_parent parent;//调整颜色while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent)//u存在且为红{Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//u不存在或者为黑,旋转加变色{if (cur parent-_left){// g// p u//cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//grandfather-_right parent{Node* uncle grandfather-_left;if (uncle uncle-_col RED){// g// u p// cuncle-_col BLACK;parent-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else// u不存在/u存在且为黑旋转变色{if (cur parent-_right){// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void InOrder(){return _InOrder(_root);}int Height(){return _Height(_root);}bool IsBalance(){if (_root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if(cur-_colBLACK)benchmark;cur cur-_left;}return _Check(_root, 0, benchmark);}private:bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}int _Height(Node* root){if(rootnullptr){return 0;}int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;}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;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}
private:Node* _rootnullptr;
};void Test_RBTree1()
{//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 };RBTreeint, int t1;for (auto e : a){/* if (e 14){int x 0;}*/t1.Insert(make_pair(e, e));//cout e 插入 t1.IsBalance() endl;}t1.InOrder();cout endl;cout t1.IsBalance() endl;
}void Test_RBTree2()
{srand(time(0));const size_t N 5000000;RBTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));//cout t.IsBalance() endl;}//t.Inorder();cout t.IsBalance() endl;cout t.Height() endl;
}
祝您学业有成
