map，set底层数据结构红黑树
红黑树
红黑树的概念
①红黑树与AVL树一样都是平衡二叉搜索树
②通过从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点的限制，确保没有一条路径会比其他路径长出俩倍，因而是接近平衡
红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(没有连续的红结点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上,包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树的极端情况
针对第三点我们很容易想到两种极端情况
虽然是AVL时间复杂度的两倍但是在log函数面前2倍并不会很大，二者相差并不大
但AVL树为了保持严格的平衡，条件更加苛刻，代价大
综合来看红黑树更优一些
用红黑树来封装map,set
定义红黑树结点
enum Colour
{
RED,
BLACK,
};
//red-black node
template <class T>
struct RBTreeNode
{
//三叉链
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;//结点储存的数据 map存储pair set存储Key
Colour _col;//结点的颜色
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)//插入新结点颜色为红色
{}
};
红黑树的迭代器
//反向迭代器
//迭代器的适配器
template<class Iterator>
struct ReverseIterator
{
typedef typename Iterator::reference Ref;
typedef typename Iterator::pointer Ptr;
typedef ReverseIterator<Iterator> Self;
Iterator _it;//储存的是正向迭代器
ReverseIterator(Iterator it)
:_it(it)
{
}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return _it.operator->();
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(const Self& s)const
{
return _it != s._it;
}
bool operator==(const Self& s)const
{
return _it == s._it;
}
};
//正向迭代器
//结点储存的数据T
template<class T, class Ref, class Ptr>
struct _TreeIterator
{
typedef Ref reference;
typedef Ptr pointer;
typedef RBTreeNode<T> Node;
typedef _TreeIterator<T, Ref, Ptr> Self;
Node* _node;//指向红黑树结点的指针
_TreeIterator(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;
}
//重点重载operator++ 根据中序遍历走
Self& operator++()
{
//右节点存在 访问右树最左的结点
if (_node->_right)
{
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
//右节点不存在的情况,向上找
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
//说明访问过了
cur = cur->_parent;
parent = parent->_parent;
}
//此时cur结点是parent的左
_node = parent;
}
//如果是最后一个结点++，则返回nullpitr
return *this;
}
//operator--()
Self& operator--()
{
//左节点存在 访问左树最右结点
if (_node->_left)
{
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
//end--返回空节点
return *this;
}
};
红黑树的插入操作
新插入红色结点更好：
插入红色结点，只可能破坏规则3,影响不大
插入黑色结点就会破坏非常关键的规则4，导致左最长路径可能不仅仅是2*log（N）破坏了平衡
预备知识：旋转
1.单旋（以右单旋为例）
大致思路：
①先保存parent的父结点
②让subLR作parent的左
③parent作subL的右
④parent的父节点作subL的parent
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
//判断subLR是否存在
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
parentParent->_left = subL;
else
parentParent->_right = subL;
subL->_parent = parentParent;
}
}
2.双旋（以左右双旋为例）
大致思路：
①先对subL左旋
②再对parent右旋
插入
①插入的结点的parent为黑色：不需要调整，直接插入
②插入的结点的parent是红色：违反规则3，需要调整（关键看Uncle）
1.cur为红，p为红，g为黑，u存在且为红（不分方向）
调整方法：将parent跟uncle变黑，grandfather变红，并且向上检查grandfather的父亲，继续向上调整
此时，cur为红色，为了保持规则3，parent必须变黑，这样左子树增加了一个黑结点，右子树uncle就需要变黑，grandfather就必须变红来保持该子树黑结点数目不变
2.cur为红，p为红，g为黑，u为黑或不存在
调整方法：有两种情况，如果两个红结点不是一条直线就需要双旋，如果是就需要单旋，与AVL树类似
讨论在左边的情况：
代码：
pair<iterator, bool> Insert(const T& data)
{
//如果是空树
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
//仿函数 转化结点储存的T map转化成pair的first set转化成key
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 make_pair(iterator(cur), false);
}
}
Node* newnode = new Node(data);
if (kot(parent->_data) > kot(data))
{
parent->_left = newnode;
newnode->_parent = parent;
}
else
{
parent->_right = newnode;
newnode->_parent = parent;
}
cur = newnode;
//判断是否调色
//父亲存在且为红，有连续的红色结点
while (parent&& parent->_col == RED)
{
Node* grandfather = parent->_parent;
//看叔叔
//左边
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//uncle跟parent为红
if (uncle&& uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else//uncle存在且为黑或者不存在
{
//右单旋情况
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else//左右双旋情况
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//右边情况
{
Node* uncle = grandfather->_left;
if (uncle&& uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle存在且为黑，或者不存在
else
{ //左单旋
if (parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else//右左双旋
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后把根节点置黑
_root->_col = BLACK;
return make_pair(iterator(newnode), 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* grandparent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
{
grandparent->_left = subR;
}
else
{
grandparent->_right = subR;
}
subR->_parent = grandparent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
parentParent->_left = subL;
else
parentParent->_right = subL;
subL->_parent = parentParent;
}
}
模拟实现红黑树的代码
//比较的key //结点储存的 //仿函数用于转化T为key
template<class K, class T, class KeyofT>
class RBTree
{
typedef RBTreeNode<T> Node;
typedef _TreeIterator<T, T&, T*> iterator;
typedef _TreeIterator<T, const T&, const T*> const_iterator;
typedef ReverseIterator<iterator> reverse_iterator;
public:
//反向迭代器
reverse_iterator rbegin()
{
//最右结点
Node* right = _root;
while (right && right->_right)
{
right = right->_right;
}
return reverse_iterator(iterator(right));//反向迭代器中储存正向迭代器
//实现正向迭代器代码的复用
}
reverse_iterator rend()
{
return reverse_iterator(iterator(nullptr));
}
//最左结点
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);//匿名对象
}
iterator end()
{
return iterator(nullptr);
}
RBTree()
:_root(nullptr)
{}
//拷贝构造，operator=
Node* Find(const K& key)
{
KeyofT kot;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<iterator, bool> Insert(const T& data)
{
//如果是空树
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
//仿函数 转化结点储存的T map转化成pair的first set转化成key
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 make_pair(iterator(cur), false);
}
}
Node* newnode = new Node(data);
if (kot(parent->_data) > kot(data))
{
parent->_left = newnode;
newnode->_parent = parent;
}
else
{
parent->_right = newnode;
newnode->_parent = parent;
}
cur = newnode;
//判断是否调色
//父亲存在且为红，有连续的红色结点
while (parent&& parent->_col == RED)
{
Node* grandfather = parent->_parent;
//看叔叔
//左边
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//uncle跟parent为红
if (uncle&& uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else//uncle存在且为黑或者不存在
{
//右单旋情况
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else//左右双旋情况
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//右边情况
{
Node* uncle = grandfather->_left;
if (uncle&& uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle存在且为黑，或者不存在
else
{ //左单旋
if (parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else//右左双旋
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后把根节点置黑
_root->_col = BLACK;
return make_pair(iterator(newnode), 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* grandparent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
{
grandparent->_left = subR;
}
else
{
grandparent->_right = subR;
}
subR->_parent = grandparent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
parentParent->_left = subL;
else
parentParent->_right = subL;
subL->_parent = parentParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* grandparent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
{
grandparent->_left = subR;
}
else
{
grandparent->_right = subR;
}
subR->_parent = grandparent;
}
}
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
~RBTree()
{
Destory(_root);
_root = nullptr;
}
private:
Node* _root;
};
封装set
set的底层就是红黑树，所以我们直接用上面的红黑树封装set
//set是K搜索模型
namespace tzc
{
//key //结点储存的值T
template<class K>
class set
{
//set仿函数
struct SetKeyofT
{
//结点储存的是key直接返回
const K& operator()(const K& key)
{
return key;
}
};
public:
//加typename是因为此时RBTree还没有实例化,所以告诉编译器这是一个类型，等实例化后再去找
typedef typename RBTree<K, K, SetKeyofT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyofT>::reverse_iterator reverse_iterator;
//反向的迭代器
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend;
}
//正向迭代器
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
private:
RBTree<K, K, SetKeyofT> _t;//红黑树
};
}
封装map
map是KV结构
比set多了一个重载[]
namespace tzc
{
template<class K, class V>
class map
{
//仿函数
struct MapKeyofT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;//结点储存的是pair，返回其first
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::reverse_iterator reverse_iterator;
//反向迭代器
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
//最为关键的重载了[]
//multimap并没有重载
V& operator[](const K& key)
{
//无论插入成功或失败都会返回该结点的pair<iterator,bool>
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;//返回该结点V的引用
}
private:
RBTree<K, pair<const K, V>, MapKeyofT> _t;
};
}
map、set设计的巧妙之处
设计地巧妙在于让map和set都复用了红黑树的代码
通过控制结点储存的值不同，传给红黑树的仿函数等不同来实现