set map函数实现
1.模板RBTree.h
#pragma once
#include<iostream>
#include"map"
#include"string"
#include"set"
#include<assert.h>
using namespace std;
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
: _data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};
template<class T, class Ref, class Ptr>
class RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _root;
Node* _node;
RBTreeIterator(Node* node, Node* root)
:_root(root)
, _node(node)
{}
Self& operator++()
{
if (_node->_right)
{
Node* leftMost = _node->_right;
while (leftMost->_left)
{
leftMost = leftMost->_left;
}
_node = leftMost;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
//--end()特殊处理
if (_node == nullptr)
{
Node* begin = _root;
while (begin && begin->_left)
{
begin = begin->_left;
}
_node = begin;
}
else if (_node->_left)
{
Node* RightMost = _node->_left;
while (RightMost && RightMost->_right)
{
RightMost = RightMost->_right;
}
_node = RightMost;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<K> Node;
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> Const_Iterator;
public:
Iterator Begin()
{
Node* leftMost = _root->_left;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return Iterator(leftMost, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
Const_Iterator Begin() const
{
Node* leftMost = _root->_left;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return Const_Iterator(leftMost, _root);
}
Const_Iterator End() const
{
return Const_Iterator(nullptr, _root);
}
RBTree() = default;
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = Copy(t._root);
}
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT > t)
{
swap(_root, t._root);
return *this;
}
~RBTree()
{
Destroy(_root);
_root = nullptr;
}
pair<Iterator, bool> Insert(const T& data)
{
//没有节点直接插入
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(Iterator(_root, _root), true);
}
//找对应的位置 有相同的值返回false
Node* cur = _root;
Node* parent = nullptr;
KeyOfT k;
while (cur)
{
if (data > k(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (data < k(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else return make_pair(Iterator(cur, _root), false);
}
//判断该位置是左孩子还是右孩子
cur = new Node(data);
cur->_col = RED;
Node* newnode = cur;
if (data > k(parent->_data)) parent->_right = cur;
else parent->_left = cur;
cur->_parent = parent;
//调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
//u位置右边
if (grandparent->_left == parent)
{
Node* uncle = grandparent->_right;
//1.u存在且为红 变色+上调
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
//2.u不存在/存在为黑色
else
{
//1.cur 位于p的左边 对g右单旋+变色 此时cur和parent都为红色 （这种情景是由情况1.u存在且为红 变色+上调出现的）
if (cur == parent->_left)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//2.cur 位于p的右边 对p左旋 再对g右单旋+变色
else
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
//处理完后 根节点为黑 各路径黑节点数相等
break;
}
}
//u位于左边
else
{
Node* uncle = grandparent->_left;
//1.u存在且为红 变色+上调
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
//2.u不存在/存在为黑色
else
{
//1.cur 位于p的右边 对g左单旋+变色 此时cur和parent都为红色 （这种情景是由情况1.u存在且为红 变色+上调出现的）
if (cur == parent->_right)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//2.cur 位于p的右边 对p左旋 再对g右单旋+变色
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
//处理完后 根节点为黑 各路径黑节点数相等
break;
}
}
}
//第一种情况u存在为红 g为根，p为空 循环结束，此时g根节点为红色 需要变色
_root->_col = BLACK;
return make_pair(Iterator(newnode,_root), true);
}
Iterator& Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > k(cur->_data))
{
cur = cur->_right;
}
else if (key < k(cur->_data))
{
cur = cur->_left;
}
else return Iterator(cur, _root);
}
return End();
}
void Inorder()
{
_Inorder(_root);
return;
}
private:
Node* _root = nullptr;
void _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_kv.first << "->" << root->_kv.second << ' ';
_Inorder(root->_right);
}
Node* Copy(Node* root, Node* parent)
{
if (root == nullptr) return nullptr;
Node* cur = new Node(root->_kv);
cur->_parent = parent;
cur->_left = Copy(root->_left, cur);
cur->_right = Copy(root->_right, cur);
return cur;
}
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;
Node* parentP = parent->_parent;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (parentP == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = parentP;
if (parentP->_left == parent) parentP->_left = subR;
else parentP->_right = subR;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (parentP == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = parentP;
if (parentP->_left == parent) parentP->_left = subL;
else parentP->_right = subL;
}
}
};
1.树节点结构
set map都可以套用RBTree。如果是set T实例化的类型就是key，map T实例化类型为pair<key,value>
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
: _data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};2.迭代器实现
iterator const_iterator
在重载operator*() operator->()时，参数可能被const修饰。T&operator*() 和 const T&operator*() 只有返回值不同不构成函数重载，不能在同一个类。
这时候就用类模板传不同类型的参数，就可以由编译器实例化出两种迭代器。
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> Const_Iterator;
template<class T, class Ref, class Ptr>
class RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _root;
Node* _node;
RBTreeIterator(Node* node, Node* root)
:_root(root)
, _node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
};operator++()
++是按照中序遍历的顺序来的，左子树 根 右子树
当这个节点的右子树子树遍历完时，以这个节点为根的子树就遍历完了。
我们可以分为两种情况，节点有右孩子，节点没有右孩子。
1.节点有右孩子，右子树最小值就是我们下一个访问的节点，也就是最左边的节点。
2.没有右孩子，说明以这个节点为根的子树就遍历完了。如果这个节点是它父母节点的右孩子，同理以这个父母节点为根的子树就遍历完了。一直向上调，直到该节点不是父母节点的右孩子，或者父母节点不存在。
Self& operator++()
{
if (_node->_right)
{
Node* leftMost = _node->_right;
while (leftMost->_left)
{
leftMost = leftMost->_left;
}
_node = leftMost;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}operator--()
--遍历顺序是和++反过来的，顺序 右子树 根 左子树
同理，当这个节点的左子树子树遍历完时，以这个节点为根的子树就遍历完了。
注意end()我们返回的是nullptr，需要特殊处理end()--就到了中序遍历的最后一个节点也就是最右节点。
Self& operator--()
{
//--end()特殊处理
if (_node == nullptr)
{
Node* rightmost = _root;
while (rightmost && rightmost ->_right)
{
rightmost = rightmost ->_right;
}
_node = rightmost ;
}
else if (_node->_left)
{
Node* RightMost = _node->_left;
while (RightMost && RightMost->_right)
{
RightMost = RightMost->_right;
}
_node = RightMost;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}operator==() operator!=()
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}3.RBTree函数
Bgin() End()
begin()返回最左节点，我们需要找到_root根节点。在迭代器中除了有当前节点的位置，还要存储_root根节点的位置。
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<K> Node;
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> Const_Iterator;
public:
Iterator Begin()
{
Node* leftMost = _root->_left;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return Iterator(leftMost, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
Const_Iterator Begin() const
{
Node* leftMost = _root->_left;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return Const_Iterator(leftMost, _root);
}
Const_Iterator End() const
{
return Const_Iterator(nullptr, _root);
}Insert()插入
insert返回的是pair<iterator , bool>类型，传的参数是类型是T。当我们实例化时，set T 是key，而map T是pair<key,value>。用T data比大小时，pair的比较方式是先比first 如果相同就比second。我们想要的是如果pair.first值相同，就不插入。
所以就需要在map中定义一个仿函数返回key值。（set 中最好也实现，保持相同）
template<class K, class T, class KeyOfT>
class RBTreeKeyOfT是一个类类型，重载operator()，返回key值
pair<Iterator, bool> Insert(const T& data)
{
//没有节点直接插入
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(Iterator(_root, _root), true);
}
//找对应的位置 有相同的值返回false
Node* cur = _root;
Node* parent = nullptr;
KeyOfT k;
while (cur)
{
if (data > k(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (data < k(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else return make_pair(Iterator(cur, _root), false);
}
//判断该位置是左孩子还是右孩子
cur = new Node(data);
cur->_col = RED;
Node* newnode = cur;
if (data > k(parent->_data)) parent->_right = cur;
else parent->_left = cur;
cur->_parent = parent;
//调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
//u位置右边
if (grandparent->_left == parent)
{
Node* uncle = grandparent->_right;
//1.u存在且为红 变色+上调
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
//2.u不存在/存在为黑色
else
{
//1.cur 位于p的左边 对g右单旋+变色 此时cur和parent都为红色 （这种情景是由情况1.u存在且为红 变色+上调出现的）
if (cur == parent->_left)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//2.cur 位于p的右边 对p左旋 再对g右单旋+变色
else
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
//处理完后 根节点为黑 各路径黑节点数相等
break;
}
}
//u位于左边
else
{
Node* uncle = grandparent->_left;
//1.u存在且为红 变色+上调
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
//2.u不存在/存在为黑色
else
{
//1.cur 位于p的右边 对g左单旋+变色 此时cur和parent都为红色 （这种情景是由情况1.u存在且为红 变色+上调出现的）
if (cur == parent->_right)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//2.cur 位于p的右边 对p左旋 再对g右单旋+变色
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
//处理完后 根节点为黑 各路径黑节点数相等
break;
}
}
}
//第一种情况u存在为红 g为根，p为空 循环结束，此时g根节点为红色 需要变色
_root->_col = BLACK;
return make_pair(Iterator(newnode,_root), true);
}Find
Iterator& Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > k(cur->_data))
{
cur = cur->_right;
}
else if (key < k(cur->_data))
{
cur = cur->_left;
}
else return Iterator(cur, _root);
}
return End();
}2.Set.cpp
#include"RBTree.h"
namespace wws
{
template<class K>
class myset
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::Const_Iterator const_iterator;
public:
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
void Print(const set<int>& s)
{
set<int>::const_iterator it = s.end();
while (it != s.begin())
{
--it;
//*it += 2;
cout << *it << " ";
}
cout << endl;
}
}3.Map.cpp
#include"RBTree.h"
namespace wws
{
template<class K, class V>
class mymap
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Const_Iterator const_iterator;
public:
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator find(const K& key)
{
return _t.Find(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}operator[]
我们找到operator[]底层也是套用的insert()，key值存在就可以修改它的value,不存在可以新建。ret.first是pair<iterator,bool>中的iterator。
ret.first->second 是pair<key,value>_data的value (编译器省略了一个箭头)
Ptr operator->()
{
return &_node->_data;
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}原文地址：https://blog.csdn.net/wws7920/article/details/140672437
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！