企业网站建设的服务类型有哪些,个人推广app的妙招,怀化建设局网站,电子商务网站是什么在了解底层封装之前除了对set和map的使用情况要有一定了解#xff0c;还需要先学习一下二叉搜索树#xff0c;AVL树#xff0c;红黑树这些数据结构。 【C】二叉搜索树 【C】AVL树 红黑树
RBTree.h
enum Colour
{RED,BLACK
};templateclass T
class RBTreeNo…在了解底层封装之前除了对set和map的使用情况要有一定了解还需要先学习一下二叉搜索树AVL树红黑树这些数据结构。 【C】二叉搜索树 【C】AVL树 红黑树
RBTree.h
enum Colour
{RED,BLACK
};templateclass T
class RBTreeNode
{
public:RBTreeNode(const T data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;
};templateclass T, class Ref, class Ptr
// 红黑树的迭代器实现
class __RBTreeIterator
{
public:typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;
public:__RBTreeIterator(Node* node): _node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{return _node s._node;}Self operator(){// 右子树不为空if (_node-_right){// 就是找右子树的最左节点Node* left _node-_right;while (left-_left){left left-_left;}_node left;}// 右子树为空else{// 就是找不是其右孩子的祖先Node* parent _node-_parent;Node* cur _node;while (parent parent-_right cur){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){// 左子树不为空if (_node-_left){// --就是找左子树的最右节点Node* right _node-_left;while (right-_right){right right-_right;}_node right;}// 左子树为空else{// --就是找不是其左孩子的祖先Node* parent _node-_parent;Node* cur _node;while (parent parent-_left cur){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}
public:Node* _node;
};// KeyOfT: 用于获取T中的key的一个仿函数类
templateclass K, class T, class KeyOfT
class RBTree
{
private:typedef RBTreeNodeT Node;
public:typedef __RBTreeIteratorT, T, T* iterator;RBTree(Node* root nullptr): _root(root){}// begin() 就是找红黑树的最左节点iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}// 因为迭代器是左闭右开所以end()的迭代器设置为空iterator end(){return iterator(nullptr);}pairiterator, bool Insert(const T data){KeyOfT kot;if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root), true);}Node* parent nullptr;Node* cur _root;while (cur){if (kot(data) kot(cur-_data)){parent cur;cur cur-_right;}else if (kot(data) kot(cur-_data)){parent cur;cur cur-_left;}else{return make_pair(iterator(cur), false);}}cur new Node(data);cur-_col RED;// 保存cur用于返回Node* newnode cur;if (kot(data) kot(parent-_data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandparent parent-_parent;if (parent grandparent-_left){Node* uncle grandparent-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else{if (cur parent-_left){RotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}else{Node* uncle grandparent-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else{if (cur parent-_right){RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode), true);}
private: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 (_root parent){_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;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}
private:Node* _root;
};Set.h
#include RBTree.hnamespace zs
{templateclass Kclass set{public:class SetKeyOfT{public:const K operator()(const K key){return key;}};typedef typename RBTreeK, K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const K key){return _t.Insert(key);}private:// set的底层就是一棵红黑树RBTreeK, K, SetKeyOfT _t;};
}Map.h
#include RBTree.hnamespace zs
{templateclass K, class Vclass map{public:class MapKeyOfT{public:const K operator()(const pairK, V kv){return kv.first;}};typedef typename RBTreeK, pairK,V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const pairK, V kv){return _t.Insert(kv);}// map支持[]操作V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:// map的底层就是一棵红黑树RBTreeK, pairK, V, MapKeyOfT _t;};}
