做视频网站需要哪些技术,万网 手机网站,上海最好的网站建设,大鱼直播文章目录 一、红黑树1.1红黑树的规则#xff1a;1.2红黑树的插入操作1.2.1不需要旋转#xff08;如果叔叔存在且为红,这里的C表示孩子#xff0c;P表示父亲#xff0c;U表示叔叔#xff0c;G表示祖父#xff09;#xff0c;包含四种情况#xff0c;无论孩子在哪里… 文章目录 一、红黑树1.1红黑树的规则1.2红黑树的插入操作1.2.1不需要旋转如果叔叔存在且为红,这里的C表示孩子P表示父亲U表示叔叔G表示祖父包含四种情况无论孩子在哪里都是只需要改变叔叔和父亲的颜色为黑祖父为红然后向上继续走C G1.2.2需要旋转左旋右旋左右双旋右左双旋叔叔不存在或者为黑 1.2红黑树的插入代码1.3红黑树的整体框架 二、map、set的底层封装2.1set的底层封装2.2map的底层封装2.3红黑树的底层封装 一、红黑树
相较于前面的AVL树红黑树的优势是旋转次数减少效率提高了同时还保留了AVL树的查找优势
1.1红黑树的规则
1.每个节点不是红色就是黑色 2.红色节点的孩子一定是黑色节点 3.不能有连续的红色节点 4.每条路径走到空为止上的黑色节点数量相同 5.最短路径最长路径2最短路径当某条路径只有黑色节点而另一条路径红色节点数量和黑色节点相同那么最长路径就是最短路路径的两倍
1.2红黑树的插入操作
1.2.1不需要旋转如果叔叔存在且为红,这里的C表示孩子P表示父亲U表示叔叔G表示祖父包含四种情况无论孩子在哪里都是只需要改变叔叔和父亲的颜色为黑祖父为红然后向上继续走C G 1.2.2需要旋转左旋右旋左右双旋右左双旋叔叔不存在或者为黑
右旋的情况(这里省略了C,P,U所连的节点 左右双旋的情况(这里省略了C,P,U所连的节点 下面两种情况省略
1.2红黑树的插入代码 bool Insert(const pairK, V data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (data.first cur-_data.first){parent cur;cur cur-_right;}else if (data.first cur-_data.first){parent cur;cur cur-_left;}elsereturn false;}cur new Node(data);if (parent-_data.first cur-_data.first)parent-_left cur;elseparent-_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)//叔叔存在且为红{uncle-_col parent-_col BLACK;grandfather-_col RED;cur grandfather;//继续向上处理parent cur-_parent;}else{if (cur parent-_left){//叔叔为黑或者叔叔不存在RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;parent-_col RED;}break;}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfather-_col RED;cur grandfather;//继续向上处理parent cur-_parent;}else{if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_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;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;}
}
1.3红黑树的整体框架
#pragma once
#includeiostream
#includeassert.h
using namespace std;//颜色定义
enum color
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{typedef RBTreeNodeK, V Node;pairK, V _data;Node* _left;Node* _right;Node* _parent;color _col;//构造函数RBTreeNode(const pairK, V data):_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _data(data){}
};templateclass K,class V
class RBTree
{
public:typedef RBTreeNodeK, V Node;bool Insert(const pairK, V data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (data.first cur-_data.first){parent cur;cur cur-_right;}else if (data.first cur-_data.first){parent cur;cur cur-_left;}elsereturn false;}cur new Node(data);if (parent-_data.first cur-_data.first)parent-_left cur;elseparent-_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)//叔叔存在且为红{uncle-_col parent-_col BLACK;grandfather-_col RED;cur grandfather;//继续向上处理parent cur-_parent;}else{if (cur parent-_left){//叔叔为黑或者叔叔不存在RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;parent-_col RED;}break;}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfather-_col RED;cur grandfather;//继续向上处理parent cur-_parent;}else{if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_data.first 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;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;}}Node* _root nullptr;
};
二、map、set的底层封装
这里我们需要加上迭代器和仿函数为了套用同一个红黑树的模版 map有两个模版参数、set只有一个模版参数因此我们需要加一个仿函数来确定是map还是set
2.1set的底层封装
namespace SF
{//仿函数templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK,const K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K key){return _t.Insert(key);}private:RBTreeK,const K, SetKeyOfT _t;};
}2.2map的底层封装
namespace SF
{templateclass K,class V class map{struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pairK,V data){return _t.Insert(data);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};
}2.3红黑树的底层封装
#pragma once
#includevectorenum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;T _data;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT Self;Node* _node;RBTreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_right){// 右子树的中序第一个(最左节点)Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent cur-_parent;}_node parent;}return *this;}Self operator--(){// return *this;}bool operator!(const Self s){return _node ! s._node;}bool operator (const Self s){return _node s._node;}
};// set-RBTreeK, K, SetKeyOfT
// map-RBTreeK, pairK, V, MapKeyOfT// KeyOfT仿函数 取出T对象中的key
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT iterator;iterator begin(){Node* subLeft _root;while (subLeft subLeft-_left){subLeft subLeft-_left;}return iterator(subLeft);}iterator end(){return iterator(nullptr);}bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}KeyOfT kot;Node* parent nullptr;Node* cur _root;while (cur){if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else{return false;}}cur new Node(data); // 红色的if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left 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){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色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{Node* uncle grandfather-_left;// 情况一叔叔存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(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 RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_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;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}private:Node* _root nullptr;
};
