目录
1.红黑树源代码
- 我们将对一棵KV模型的红黑树进行封装，同时模拟实现出C++STL库当中的map和set
//枚举定义结点的颜色
enum Colour
{
RED,
BLACK
};
//红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{
//三叉链
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
//存储的键值对
pair<K, V> _kv;
//结点的颜色
int _col; //红/黑
//构造函数
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
//红黑树的实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//构造函数
RBTree()
:_root(nullptr)
{}
//拷贝构造
RBTree(const RBTree<K, V>& t)
{
_root = _Copy(t._root, nullptr);
}
//赋值运算符重载（现代写法）
RBTree<K, V>& operator=(RBTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
//析构函数
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first) //key值小于该结点的值
{
cur = cur->_left; //在该结点的左子树当中查找
}
else if (key > cur->_kv.first) //key值大于该结点的值
{
cur = cur->_right; //在该结点的右子树当中查找
}
else //找到了目标结点
{
return cur; //返回该结点
}
}
return nullptr; //查找失败
}
//插入函数
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
{
_root = new Node(kv);
_root->_col = BLACK; //根结点必须是黑色
return make_pair(_root, true); //插入成功
}
//1、按二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //待插入结点的key值等于当前结点的key值
{
return make_pair(cur, false); //插入失败
}
}
//2、将待插入结点插入到树中
cur = new Node(kv); //根据所给值构造一个结点
Node* newnode = cur; //记录新插入的结点（便于后序返回）
if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
{
//插入到parent的左边
parent->_left = cur;
cur->_parent = parent;
}
else //新结点的key值大于parent的key值
{
//插入到parent的右边
parent->_right = cur;
cur->_parent = parent;
}
//3、若插入结点的父结点是红色的，则需要对红黑树进行调整
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
if (parent == grandfather->_left) //parent是grandfather的左孩子
{
Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
{
//颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+情况3：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)
{
RotateR(grandfather); //右单旋
//颜色调整
grandfather->_col = RED;
parent->_col = BLACK;
}
else //cur == parent->_right
{
RotateLR(grandfather); //左右双旋
//颜色调整
grandfather->_col = RED;
cur->_col = BLACK;
}
break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
}
}
else //parent是grandfather的右孩子
{
Node* uncle = grandfather->_left; //uncle是grandfather的左孩子
if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
{
//颜色调整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+情况3：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)
{
RotateRL(grandfather); //右左双旋
//颜色调整
cur->_col = BLACK;
grandfather->_col = RED;
}
else //cur == parent->_right
{
RotateL(grandfather); //左单旋
//颜色调整
grandfather->_col = RED;
parent->_col = BLACK;
}
break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
}
}
}
_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
return make_pair(newnode, true); //插入成功
}
private: //内部私有函数
//拷贝树
Node* _Copy(Node* root, Node* parent)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyNode = new Node(root->_data);
copyNode->_parent = parent;
copyNode->_left = _Copy(root->_left, copyNode);
copyNode->_right = _Copy(root->_right, copyNode);
return copyNode;
}
//析构函数子函数
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;
//1、建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL) //subRL可能为空
subRL->_parent = parent;
//2.记录pparent
Node* pparent = parent->_parent;
//3.建立parent和subR的关系
subR->_left = parent;
parent->_parent = subR;
//4.建立pparent和subR的关系
if (pparent == nullptr) //parent为根，是一颗单独的树
{
_root = subR;
subR->_parent = nullptr; //subR的_parent指向需改变
}
else
{
if (parent == pparent->_left)
{
pparent->_left = subR;
}
else //parent == pparent->_right
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//1.建立parent和subLR的关系
parent->_left = subLR;
if (subLR) //subLR可能为空
{
subLR->_parent = parent;
}
//2.记录pparent
Node* pparent = parent->_parent;
//3.建立subL和parent的关系
subL->_right = parent;
parent->_parent = subL;
//4.建立pparen和subL的关系
if (parent == _root) //parent是一颗独立的树
{
_root = subL;
_root->_parent = nullptr;
}
else //parent是一颗子树，
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->parent = pparent;
}
}
//左右双旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//右左双旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
Node* _root; //红黑树的根结点
};
2.红黑树模板参数的控制
(1)set是K模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？
①这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。
template<class K, class T>
class RBTree
②T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key
template<class K>
class set
{
public:
//...
private:
RBTree<K, K> _t;
};
③如果是map容器，那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对
template<class K, class V>
class map
{
public:
//...
private:
RBTree<K, pair<K, V>> _t;
};
(2)能不能不要红黑树的第一个模板参数，只保留第二个模板参数呢？
- 看着好像是可以的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但实际上红黑树的第一个模板参数是不能省略的。
- 对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find。
3.红黑树结点当中存储的数据
(1)现在红黑树的模板参数变成了K和T，那么红黑树结点当中存储的应该是什么
- set容器：K和T都代表键值Key。
- map容器：K代表键值Key，T代表由Key和Value构成的键值对。
- 对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。
这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。
(2)更改后的代码
//红黑树结点的定义
template<class T>
struct RBTreeNode
{
//三叉链
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//存储的数据
T _data;
//结点的颜色
int _col; //红/黑
//构造函数
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
4.模板参数中仿函数的增加
(1)由于结点当中存储的是T，这个T可能是Key，也可能是<Key, Value>键值对。那么当我们需要进行结点的键值比较时，应该如何获取结点的键值呢？
- 当上层容器是set的时候T就是键值Key，直接用T进行比较即可，但当上层容器是map的时候就不行了，此时我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较。
- 因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。
- 使用仿函数比使用函数指针的方法更方便
(2)仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现 operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
- 对于底层红黑树来说，它并不知道上层容器是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。
- set容器也需要向底层红黑树传入一个仿函数，虽然这个仿函数单独看起来没什么用，但却是必不可少的。
template<class K, class V>
class map
{
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
{
return kv.first;
}
};
public:
//...
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};template<class K>
class set
{
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key) //返回键值Key
{
return key;
}
};
public:
//...
private:
RBTree<K, K, SetKeyOfT> _t;
};(3)set容器传入底层红黑树的就是set的仿函数，map容器传入底层红黑树的就是map的仿函数。
(4)当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较
- 仿函数更改比较方式，T可以是任意类型，只要传仿函数就能够对T类型进行排序
- 所有进行结点键值比较的地方，均需要通过仿函数获取对应结点的键值后再进行键值的比较。
//查找函数
iterator Find(const K& key)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (key < kot(cur->_data)) //key值小于该结点的值
{
cur = cur->_left; //在该结点的左子树当中查找
}
else if (key > kot(cur->_data)) //key值大于该结点的值
{
cur = cur->_right; //在该结点的右子树当中查找
}
else //找到了目标结点
{
return iterator(cur); //返回该结点
}
}
return end(); //查找失败
}
5.正向迭代器的实现
- 红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。
(1)迭代器的基本实现
--正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
-- Ref 引用 ， Ptr 指针
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;
}
};
(2)红黑树正向迭代器实现时，真正的难点实际上++和--运算符的重载。
①++重载
- 如果当前结点的右子树不为空，则
++操作后应该找到其右子树当中的最左结点。 - 如果当前结点的右子树为空，则
++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。
--前置++
Self& operator++() //中序遍历
{
if (_node->_right)//右不为空
{
//下一个访问的就是右树中，中序的第一个节点(右子树的最左节点)
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left; //++后变为该结点
}
else //右子树等于空(这棵树访问完了) : 沿着三叉链，找孩子不是父亲右的那个祖先
{
//因为cur 右为空，说明cur所在的子树已经访问完了
//如果cur是parent右，说明parent也访问完了
Node* cur = _node;
Node* parent = cur->_parent; //这里表示cur是parent的左子树 //中
while (parent && cur == parent->_right) //cur是parent的右子树
{
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* cur = _node;
Node* parent = cur->_parent;
while (parent&&cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent; //--后变为该结点
}
return *this;
}
(3)begin和end
①正向迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef，因为类型名称太长了。需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。
②然后在红黑树当中实现成员函数begin和end：
- begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
- end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //结点的类型
public:
typedef __TreeIterator<T, T&, T*> iterator; //正向迭代器
iterator begin()
{
//寻找最左结点
Node* left = _root;
while (left&&left->_left)
{
left = left->_left;
}
//返回最左结点的正向迭代器
return iterator(left);
}
iterator end()
{
//返回由nullptr构造得到的正向迭代器（不严谨）
return iterator(nullptr);
}
private:
Node* _root; //红黑树的根结点
};
(4)在C++STL中，底层红黑树实现正向迭代器时所用的结构
- 实际上，上述所实现的迭代器是有缺陷的，因为理论上我们对
end()位置的正向迭代器进行--操作后，应该得到最后一个结点的正向迭代器，但我们实现end()时，是直接返回由nullptr构造得到的正向迭代器的，因此上述实现的代码无法完成此操作。 - C++STL库当中实现红黑树时，在红黑树的根结点处增加了一个头结点，该头结点的左指针指向红黑树当中的最左结点，右指针指向红黑树当中的最右结点，父指针指向红黑树的根结点。
- 在该结构下，实现begin()时，直接用头结点的左孩子构造一个正向迭代器即可，实现rbegin()时，直接用头结点的右孩子构造一个反向迭代器即可（实际是先用该结点构造一个正向迭代器，再用正向迭代器构造出反向迭代器），而实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行--操作后得到最后一个结点的正向迭代器。
- 但实现该结构需要更改当前很多函数的逻辑，例如插入结点时，若插入到了红黑树最左结点的左边，或最右结点的右边，此时需要更新头结点左右指针的指向，这里就不进行实际实现了。
6.反向迭代器的实现
- 红黑树的反向迭代器实际上就是正向迭代器的一个封装，因此红黑树的反向迭代器就是一个迭代器适配器。
(1)在反向迭代器当中只有一个成员变量，那就是反向迭代器封装的正向迭代器。反向迭代器的中成员函数，都是通过调用正向迭代器对应的函数来完成相应功能的。
//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //反向迭代器的类型
typedef typename Iterator::reference Ref; //结点指针的引用
typedef typename Iterator::pointer Ptr; //结点指针
Iterator _it; //反向迭代器是对正向迭代器的封装
//构造函数
ReverseIterator(Iterator it)
:_it(it) //根据所给正向迭代器构造一个反向迭代器
{}
Ref operator*()
{
return *_it; //通过调用正向迭代器的operator*返回结点数据的引用
}
Ptr operator->()
{
return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针
}
//前置++
Self& operator++()
{
--_it; //调用正向迭代器的前置--
return *this;
}
//前置--
Self& operator--()
{
++_it; //调用正向迭代器的前置++
return *this;
}
bool operator!=(const Self& s) const
{
return _it != s._it; //调用正向迭代器的operator!=
}
bool operator==(const Self& s) const
{
return _it == s._it; //调用正向迭代器的operator==
}
};
(2)反向迭代器只接收了一个模板参数，即正向迭代器的类型，也就是说，反向迭代器不知道结点的引用类型和结点的指针类型，因此我们需要在正向迭代器当中对这两个类型进行typedef，这样反向迭代器才能通过正向迭代器获取结点的引用类型和结点的指针类型。
//正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef Ref reference; //结点指针的引用
typedef Ptr pointer; //结点指针
};
(3)反向迭代器实现后，我们也需要在红黑树的实现当中进行迭代器类型的typedef，并在红黑树当中实现成员函数rbegin和rend
- rbegin函数返回中序序列当中最后一个结点的反向迭代器，即最右结点。
- rend函数返回中序序列当中第一个结点前一个位置的反向迭代器，这里直接用空指针构造一个反向迭代器。
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //结点的类型
public:
typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器
reverse_iterator rbegin()
{
//寻找最右结点
Node* right = _root;
while (right && right->_right)
{
right = right->_right;
}
//返回最右结点的反向迭代器
return reverse_iterator(iterator(right));
}
reverse_iterator rend()
{
//返回由nullptr构造得到的反向迭代器（不严谨）
return reverse_iterator(iterator(nullptr));
}
private:
Node* _root; //红黑树的根结点
};
7.set模拟实现
- set的模拟实现，其中的成员函数都是调用底层红黑树的对应接口就行了，只不过需要注意将插入函数和查找函数返回值当中的结点指针改为迭代器即可。
template<class K>
class set
{
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key) //返回键值Key
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //正向迭代器
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//插入函数
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
//查找函数
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
8.map的模拟实现
- map的模拟实现，其成员函数也是调用底层红黑树的对应接口，但对于map来说，除了将插入函数和查找函数返回值当中的结点指针改为迭代器之外，还需要实现
[]运算符的重载函数。
template<class K, class V>
class map
{
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//插入函数
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
//[]运算符重载函数
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
iterator it = ret.first;
return it->second;
}
//查找函数
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
9.封装过后的整体代码
(1)红黑树代码
//枚举定义结点的颜色
enum Colour
{
RED,
BLACK
};
//红黑树结点的定义
template<class T>
struct RBTreeNode
{
//三叉链
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//存储的数据
T _data;
//结点的颜色
int _col; //红/黑
//构造函数
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
//红黑树的实现
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //结点的类型
public:
typedef __TreeIterator<T, T&, T*> iterator; //正向迭代器
typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器
reverse_iterator rbegin()
{
//寻找最右结点
Node* right = _root;
while (right&&right->_right)
{
right = right->_right;
}
//返回最右结点的反向迭代器
return reverse_iterator(iterator(right));
}
reverse_iterator rend()
{
//返回由nullptr构造得到的反向迭代器（不严谨）
return reverse_iterator(iterator(nullptr));
}
iterator begin()
{
//寻找最左结点
Node* left = _root;
while (left&&left->_left)
{
left = left->_left;
}
//返回最左结点的正向迭代器
return iterator(left);
}
iterator end()
{
//返回由nullptr构造得到的正向迭代器（不严谨）
return iterator(nullptr);
}
//构造函数
RBTree()
:_root(nullptr)
{}
//拷贝构造
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = _Copy(t._root, nullptr);
}
//赋值运算符重载（现代写法）
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
{
swap(_root, t._root);
return *this; //支持连续赋值
}
//析构函数
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
//查找函数
iterator Find(const K& key)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (key < kot(cur->_data)) //key值小于该结点的值
{
cur = cur->_left; //在该结点的左子树当中查找
}
else if (key > kot(cur->_data)) //key值大于该结点的值
{
cur = cur->_right; //在该结点的右子树当中查找
}
else //找到了目标结点
{
return iterator(cur); //返回该结点
}
}
return end(); //查找失败
}
//插入函数
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
{
_root = new Node(data);
_root->_col = BLACK; //根结点必须是黑色
return make_pair(iterator(_root), true); //插入成功
}
//1、按二叉搜索树的插入方法，找到待插入位置
KeyOfT kot;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(data) < kot(cur->_data)) //待插入结点的key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (kot(data) > kot(cur->_data)) //待插入结点的key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //待插入结点的key值等于当前结点的key值
{
return make_pair(iterator(cur), false); //插入失败
}
}
//2、将待插入结点插入到树中
cur = new Node(data); //根据所给值构造一个结点
Node* newnode = cur; //记录新插入的结点（便于后序返回）
if (kot(data) < kot(parent->_data)) //新结点的key值小于parent的key值
{
//插入到parent的左边
parent->_left = cur;
cur->_parent = parent;
}
else //新结点的key值大于parent的key值
{
//插入到parent的右边
parent->_right = cur;
cur->_parent = parent;
}
//3、若插入结点的父结点是红色的，则需要对红黑树进行调整
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
if (parent == grandfather->_left) //parent是grandfather的左孩子
{
Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
{
//颜色调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+情况3：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)
{
RotateR(grandfather); //右单旋
//颜色调整
grandfather->_col = RED;
parent->_col = BLACK;
}
else //cur == parent->_right
{
RotateLR(grandfather); //左右双旋
//颜色调整
grandfather->_col = RED;
cur->_col = BLACK;
}
break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
}
}
else //parent是grandfather的右孩子
{
Node* uncle = grandfather->_left; //uncle是grandfather的左孩子
if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
{
//颜色调整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+情况3：uncle不存在 + uncle存在且为黑
{
if (cur == parent->_left)
{
RotateRL(grandfather); //右左双旋
//颜色调整
cur->_col = BLACK;
grandfather->_col = RED;
}
else //cur == parent->_right
{
RotateL(grandfather); //左单旋
//颜色调整
grandfather->_col = RED;
parent->_col = BLACK;
}
break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
}
}
}
_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
return make_pair(iterator(newnode), true); //插入成功
}
private:
//拷贝树
Node* _Copy(Node* root, Node* parent)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyNode = new Node(root->_data);
copyNode->_parent = parent;
copyNode->_left = _Copy(root->_left, copyNode);
copyNode->_right = _Copy(root->_right, copyNode);
return copyNode;
}
//析构函数子函数
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;
//1、建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL) //subRL可能为空
subRL->_parent = parent;
//2.记录pparent
Node* pparent = parent->_parent;
//3.建立parent和subR的关系
subR->_left = parent;
parent->_parent = subR;
//4.建立pparent和subR的关系
if (pparent == nullptr) //parent为根，是一颗单独的树
{
_root = subR;
subR->_parent = nullptr; //subR的_parent指向需改变
}
else
{
if (parent == pparent->_left)
{
pparent->_left = subR;
}
else //parent == pparent->_right
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//1.建立parent和subLR的关系
parent->_left = subLR;
if (subLR) //subLR可能为空
{
subLR->_parent = parent;
}
//2.记录pparent
Node* pparent = parent->_parent;
//3.建立subL和parent的关系
subL->_right = parent;
parent->_parent = subL;
//4.建立pparen和subL的关系
if (parent == _root) //parent是一颗独立的树
{
_root = subL;
_root->_parent = nullptr;
}
else //parent是一颗子树，
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->parent = pparent;
}
}
//左右双旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//右左双旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
Node* _root; //红黑树的根结点
};
(2)正向迭代器代码
//正向迭代器
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; //判断两个正向迭代器所封装的结点是否是同一个
}
//前置++
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 = 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* cur = _node;
Node* parent = cur->_parent;
while (parent&&cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent; //--后变为该结点
}
return *this;
}
};
(3)反向迭代器代码
//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //反向迭代器的类型
typedef typename Iterator::reference Ref; //结点指针的引用
typedef typename Iterator::pointer Ptr; //结点指针
Iterator _it; //反向迭代器所封装的正向迭代器
//构造函数
ReverseIterator(Iterator it)
:_it(it) //根据所给正向迭代器构造一个反向迭代器
{}
Ref operator*()
{
return *_it; //通过调用正向迭代器的operator*返回结点数据的引用
}
Ptr operator->()
{
return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针
}
//前置++
Self& operator++()
{
--_it; //调用正向迭代器的前置--
return *this;
}
//前置--
Self& operator--()
{
++_it; //调用正向迭代器的前置++
return *this;
}
bool operator!=(const Self& s) const
{
return _it != s._it; //调用正向迭代器的operator!=
}
bool operator==(const Self& s) const
{
return _it == s._it; //调用正向迭代器的operator==
}
};
(4)set代码
namespace XM //防止命名冲突
{
template<class K>
class set
{
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key) //返回键值Key
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //正向迭代器
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//插入函数
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
//查找函数
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
(5) map代码
namespace XM //防止命名冲突
{
template<class K, class V>
class map
{
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//插入函数
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
//[]运算符重载函数
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
iterator it = ret.first;
return it->second;
}
//查找函数
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}