如何做淘宝直播教学视频网站,上海网站建设公司站霸网络,成品短视频app下载有哪些,免费的h5页面制作工具前言
前面我们介绍了AVL树#xff0c;AVL树是一棵非常自律的树#xff0c;有着严格的高度可控制#xff01;但是正它的自律给他带来了另一个问题#xff0c;即虽然他的查找效率很高#xff0c;但是插入和删除由于旋转而导致效率没有那么高。我们上一期的结尾说过经常修改…前言
前面我们介绍了AVL树AVL树是一棵非常自律的树有着严格的高度可控制但是正它的自律给他带来了另一个问题即虽然他的查找效率很高但是插入和删除由于旋转而导致效率没有那么高。我们上一期的结尾说过经常修改的话就不太适合AVL树了而红黑树更加适合OK本期就来介绍一下赫赫有名的红黑树
本期内容介绍 什么是红黑树 红黑树的实现 红黑树的效率分析以及应用 什么是红黑树
红黑树是1972年由Rudolf Bayer发明的当时被称为平衡二叉B树symmetric binary B-trees。后来在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的 红黑树 。 红黑树是一种二叉搜索树但在每个结点上增加了一个存储位表示结点的颜色可以是红色或是黑色通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径比其他的路径长出两倍因而是接近平衡的 OK这就是一棵红黑树 最长节点的路径就是一黑一红的交替最短的就是两黑 红黑树的性质 1、每个结点要么是红色要么是黑色 2、根节点是黑色 3、如果一个结点是红色则它的两个孩子结点是黑色 4、对于任意一个节点从该结点到其所有的后代叶子结点的简单路径上均包含相同的黑色结点 5、每个叶子结点就是黑色的此处的叶子结点指的是空节点 上面的这5条性质就是限制红黑树平衡的规则其中4最重要的下来是3基本所有的操作都是围着4进行的
红黑树的实现
OK上面介绍了红黑树是一种二叉搜索树只不过是在每个结点添加了一个存储颜色的颜色位所以它的大框架还是和搜索树一样的所以我们就先搭一个框架出来
enum Col//颜色
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;//左孩子RBTreeNodeK, V* _right;//右孩子RBTreeNodeK, V* _parent;//父结点pairK, V _kv;//数据域Col _col;//颜色RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//新插入的节点默认是红色{}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:RBTree():_root(nullptr),_size(0){}private:Node* _root;//根节点size_t _size;//节点的数量
}; 思考新插入的节点应该是红色还是黑色为什么 新插入的节点一定是红色 因为新插入的节点是红色可能违反性质3但一定不违反性质4 如果新插入的是黑色一定违反性质4也就是在部分子路径上增加了黑色节点。所以插入的新节点一定是红色即使红色违反了性质3也是比较好控制的 OK这里依旧是采用的三叉链原因是方便找父亲 红黑树的插入
上面介绍了红黑树的本质是一种二叉搜索树所以先不管它的颜色和高度如何调节先把搜索树的那一套给整出来
bool Insert(const pairK, V kv)
{Node* cur _root;//当前节点Node* parent nullptr;//插入位置的父亲//第一次插入if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点是黑色return true;}//寻找插入的位置while (cur){if (cur-_kv.first kv.first)//插入节点的key比当前节点的key大{parent cur;cur cur-_right;//去右边找}else if(cur-_kv.first kv.first)//插入节点的key比当前节点的key小{parent cur;cur cur-_left;//去左边找}else{return false;//插入的节点存在}}//找到插入位置cur new Node(kv);//链接if (parent-_kv.first cur-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//颜色和高度调整//....return true;
}
OK还是先来验证一下当前的逻辑对不对所以走个中序看看是不是有序即可由于中序要根节点而类外面是无法访问的所以我们还是和以前一样搞成子函数或提供get和set方法这里就搞成子函数了
中序遍历
void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);
} OK没问题下面我们就来讨论一下红黑树的维持平衡的方式:变色和旋转
红黑树的变色和旋转 由于新插入的节点一定是红色的此时分为两种情况1、父亲为黑 2、父亲为红 如果父亲为黑不违反任何性质插入结束 如果父亲为红看看叔叔此时叔叔有三类情况1、叔叔存在且为红 2、叔叔不存在 3、叔叔存在为黑 如果叔叔存在且为红变色将父亲和叔叔变黑色将爷爷变红色继续更新 如果叔叔不存在或存在且为黑旋转 变色如果孩子是父亲的左/右先对孩子父亲进行左/右旋在对爷爷进行左/右 OK这里看着可能会有些迷看看下面的导图会很清楚 OK理解了上述的表达下面我来画图解释一下
parent是黑色插入结束 parent为红叔叔存在且为红变色 父亲和叔叔变黑爷爷变红继续向上更新 这里只画了parent在爷爷的左边的情况如果parent在爷爷的右边和这个是一样的
parent为红叔叔不存在会存在为黑变色 旋转 如果parent在爷爷的左且cur在父亲的左对爷爷进行右单旋 如果parent在爷爷的左且cur在父亲的右先对parent左单旋在对爷爷进行右单旋 如果parent在爷爷的右且cur在父亲的右对爷爷进行左单旋 如果parent在爷爷的右且cur在父亲的左先对parent右单旋在对爷爷进行左单旋 OK废话不多说直接上代码
bool Insert(const pairK, V kv)
{Node* cur _root;//当前节点Node* parent nullptr;//插入位置的父亲//第一次插入if (_root nullptr){_root new Node(kv);_size;//插入成功节点数1_root-_col BLACK;//根节点是黑色return true;}//寻找插入的位置while (cur){if (cur-_kv.first kv.first)//插入节点的key比当前节点的key大{parent cur;cur cur-_right;//去右边找}else if(cur-_kv.first kv.first)//插入节点的key比当前节点的key小{parent cur;cur cur-_left;//去左边找}else{return false;//插入的节点存在}}//找到插入位置cur new Node(kv);//链接if (parent-_kv.first cur-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//颜色和高度调整while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left)//父亲在爷爷的左{Node* uncle grandfather-_right;//叔叔就是父亲的右//父亲存在且为红 - 变色if (uncle uncle-_col RED){grandfather-_col RED;parent-_col uncle-_col BLACK;//继续向上调整cur grandfather;parent cur-_parent;}else//叔叔不存在或存在但为黑 - 变色 旋转{if (cur parent-_left)//cur在父亲的左{// g// p u// cRotateR(grandfather);//旋转parent-_col BLACK;//变色grandfather-_col RED;}else//cur在父亲的右{// g// p u// cRotateL(parent);//旋转RotateR(grandfather);cur-_col BLACK;//变色grandfather-_col RED;}break;//旋转后不需要再向上更新了}}else//parent在爷爷的右{Node* uncle grandfather-_left;//叔叔在父亲的左//叔叔存在且为红 - 变色if (uncle uncle-_col RED){grandfather-_col RED;parent-_col uncle-_col BLACK;//继续向上调整cur grandfather;parent cur-_parent;}else//叔叔不存在或存在但为黑 - 变色 旋转{if (cur parent-_left)//cur在父亲的左 {// g// u p// cRotateR(parent);//旋转RotateL(grandfather);cur-_col BLACK;//变色grandfather-_col RED;}else{// g// u p// cRotateL(grandfather);//旋转parent-_col BLACK;//变色grandfather-_col RED;}break;//旋转后不需要再向上更新了}}}_root-_col BLACK;//保证根节点永远是黑色_size;//插入成功节点数1return true;
}
旋转 红黑树的旋转没有AVL的复杂只有左右单旋且没有平衡因子整体的逻辑和AVL一样的这里不在详细介绍了 void RotateR(Node* parent)
{Node* subL parent-_left;//父亲的左Node* subLR subL-_right;//左子树的右Node* ppNode parent-_parent;//parent的父节点,方便旋转后的链接parent-_left subLR;//将左子树的右给父亲的做if (subLR)subLR-_parent parent;subL-_right parent;//parent做左子树的右parent-_parent subL;if (parent _root)//parent是根{_root subL;//此时的新根就是subLppNode nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}
}void RotateL(Node* parent)
{Node* subR parent-_right;//父亲的右Node* subRL subR-_left;//右子树的左Node* ppNode parent-_parent;//parent的父节点,方便旋转后的链接parent-_right subRL;//将右子树的左连接到parent的右if (subRL)subRL-_parent parent;subR-_left parent;//parent连接到subR的左parent-_parent subR;if (parent _root)//parent是根{_root subR;//此时的新根就是subRppNode nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}
}
OK我们验证一下判断一下是否是平衡的
是否平衡 先获取任意一条路径的黑色节点然后通过dfs进行检查每个结点是不是符合红黑树的规则 如果出现连续的红色节点不符合判断方式当出现红色节点时检查其父节点是否是红色的如果是则不符合 如走到空了检查该条路径的黑色节点和一开始求出的是否一致不一致则不符合 当前节点符合去检查其左右 bool IsBalance()
{if (_root _root-_col RED){return false;//根为红一定不是红黑树}int black 0;//获取任意一条路径的黑色节点这里是最左路Node* cur _root;while (cur){if (cur-_col BLACK){black;}cur cur-_left;}return Check(_root, black, 0);
}
bool Check(Node* root, const int black, int num)
{if (root nullptr){//当走到叶子节点的时候和其他路径的黑色节点的个数不一样if (black ! num){return false;}return true;}//存在连续的红色节点if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}//遇到黑色节点if (root-_col BLACK){num;}//当前节点符合红黑树它的左右子树也要都符合return Check(root-_left, black, num) Check(root-_right, black, num);
}
OK验证一下
OK么有问题下面把其他的接口补一下
Size 由于我们提前记录了_size所以直接返回成员_size即可 size_t Size()
{return _size;
}
Find 和以前的搜索树一样大了去右边找小了去左边找 Node* Find(const K key)
{Node* cur _root;while (cur){if (cur-_kv.first key)//插入节点的key比当前节点的key大{cur cur-_right;//去右边找}else if (cur-_kv.first key)//插入节点的key比当前节点的key小{cur cur-_left;//去左边找}else{return cur;//找到了}}return nullptr;//没找到
} 再来一组随机的测试用例插入1亿个随机值看看时间和是否平衡注意这里一亿个节点在32位debug下可能内存空间不够可以把他改成64的release地址空间大一点
void Test()
{const int N 100000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}size_t begin2 clock();RBTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}size_t end2 clock();cout time : end2 - begin2 endl;cout t.IsBalance() endl;
} 红黑树的删除请参考这篇博客 红黑树的删除
全部源码
#pragma onceenum Col//颜色
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;//左孩子RBTreeNodeK, V* _right;//右孩子RBTreeNodeK, V* _parent;//父结点pairK, V _kv;//数据域Col _col;//颜色RBTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//新插入的节点默认是红色{}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:RBTree():_root(nullptr),_size(0){}bool Insert(const pairK, V kv){Node* cur _root;//当前节点Node* parent nullptr;//插入位置的父亲//第一次插入if (_root nullptr){_root new Node(kv);_size;//插入成功节点数1_root-_col BLACK;//根节点是黑色return true;}//寻找插入的位置while (cur){if (cur-_kv.first kv.first)//插入节点的key比当前节点的key大{parent cur;cur cur-_right;//去右边找}else if(cur-_kv.first kv.first)//插入节点的key比当前节点的key小{parent cur;cur cur-_left;//去左边找}else{return false;//插入的节点存在}}//找到插入位置cur new Node(kv);//链接if (parent-_kv.first cur-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//颜色和高度调整while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left)//父亲在爷爷的左{Node* uncle grandfather-_right;//叔叔就是父亲的右//父亲存在且为红 - 变色if (uncle uncle-_col RED){grandfather-_col RED;parent-_col uncle-_col BLACK;//继续向上调整cur grandfather;parent cur-_parent;}else//叔叔不存在或存在但为黑 - 变色 旋转{if (cur parent-_left)//cur在父亲的左{// g// p u// cRotateR(grandfather);//旋转parent-_col BLACK;//变色grandfather-_col RED;}else//cur在父亲的右{// g// p u// cRotateL(parent);//旋转RotateR(grandfather);cur-_col BLACK;//变色grandfather-_col RED;}break;//旋转后不需要再向上更新了}}else//parent在爷爷的右{Node* uncle grandfather-_left;//叔叔在父亲的左//叔叔存在且为红 - 变色if (uncle uncle-_col RED){grandfather-_col RED;parent-_col uncle-_col BLACK;//继续向上调整cur grandfather;parent cur-_parent;}else//叔叔不存在或存在但为黑 - 变色 旋转{if (cur parent-_left)//cur在父亲的左 {// g// u p// cRotateR(parent);//旋转RotateL(grandfather);cur-_col BLACK;//变色grandfather-_col RED;}else{// g// u p// cRotateL(grandfather);//旋转parent-_col BLACK;//变色grandfather-_col RED;}break;//旋转后不需要再向上更新了}}}_root-_col BLACK;//保证根节点永远是黑色_size;//插入成功节点数1return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key)//插入节点的key比当前节点的key大{cur cur-_right;//去右边找}else if (cur-_kv.first key)//插入节点的key比当前节点的key小{cur cur-_left;//去左边找}else{return cur;//找到了}}return nullptr;//没找到}void InOrder(){return _InOrder(_root);}size_t Size(){return _size;}bool IsBalance(){if (_root _root-_col RED){return false;//根为红一定不是红黑树}int black 0;//获取任意一条路径的黑色节点这里是最左路Node* cur _root;while (cur){if (cur-_col BLACK){black;}cur cur-_left;}return Check(_root, black, 0);}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}void RotateR(Node* parent){Node* subL parent-_left;//父亲的左Node* subLR subL-_right;//左子树的右Node* ppNode parent-_parent;//parent的父节点,方便旋转后的链接parent-_left subLR;//将左子树的右给父亲的做if (subLR)subLR-_parent parent;subL-_right parent;//parent做左子树的右parent-_parent subL;if (parent _root)//parent是根{_root subL;//此时的新根就是subLppNode nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void RotateL(Node* parent){Node* subR parent-_right;//父亲的右Node* subRL subR-_left;//右子树的左Node* ppNode parent-_parent;//parent的父节点,方便旋转后的链接parent-_right subRL;//将右子树的左连接到parent的右if (subRL)subRL-_parent parent;subR-_left parent;//parent连接到subR的左parent-_parent subR;if (parent _root)//parent是根{_root subR;//此时的新根就是subRppNode nullptr;}else//parent不是根{//将新的根连接到ppNodeif (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}bool Check(Node* root, const int black, int num){if (root nullptr){//当走到叶子节点的时候和其他路径的黑色节点的个数不一样if (black ! num){return false;}return true;}//存在连续的红色节点if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}//遇到黑色节点if (root-_col BLACK){num;}//当前节点符合红黑树它的左右子树也要都符合return Check(root-_left, black, num) Check(root-_right, black, num);}private:Node* _root;//根节点size_t _size;//节点的数量
};红黑树的效率分析以及应用
红黑树和AVL树的比较 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log_2 N)红黑树不追 求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数 所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 红黑树的应用 C的STL库中的map/set/multimap/multiset底层都是红黑树实现的 一些Java的库例如: TreeMap和TreeSet等 一些Linux的内核例如进程调度等 OK本期分享就到这里好兄弟我们下期再见 结束语简单的事重复做重复的是坚持做
