封装红黑树->mapset
目录
目录
1.KeyofT
2.iterator
3.key不支持修改问题
4.map的operator[ ]
5.map实现
6.set实现
7.封装后的红黑树
小知识
由于set为单模版参数,map为双模版参数,所以为了只实现一棵红黑树,对红黑树进行了一些处理
1.KeyofT
获取key值,用来实现比较逻辑,在set和map中要分别实现一个。
set中:
struct KeyofT
{
const T& operator()(const T& key)
{
return key;
}
};map中:
struct KeyofV
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
2.iterator
这里使用带头结点的红黑树。
++:右子树不为空时,下一个访问右子树的最左结点;为空,下一个访问孩子是父亲的左结点的父亲结点。
--:左子树不为空时,下一个访问左子树的最右结点;为空,下一个访问孩子节点时父亲的右结点的父亲结点
和list中的封装类似,++和--的逻辑不同。
template<class T,class ref,class ptr>
struct RBTree_Iterator
{
typedef RBTree_node<T> Node;
Node* _node;
Node* _root;
typedef RBTree_Iterator<T, ref, ptr> self;RBTree_Iterator(Node* node, Node* root)
:_node(node)
,_root(root)
{}self& operator++()
{
if (_node->_right)
{
_node = _node->_right;
while (_node->_left)
{
_node = _node->_left;
}
}
else
{
if (_node != _root)
{
Node* parent = _node->_parent;
while (parent->_left != _node)
{
if (parent == _root)
{
_node = nullptr;
return *this;
}
_node = parent;
parent = _node->_parent;
}
_node = parent;
}
else
{
_node = nullptr;
}
}
return *this;
}self& operator--()
{
if (!_node)
{
_node = _root->_parent->_right;
}
else if (_node->_left)
{
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
}
else
{
if (_node != _root)
{
Node* parent = _node->_parent;
while (parent->_right != _node)
{
if (parent == _root)
{
_node = nullptr;
break;
}
_node = parent;
parent = _node->_parent;
}
_node = parent;
}
else
{
_node = nullptr;
}
}
return *this;
}ref operator*()
{
return _node->_data;
}ptr operator->()
{
return &_node->_data;
}bool operator==(const self& Iterator)
{
return _node == Iterator._node;
}bool operator!=(const self& Iterator)
{
return _node != Iterator._node;
}};
3.key不支持修改问题
由于我们在使用树时,key值是不允许修改的,所以要在构造红黑树对象时,传入constkey
map中: RBTree<K, pair<const K, V>, KeyofV> _root;
typedef typename RBTree<K, pair<const K,V>, KeyofV>::Iterator iterator;
typedef typename RBTree<K, pair<const K,V>, KeyofV>::const_Iterator const_iterator;set中: RBTree<T,const T, KeyofT> _root;
typedef typename RBTree<T, const T, KeyofT>::Iterator iterator;
typedef typename RBTree<T, const T, KeyofT>::const_Iterator const_iterator;
4.map的operator[ ]
迭代器实现后这个重载很简单
V& operator[](const K& key)
{
return insert(make_pair(key, V())).first->second;
}
5.map实现
include了红黑树的头文件
template<class K,class V>
class mymap
{
struct KeyofV
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};RBTree<K, pair<const K, V>, KeyofV> _root;
public:
typedef typename RBTree<K, pair<const K,V>, KeyofV>::Iterator iterator;
typedef typename RBTree<K, pair<const K,V>, KeyofV>::const_Iterator const_iterator;iterator begin()
{
return _root.begin();
}iterator end()
{
return _root.end();
}const_iterator begin() const
{
return _root.cbegin();
}const_iterator end() const
{
return _root.cend();
}iterator find(const K& key)
{
return _root.find(key);
}pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _root.insert(kv);
}V& operator[](const K& key)
{
return insert(make_pair(key, V())).first->second;
}};
6.set实现
include了红黑树的头文件
template<class T>
class myset
{
struct KeyofT
{
const T& operator()(const T& key)
{
return key;
}
};
RBTree<T,const T, KeyofT> _root;
public:
typedef typename RBTree<T, const T, KeyofT>::Iterator iterator;
typedef typename RBTree<T, const T, KeyofT>::const_Iterator const_iterator;
iterator begin()
{
return _root.begin();
}iterator end()
{
return _root.end();
}const_iterator begin() const
{
return _root.cbegin();
}const_iterator end() const
{
return _root.cend();
}pair<iterator,bool> insert(const T& key)
{
return _root.insert(key);
}iterator find(const T& key)
{
return _root.find(key);
}
};
7.封装后的红黑树
enum color
{
red,
black
};template<class T>
struct RBTree_node
{
T _data;
RBTree_node<T>* _left = nullptr;
RBTree_node<T>* _right = nullptr;
RBTree_node<T>* _parent = nullptr;
color _color = black;RBTree_node(const T& data = T())
:_data(data)
{}
};template<class T,class ref,class ptr>
struct RBTree_Iterator
{
typedef RBTree_node<T> Node;
Node* _node;
Node* _root;
typedef RBTree_Iterator<T, ref, ptr> self;RBTree_Iterator(Node* node, Node* root)
:_node(node)
,_root(root)
{}self& operator++()
{
if (_node->_right)
{
_node = _node->_right;
while (_node->_left)
{
_node = _node->_left;
}
}
else
{
if (_node != _root)
{
Node* parent = _node->_parent;
while (parent->_left != _node)
{
if (parent == _root)
{
_node = nullptr;
return *this;
}
_node = parent;
parent = _node->_parent;
}
_node = parent;
}
else
{
_node = nullptr;
}
}
return *this;
}self& operator--()
{
if (!_node)
{
_node = _root->_parent->_right;
}
else if (_node->_left)
{
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
}
else
{
if (_node != _root)
{
Node* parent = _node->_parent;
while (parent->_right != _node)
{
if (parent == _root)
{
_node = nullptr;
break;
}
_node = parent;
parent = _node->_parent;
}
_node = parent;
}
else
{
_node = nullptr;
}
}
return *this;
}ref operator*()
{
return _node->_data;
}ptr operator->()
{
return &_node->_data;
}bool operator==(const self& Iterator)
{
return _node == Iterator._node;
}bool operator!=(const self& Iterator)
{
return _node != Iterator._node;
}};
template<class K,class T,class KeyofT>
class RBTree
{
typedef RBTree_node<T> node;
node* _phead;node* Copy(node* root)
{
if (!root)
return nullptr;node* newroot = new node(root->_data);
newroot->_color = root->_color;
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);return newroot;
}void Destory(node* root)
{
if (!root)
return;Destory(root->_left);
Destory(root->_right);
delete root;
}void rotateL(node* root)
{
node* child = root->_right;
node* childchild = child->_left;
node* rootparent = root->_parent;
node* _root = getroot();root->_right = childchild;
if (childchild) childchild->_parent = root;child->_parent = rootparent;
if (root == _root) rootparent->_parent = child;
else
{
if (rootparent->_left == root) rootparent->_left = child;
else if (rootparent->_right == root) rootparent->_right = child;
else assert(false);
}
root->_parent = child;
child->_left = root;
}void rotateR(node* root)
{
node* child = root->_left;
node* childchild = child->_right;
node* rootparent = root->_parent;
node* _root = getroot();root->_left = childchild;
if (childchild) childchild->_parent = root;child->_parent = rootparent;
if (root == _root) rootparent->_parent = child;
else
{
if (rootparent->_left == root) rootparent->_left = child;
else if (rootparent->_right == root) rootparent->_right = child;
else assert(false);
}
root->_parent = child;
child->_right = root;
}void rotateLR(node* root)
{
node* orootp = root->_parent;
rotateL(root);
rotateR(orootp);
}void rotateRL(node* root)
{
node* orootp = root->_parent;
rotateR(root);
rotateL(orootp);
}int _Height(node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}size_t _size(node* root)
{
if (!root) return 0;
return _size(root->_left) + _size(root->_right) + 1;
}node* getroot()
{
if (_phead->_parent)
return _phead->_parent;
return nullptr;
}const node* getroot()const //记得重载const版本,不然会出错
{
return _phead->_parent ? _phead->_parent : nullptr;
}public:
typedef RBTree_Iterator<T, T&, T*> Iterator;
typedef RBTree_Iterator<T, const T&, const T*> const_Iterator;RBTree()
{
_phead = new node;
_phead->_left = _phead->_right = _phead;
};/*RBTree(const RBTree<K,T,KeyofT>& tmp)
{
_phead->_parent = Copy(tmp._phead->_parent);
if (_phead->_parent) _phead->_parent->_parent = _phead;
}RBTree<K, T, KeyofT>& operator=(RBTree<K,T,KeyofT> tmp)
{
swap(_phead, tmp._phead);
return *this;
}*/~RBTree()
{
Destory(getroot());
delete _phead;
_phead = nullptr;
}//iterator
Iterator begin()
{
node* _root = getroot();
if(_root)
return Iterator(_phead->_left, _root);
return Iterator(_root, _root);
}Iterator end()
{
return Iterator(nullptr, getroot());
}const_Iterator cbegin() const
{
const node* _root = getroot();
if (_root)
return const_Iterator(_phead->_left, const_cast<node*>(_root));
return const_Iterator(const_cast<node*>(_root), const_cast<node*>(_root));
}const_Iterator cend() const
{
return const_Iterator(nullptr, const_cast<node*>(getroot()));
}pair<Iterator,bool> insert(const T& data)
{
node* _root = getroot();
KeyofT kot;//获取key值用来比较if (!_root) {
_root = new node(data);
_phead->_parent = _phead->_left = _phead->_right = _root;
_root->_parent = _phead;
return make_pair(Iterator(_root, _root), true);
}
else
{
node* cur = _root;
node* newnode = new node(data);
node* parent = _root;
newnode->_color = red;while (cur)
{
if (kot(data) > kot(cur->_data))
{
cur = cur->_right;
if (cur)
parent = parent->_right;
}
else if (kot(data) < kot(cur->_data))
{
cur = cur->_left;
if (cur)
parent = parent->_left;
}
else
return make_pair(Iterator(cur,_root), false);
}node* u = nullptr;
newnode->_parent = parent;
if (kot(parent->_data) < kot(data))
{
parent->_right = newnode;
}
else if (kot(parent->_data) > kot(data))
{
parent->_left = newnode;
}if (newnode == _phead->_left->_left) _phead->_left = newnode;
if (newnode == _phead->_right->_right) _phead->_right = newnode;//维护头结点的左右指针node* g = parent->_parent;
cur = newnode;
while (g)
{
if (parent->_color == black)
break;
else
{
if (g->_left == parent) u = g->_right;
else u = g->_left;
if (u && u->_color == red)
{
g->_color = red;
parent->_color = u->_color = black;
//更新cur g parent u
cur = g; parent = cur->_parent;
if (!parent) break;
g = parent->_parent;
}
else
{
if (parent->_left == cur && g->_left == parent)
{
rotateR(g); parent->_color = black; g->_color = red;
}
else if (parent->_right == cur && g->_right == parent)
{
rotateL(g); parent->_color = black; g->_color = red;
}
else if (parent->_right == cur && g->_left == parent)
{
rotateLR(parent); g->_color = red; cur->_color = black;
}
else if (parent->_left == cur && g->_right == parent)
{
rotateRL(parent); g->_color = red; cur->_color = black;
}
break;
}
}
}
getroot()->_color = black;
return make_pair(Iterator(newnode, _root), true);
}
}int Height()
{
return _Height(getroot());
}int Size()
{
return _size(getroot());
}node* leftmin()
{
return _phead->_left;
}node* rightmax()
{
return _phead->_right;
}Iterator find(const T& data)
{
KeyofT kot;
node* cur = getroot();
while (cur)
{
if (kot(cur->_data) < kot(data))
cur = cur->_right;
else if (kot(cur->_data) > kot(data))
cur = cur->_left;
else
return Iterator(cur, getroot());
}
return Iterator(nullptr, getroot());
}bool blacknum(node* root, int sum, int num)
{
if (!root)
{
if (num == 0) num = sum;
return num == sum;
}if (root->_color == black) sum += 1;
return blacknum(root->_left, sum, num) && blacknum(root->_right, sum, num);}
bool singlered(node* root)
{
if (!root) return true;if (root->_color == red && root->_parent->_color == red) return false;
return singlered(root->_left) && singlered(root->_right);
}bool IsBalanceTree()
{
node* _root = getroot();
if (!_root) return true;
if (_root->_color != black) return false;if (!blacknum(_root, 0, 0)) return false;
if (!singlered(_root)) return false;
return true;
}
};
小知识
1.C++可以使用范围for来遍历数组,相当于使用指针(特殊的迭代器)来遍历
2.java/c++中 负数 % 整数 = 负数 a%p = n ----》修正 = (a%p+p)%p 使结果为正