前言
在map和set的使用文章中提到了C++STL中的map和set的底层其实就是用的红黑树来实现的,所以可以用红黑树来简单模拟实现一下STL中的map和set.
STL源码中map和set的实现
map:
我们看到它的底层这个成员变量其实就是一棵红黑树, 之前说过map其实就对应搜索树的KV模型，那其实这里的key_type和data_type就对应的是Key和Value的的类型, 还有一个value_type是一个pair, 而且key_type和value_type都传给了红黑树成员.
set:
首先set的底层也是红黑树, 我们会发现map和set底层用的是同一个红黑树的类模板, 但是它们不是一个对应KV模型, 一个对应K模型嘛, 那我们想的可能是应该实现两个红黑树, 一棵存Key的单个值,另一棵存KV的键值对, 然后用这两棵红黑树分别封装map和set。
额外说明一下, stl_map.h里没有包含红黑树的头文件, 但是可以使用红黑树, 因为红黑树是间接包含的,set也是同理:
这里是如何做到map和set底层都用同一个红黑树的类模板呢？
观察红黑树的结点的成员变量, 发现并不能直接观察出红黑树是k模型还是kv模型, 再看红黑树的成员, 用Value对结点做初始化, 简单来说就是红黑树的第二个模板参数决定了node中存的是什么.
rb_tree是k结构还是kv结构是由第二个模板参数决定, 这是泛型编程的思想.
比如map中value_type是一个pair, set中value_type是key, 它们把value_type作为rb_tree的第二个模板参数传递, value_type是什么, 这棵树的结点内容就存什么, 从而决定了他们的k/kv结构.
可以发现set中key_type和value_type都是key, 给rb_tree传了两遍, 这不是重复了吗? 而且map中key_type是key不是可以通过pair获取吗, 为什么还要传一个key_type?
先想一下map和set都有find, erase这些接口, 那它们有什么不同？
set它的查找是按结点里面存的key去查找的, 返回的是对应元素的迭代器.
map它里面存的是KV的键值对, 但是它查找的时候是不是只拿K去查找啊, 因为key是唯一的，而value其实是可以重复的。 因为map里面存的是KV的键值对, 但是查找这些操作的时候是以K为目标去查找的，所以红黑树里面要多搞出来一个参数Key来单独获取这个Key。
那其实对于set来说是不需要的(因为set里面存的就是单独一个key,查找也是用的key, 上面我们也看了, 它传的前两个模板就是一样的, 都是key), 但是因为set要和map共用一个红黑树模板, 所以必须迎合这个红黑树的结构, 也去多传一个。
其实map也可以不用第一个参数, 查找的时候用pair.first就行了, 但是set里面只存了一个key,它不能进行.first, 因为模板是泛型编程,一套逻辑要对所有的实例都适用, 所以红黑树才要增加一个模板参数, 这样红黑树里面的find, erase这些函数就可以以一种统一的实现(即都用第一个模板参数接收的key去查找), 这样map和set才可以共同复用同一个红黑树的模板类.
改造红黑树+封装map和set
红黑树结构修改
结点结构修改:
首先结点的结构只能传一个模板参数来限定类型, 和库中一样:
emplate<class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _right;
RBTreeNode<T>* _left;
T _data;
COLOR _col;
RBTreeNode(const T& data)
: _parent(nullptr)
, _right(nullptr)
, _left(nullptr)
, _data(data)
, _col(RED)
{}
};但我们的跟库里面源码还是不太一样,库里还继承了一个base, 里面又实现了一些其他功能,求最大值最小值之类,但没什么影响。
树的结构也要修改:
template<class Key,class Value>
class RBTree
{
typedef RBTreeNode<Value> Node;
public:
//..成员函数
private:
Node* _root = nullptr;
};map、set的结构定义:
template<class K>
class set
{
public:
//成员函数
private:
RBTree<K,K> rb_tree;
};
template<class K,class V>
class map
{
public:
private:
RBTree<K, pair<const K, V>> rb_tree;
};
因为map里面pair的键key不能修改, 所以我们加一个const, 库里面也是这样的。
insert的封装
其实还是复用红黑树的Insert, 当然之前我们学过map和set的使用, 它们insert的返回值其实是一个pair（只是插入一个元素的那个重载）, 这里先这样写，后面需要的时候再结合具体场景修改。
先粘贴过来:
bool Insert(const Value& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col= BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_data > data)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_data < data)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(data);
//cur->_col = RED;
if (parent->_data >data)
{
parent->_left = cur;
cur->_parent = parent;
}
else if (parent->_data < data)
{
parent->_right = cur;
cur->_parent = parent;
}
else
assert(false);
//插入完成, 调整颜色
parent的颜色是黑,不需要调整
//if (parent->_col == BLACK)
//{
// return true;
//}
//parent的颜色是红,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
//parent在grandparent的左
// g g
// p u p u
//c c
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
{
// g
// p u
//c
if (cur == parent->_left)
{
rotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
// g
// p u
// c
else if (cur == parent->_right)
{
rotateL(parent);
rotateR(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
}
}
//parent在grandparent的左
// g g
// u p u p
// c c
else if (parent == grandparent->_right)
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_right)
{
rotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
// g
// u p
// c
else if (cur == parent->_left)
{
rotateR(parent);
rotateL(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
}
}
_root->_col = BLACK;
}
return true;
}我们前面实现的红黑树是K模型的, 里面的插入就是按照结点里面的_data去比较的
但是现在map和set都是复用这棵红黑树, 所以data里面可能是单独一个key（那就是set实例化的时候）,也可能是一个pair（那就对于map）.
那set肯定没问题, 因为set对应的就是K模型, 内置类型的比较可以直接比较.
那map的时候呢, map的data里面就是存的pair的键值对, 那pair虽然也是可以比较大小的,但是pair比较大小的方式不是我们想要的, 它是pair.first和pair.second里有一个小就小, 我们需要的是pair.first进行比价, 不需要pair.second的参与.
那我们怎么去解决?
一种思路是可以用类型去判断, typeid.name去判断类型:
if(typeid(cu->_data).name == K)
{
//处理set..
}库里面的做法是接收了第三个模板参数, 第三个参数其实就是为了解决这个问题而引入的，它接收一个仿函数, 用这个仿函数取出对应的key值, 先来看map取出pair里面的first, set直接返回key即可:
struct SetKeyOfValue
{
const K& operator()(const K& v)
{
return v;
}
};
struct MapKeyOfValue
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
这个仿函数接收一个pair, 返回里面的first, 然后对于set, 其实是不需要的, 但是为了匹配, 因为它们用了同一个红黑树模板, 所以也要写一个, 然后把这个仿函数传给RBTree的第三个模板参数，这样在红黑树里面，我们不需要管data是单独的key还是pair类型的数据，都可以用一个统一的方式拿到真正用了比较的那个单独的key
bool Insert(const Value& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col= BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (KeyOfValue()(cur->_data) > KeyOfValue()(data))
{
parent = cur;
cur = cur->_left;
}
else if (KeyOfValue()(cur->_data) < KeyOfValue()(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(data);
//cur->_col = RED;
if (KeyOfValue()(parent->_data) > KeyOfValue()(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else if (KeyOfValue()(parent->_data) < KeyOfValue()(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
assert(false);
//插入完成, 调整颜色
parent的颜色是黑,不需要调整
//if (parent->_col == BLACK)
//{
// return true;
//}
//parent的颜色是红,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
//parent在grandparent的左
// g g
// p u p u
//c c
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
{
// g
// p u
//c
if (cur == parent->_left)
{
rotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
// g
// p u
// c
else if (cur == parent->_right)
{
rotateL(parent);
rotateR(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
}
}
//parent在grandparent的左
// g g
// u p u p
// c c
else if (parent == grandparent->_right)
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_right)
{
rotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
// g
// u p
// c
else if (cur == parent->_left)
{
rotateR(parent);
rotateL(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
}
}
_root->_col = BLACK;
}
return true;
}红黑树迭代器实现
迭代器只要实现红黑树的, map和set直接复用就行了, 那红黑树的迭代器呢其实就是结点指针的封装,与list的迭代器差不多
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
}
map中:
set中:
迭代器的begin和end：
begin返回的应该返回指向中序遍历第一个结点的迭代器, 而中序遍历的第一个结点就是整棵树最左边的那个结点。
iterator begin()
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}end返回中序遍历最后一个结点的下一个元素, 最后一个结点后面就没有元素了, 所以我们直接用空指针构造一个迭代器返回就行了
iterator end()
{
return iterator(nullptr);
}const迭代器:
const_iterator begin() const
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}map和set中的begin和end都是一样的, 直接返回红黑树的begin和end:
++和- -的重载:
最开始迭代器it在1这个结点的位置（它是中序遍历第一个）, 其实不论it当前在那个位置, 我们都可以认为它在当前所处的这棵子树的根结点上, 那么根结点访问完, 中序遍历的话下面访问右子树, 那对于右子树来说, 如果它不为空的话, 同样要对它进行中序, 所以it下面要访问的就是it的右子树的最左结点, 前提是右子树不为空.
如果是右为空的情况呢?
1.如果这个结点是它父亲的左子树, 比如22, 22右子树为空相当于访问完了, 它是父亲的左子树, 所以下一个一定要访问它的父亲, 直接访问即可, 不需要其他的判断.
2.如果这个结点是它父亲的右子树, 比如6,6的右子树为空, 相当于6这棵树访问完了, 6是1的右子树, 说明1的右子树访问完了, 1是8的左子树, 所以1这棵树访问完就相当于8的左子树访问完了, 那下面就要访问根结点8了, 所以如果右为空且它是父亲的右子树的话, 我们就应该往上去判断it是不是它父亲的左子树, 如果不是, 就顺着父亲指针往上走(比如27 25 17 13一直走到空), 是的话停下来,代表此时父亲的左子树访问完了,此时这个父亲就是下一个要访问的结点.
Self operator++()
{
if (_node->_right)
{
_node = _node->_right;
while (_node->_left)
{
_node = _node->_left;
}
return _node;
}
else
{
if (_node == _node->_parent->_left)
{
_node = _node->_parent;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return _node;
}
}operator--其实就是跟++的反过来, 中序是左子树,根,右子树, 那- -就右子树、根、左子树.
1. 先判断的左子树为不为空，不为空就访问左子树的最右结点.
2. 如果左为空, 它是父亲的右子树, 那直接返回父亲,比如11
如果它是父亲的左子树, 那就要向上去找it是谁的右子树, 找到的话当前it的这个父亲就是下一个要访问的结点.
Self operator--()
{
if (_node->_left)
{
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
return _node;
}
else
{
if (_node == _node->_parent->_right)
{
_node = _node->_parent;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return _node;
}
}源码的实现跟我们有一些不同:
他给这棵红黑树增加了一个头结点, 头结点的左指针指向最左结点（中序第一个）, 头结点的右指针指向最右结点, 然后它的parent指向根结点, 根结点的parent指向这个头结点.
这样迭代器end就指向这个头结点, 就不为空, 这样的好处是对end–的话可以找到前一个结点,而像上面那样写的end设置为空, end--会出现解引用空指针的问题, 因为我们的end使用空nullptr构造的, 就没法向前寻找前一个结点, 因此最好的方式是将end()放在头结点的位置.
map的[]重载
学习map的使用时,我们知道map重载的[]. 底层是跟insert的返回值有关系的, 所以我们得修改一下红黑树的insert,应该让它返回一个pair:
当插入成功的时候, pair的first为指向新插入元素的迭代器, second为true, 当插入失败的时候(其实就是插入的键已经存在了)，那它的first为容器中已存在的那个元素的迭代器, second为false, 后面这个bool标识插入成功还是失败.
1.如果根是空
2.插入失败
3. 插入成功
map和set里面insert的封装也要改:
map重载[]:
测试:
void test_set()
{
test::set<int> s;
s.insert(4);
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(2);
s.insert(0);
s.insert(10);
s.insert(5);
test::set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_map()
{
test::map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
test::map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
//it->first += 'x'; //修改key会报错
it->second += 'y';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
string arr[] = {"苹果","香蕉","苹果"};
test::map<string, int> countMap;
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
} 
关于元素不能修改的问题
set里面的元素是不能修改的, 因为底层是搜索树, 如果可以随意修改的话就会破坏搜索树的关系;而对于map, key是不可以修改的, 不过value可以修改。
目前的实现中set元素是可以修改的:
如何解决呢？
库里面是怎么解决的：
先来看set里面的迭代器,它里面的普通迭代器和const迭代器都是用的红黑树的const迭代器, 它虽然看起来是普通的迭代器, 但是还是const迭代器, 再写了一个const迭代器是为了符合规范.
所以我们也在这里加上typedef:
但是会出现这个问题:
这里类型转换发生了错误, 因为rb_tree的insert返回的是一个普通迭代器, 而set里虽然形式上写的是iterator, 但是这个iterator其实还是红黑树里的const迭代器, 为什么不能直接让红黑树的insert也返回const迭代器, 这样类型不就符合了吗? 但是这仅仅满足了set, map还要用这个返回值进行修改, 需要的是普通迭代器.
怎么解决?
要想办法让类型匹配起来, 这里就可以利用pair自身的那个既是构造又是拷贝构造的拷贝构造, 
让红黑树里的insert返回值的第一个元素变成Node*, 当它作为set的返回值的时候, set的pair自己根据Node*去构造一个自己的迭代器(const迭代器), 当它作为map的返回值的时候, map的pair根据Node*去构造自己的迭代器(普通迭代器).
编译通过了, 而且想要修改set的值也不行了:
代码
RBTree.h
#pragma once
#include<assert.h>
enum COLOR
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _right;
RBTreeNode<T>* _left;
T _data;
COLOR _col;
RBTreeNode(const T& data)
: _parent(nullptr)
, _right(nullptr)
, _left(nullptr)
, _data(data)
, _col(RED)
{}
};
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self operator++()
{
if (_node->_right)
{
_node = _node->_right;
while (_node->_left)
{
_node = _node->_left;
}
return _node;
}
else
{
if (_node == _node->_parent->_left)
{
_node = _node->_parent;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return _node;
}
}
Self operator--()
{
if (_node->_left)
{
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
return _node;
}
else
{
if (_node == _node->_parent->_right)
{
_node = _node->_parent;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return _node;
}
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class Key,class Value,class KeyOfValue>
class RBTree
{
typedef RBTreeNode<Value> Node;
public:
typedef __RBTreeIterator<Value, Value&, Value*> iterator;
typedef __RBTreeIterator<Value, const Value&, const Value*> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
pair<Node*,bool> Insert(const Value& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col= BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (KeyOfValue()(cur->_data) > KeyOfValue()(data))
{
parent = cur;
cur = cur->_left;
}
else if (KeyOfValue()(cur->_data) < KeyOfValue()(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
cur = new Node(data);
Node* newnode = cur;//需要保存一下cur, 因为最后要返回这个节点, cur在下面的调整中可能会发生变化
if (KeyOfValue()(parent->_data) > KeyOfValue()(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else if (KeyOfValue()(parent->_data) < KeyOfValue()(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
assert(false);
//插入完成, 调整颜色
parent的颜色是黑,不需要调整
//if (parent->_col == BLACK)
//{
// return true;
//}
//parent的颜色是红,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
//parent在grandparent的左
// g g
// p u p u
//c c
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
{
// g
// p u
//c
if (cur == parent->_left)
{
rotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
// g
// p u
// c
else if (cur == parent->_right)
{
rotateL(parent);
rotateR(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
}
}
//parent在grandparent的左
// g g
// u p u p
// c c
else if (parent == grandparent->_right)
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_right)
{
rotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
// g
// u p
// c
else if (cur == parent->_left)
{
rotateR(parent);
rotateL(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
}
}
_root->_col = BLACK;
}
return make_pair(newnode, true);
}
void InOrderPrint()
{
_InOrder(_root);
}
bool IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
Node* cur = _root;
int ref = 0;
while (cur)
{
if (cur->_col == BLACK)
{
ref++;
}
cur = cur->_left;
}
int blacknum = 0;
return _Check(_root, blacknum,ref);
}
/*Node* Find(const K& data)
{
Node* cur = _root;
while (cur)
{
if (kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}*/
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
private:
Node* _root = nullptr;
bool _Check(Node* root,int blacknum, const int ref)
{
if (root == nullptr)
{
if (blacknum != ref)
return false;
return true;
}
if (root->_col == BLACK)
blacknum++;
if (root->_col == RED && root->_parent->_col == RED)
return false;
return _Check(root->_left, blacknum, ref)
&& _Check(root->_right, blacknum, ref);
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
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* parentParent = parent->_parent;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_right)
parentParent->_right = subR;
else if (parent == parentParent->_left)
parentParent->_left = subR;
subR->_parent = parentParent;
}
}
void rotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_left = subLR;
parent->_parent = subL;
if (subLR)
subLR->_parent = parent;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else if (parentParent->_right == parent)
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
};Myset:
#pragma once
namespace test
{
template<class K>
class set
{
struct SetKeyOfValue
{
const K& operator()(const K& v)
{
return v;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfValue>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfValue>::const_iterator const_iterator;
iterator begin() const
{
return rb_tree.begin();
}
iterator end() const
{
return rb_tree.end();
}
pair<iterator,bool> insert(const K& data)
{
return rb_tree.Insert(data);
}
private:
RBTree<K,K, SetKeyOfValue> rb_tree;
};
}mymap:
#pragma once
#include "RBTree.h"
namespace test
{
template<class K,class V>
class map
{
struct MapKeyOfValue
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfValue>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfValue>::const_iterator const_iterator;
//typedef __RBTreeIterator<pair<const K,V>, pair<const K, V>&, pair<const K, V>*> iterator;
iterator begin()
{
return rb_tree.begin();
}
iterator end()
{
return rb_tree.end();
}
pair<iterator, bool> insert(const pair<K,V>& kv)
{
return rb_tree.Insert(kv);
}
V& operator[](const K& k)
{
return (*insert(make_pair(k, V())).first).second;
}
private:
RBTree<K, pair<const K, V>,MapKeyOfValue> rb_tree;
};
}
