用红黑树封装map和set
本文详细介绍了红黑树的实现及其在STL容器set和map中的应用。主要内容包括：1）红黑树节点的模板化设计，使其能同时支持set（存储key）和map（存储pair）；2）通过仿函数KeyOfT统一提取节点中的key值，解决不同类型数据比较问题；3）迭代器实现，包括operator++和operator--的中序遍历逻辑；4）红黑树插入操作的完整实现，包括颜色调整和旋转处理；5）set和map的封
·
目录
以前的set和map实现要自己写两颗RBTree，因为set中存储的是key，map中存储的是pair，现在我们对set和map进行封装，也就是使用同一个模板RBTree让编译器实例化出set和map两个类
通过给set和map传入不同的模板参数，在各自的类里实例化出参数个数相同但参数类型不同的红黑树
我们先看源代码
set的第二个模板参数为value_type，类型是Key；map的第二个模板参数为value_type，类型是pair<const Key，T>。注意：T为单个数值的类型(我们常说的value)，value_type（pair）为红黑树节点存储的数据类型
我们再往深挖一下
我们可以看到源码中rb_tree有5个模板参数，通过传入不同的Value（key/pair<key，value>）来实现存储数据的类型不同，进而实现对set和map的不同实例化。
第一个困境：
为什么BTree类的第二个模板参数Value中包含key，但还要传入第一个key模板参数呢？
如果是insert（const Value& v）就刚刚好，但如果是find（const Key& key），得传入key，因此就需要第一个模板参数。
第二个困境：
为什么BTree类的第二个模板参数Value中包含key，但还要传入第三个模板参数仿函数KeyOfT，来取出Value中的key呢？
比如 Insert(const Value& data) BTreeNode<Value>* cur=_root;(Value可能是key/pair)
我们当然可以通过第二个模板参数Value从中这样取出key（set：cur->_data（Value--key）；map：cur->_data.first（Value.first--key））但是BRTree模板的代码只有一份，我们得统一形式；
所以使用一个仿函数KeyOfT，来取出 data中的key，KeyOfT(cur->_data)，这样将Key作为形参时，代码就相同了。
封装set和map的红黑树的实现
我们对红黑树的框架进行修改，修改成模板
这里key用K，value用V，红黑树节点中存储的的类型用T，T可能是key/pair
这里我们不知道红黑树节点中存储的数据类型是啥，因此对T实现泛型
1.我们先对RBTreeNode红黑树节点修改
将存储的数据类型泛化为T，T可能是set存储的key，也可能是map存储的pair，就看set/map的模板参数传啥实例化了
2.接着对RBTree修改
如上文所说，红黑树还需要实现find/erase，需要通过key来实现，因此增加第一个模板参数Key；插入insert时，形参传入T，第一步得通过T中的key找到待插入的位置，但下层红黑树内部RBTree不知道是传入的T data是key还是pair，但是上层set/map中知道T的类型，在外部定义仿函数，然后传给BTree模板，因此增加第三个模板参数，取出T中的key，通过仿函数来实现。
先通过insert理解一下仿函数的作用
insert插入得先通过Key找到待插入的位置，通过不同类中的仿函数，取出T中的Key。
可以直接比较cur->_data与data吗？
传入set比较K，传入map比较pair也挺好的呀，
但cur->_data不能与data直接比较，因为data的类型不知到是K，还是pair；是K那就直接比较，但如果是pair，它的比较逻辑是比完K还要比value
因此我们需要实现仿函数KeyOfValue直接取出value中的K。
迭代器的实现
用一个迭代器类型RBTreeIterator封装节点的指针，这个类中再加上其他成员函数，重载运算符来实现
先定义一个迭代器的类
template<class T, class Ref, class Ptr>//T,T&,T*
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;//当前节点
RBTreeIterator(Node* node)
:_node(node)
{ }
};当前迭代器中包含一个成员，当前迭代器所处节点_node.
为了让迭代器像指针一样使用，先对*，->进行运算符重载
//模拟指针解引用,返回迭代器当前指向节点中存储的元素值的引用
Ref operator*()
{
return _node->_data;
}
//模拟指针的成员访问，当存储的是结构体时，直接访问对象的成员，返回元素的指针。
Ptr operator->()
{
return &_node->_data;
}
//判断两个迭代器是否指向同一个节点（即是否指向容器中的同一个元素）。
operator==((const Self& s) const
{
return _node == s._node;
}
operator!=((const Self& s) const
{
return _node != s._node;
}在RBTree中实现
1.begin（），返回首元素的迭代器，也就是二叉搜索树中的最小元素，在最左边。
2.end（），返回最后一个元素的下一个位置，也就是nullptr
//迭代器
template<class T, class Ref, class Ptr>//T,T&,T*
struct RBTreeIterator
{
typedef RBTNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Node* _node;//当前节点
RBTreeIterator(Node* node)
:_node(node)
{ }
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBNode<T> Node;
typedef RBTreeIterator<T, T&, T*> Iterator;
public:
Iterator Begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur);
}
Iterator End()
{
return Iterator(nullptr);
}
private:
Node* _root = nullptr;
};const迭代器也是如此，在旁边加上const修饰，保证this指向的对象的内容不能被修改
ConstIterator Begin() const//const保证this指针指向的对象内容不能被修改
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur);
}
ConstIterator End() const
{
return ConstIterator(nullptr);
}迭代器类中实现
operator++（），红黑树走中序遍历（左子树-根-右子树），++意味着当前节点已经访问完，该访问的下一个节点是右子树的中序的第一个。
因此有两种情况：
1.该节点有右子树，访问右子树的最左节点
2.该节点的右子树为空，说明以该节点为根的子树已经遍历完了，又分为两种情况
1）当前的子树是父亲的左子树，那++之后就该遍历这个父节点了
2）当前的子树是父亲的右子树，说明父亲和父亲的右和左已经遍历完，以父节点为根的子树已经遍历完；然后循环判断 以父节点为根的子树 是祖父的左还是右，如果是左的话，就遍历祖父节点，如果是右的话，那就说明以祖父节点为根节点的子树已经遍历完。一直循环，最差_node到根节点，父亲为nullptr（此时++，迭代器指向有效元素的下一个位置，返回null迭代器）。
Self operator++()
{
if (_node->_right != nullptr)//右子树不为空，找右子树的最左节点
{
Node* min = _node->_right;//minright！=nullptr
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else//右子树为空
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == _node)//最差到根节点
{
_node = parent;
parent = parent->_parent;
}
_node = parent;//即使parent==null，说明_node 为根，++后返回迭代器末尾null也合理
}
return *this;//返回的是该对象的迭代器，迭代器内部的当前节点_node改成parent，相当于移动了
}operator--（），红黑树走中序遍历，--之后遍历当前节点的左子树的最大值（左子树的最右边/左子树中序遍历的最后一个）
分两种情况：
1.该节点有左子树，访问左子树的最右节点
2.该节点没有左子树，--表示要找比当前节点更小的值，但以当前节点为根的子树已经不可能存在；当前节点是父亲的右节点，那就返回父亲；当前节点是父亲的左节点，继续循环，如果父亲是祖父的右节点，返回祖父，如果父亲是祖父的左节点，还需继续返回到上一层。一直循环，最差到根节点。（此时_node--，返回null迭代器）
这种情况有点特殊，在迭代器内部应该引入一个新的成员变量_root，因为如果是--end（）的话，当前_node = nullptr，应该返回最大的有效元素，也就是树的最右边的节点，此时就需要根节点_root寻找最右边的节点。
Self operator--()
{
//_node=nullptr,也就是--end
//迭代器中只有当前所处节点，现在成员中应该加上根节点
if (_node == nullptr)
{
Node* max = _root;//找右子树的最大值
while (max->_right)
{
max = max->_right;
}
_node = max;
}
//左不为空，找左子树中的最大值
else if(_node->_left)
{
Node* max = _root->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* parent = _node->_parent;
while (parent && parent->_left==_node)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}所以，最终的迭代器类框架应该长这样：
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
typedef RBNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;//当前迭代器所处节点
Node* _root;//根节点，--end
RBTreeIterator(Node* node,Node* root)
:_node(node)
,_root(root)
{ }
};有两个成员变量，那其他的函数应该跟随改动，也就是初始化迭代器的时候传入当前节点和根节点。
红黑树成员函数的实现
接下来在红黑树中实现插入
1.先通过仿函数找到key进而找到插入位置
2.红黑树的插入逻辑
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = BLACK;
return true;
}
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 false;
}
}
cur = new Node(data);
//开始插入，parent为红，grandfather为黑，uncle为红，cur为红
cur->_color = RED;
//链接节点
//判断这新节点cur插入到parent的左边还是右边
if (kot(cur->_data) < kot( parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//调整颜色
//父亲的颜色为红
while (parent && parent->_color == RED)
{
Node* grandparent = parent->_parent;//parent必存在，否则parent为根
//先判断父亲在爷爷的左边还是右边,这样才能确定u的位置
if (grandparent->_left == parent)
{
// g
//p u
Node* uncle = grandparent->_right;
//情况1
//叔叔存在，且叔叔的颜色为红
if (uncle && uncle->_color == RED)
{
parent->_color = BLACK;
uncle->_color = BLACK;
//爷爷肯定为黑，把它变红
grandparent->_color = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
//情况2,叔叔不存在，或者叔叔存在但颜色为黑
else
{
//已知p为g的左边，判断c是否为p的左边
if (parent->_left == cur)
{
//g进行右单旋
RotateR(grandparent);
//变色，p变黑，g变红
parent->_color = BLACK;
grandparent->_color = RED;
}
else//p在g的左边，c在p的右边
{
//进行双旋
RotateL(parent);
RotateR(grandparent);
//接着变色，c变黑，g变红
cur->_color = BLACK;
grandparent->_color = RED;
}
break;
}
}
else//父亲在爷爷的右边
{
Node* uncle = grandparent->_left;//叔叔在爷爷的左边
//情况1，叔叔存在且为红
if (uncle && uncle->_color == RED)
{
//变色，不用旋转
parent->_color = BLACK;
grandparent->_color = RED;
uncle->_color = BLACK;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
//情况2，叔叔不存在；或者叔叔存在且为黑
//旋转+变色
else
{
//单旋
if (parent->_right == cur)//cur在parent的右边
{
//左旋
RotateL(grandparent);
//变色
parent->_color = BLACK;
grandparent->_color = RED;
}
//双旋
else//cur在parent的左边
{
//parent右旋
RotateR(parent);
//grandfather左旋
RotateL(grandparent);
//变色
cur->_color = BLACK;
grandparent->_color = RED;
}
break;
}
}
}
//直接将_root变成黑色
_root->_color = BLACK;
return true;
}接下来要解决map和set中key不能修改的问题：
只需要在set和map类里分别传入不同的const模板参数来实例化出不能修改的key红黑树就行
set的iterator不支持修改，那就将set的第二个模板参数K改成const K；map的iterator不支持修改K，但支持修改value，将pair的第1个模板参数改为const K。
set：RBTree<K，K， SetKeyOfT> _t 改成 RBTree<K，const K， SetKeyOfT> _t;
map：RBTree<K, pair<K, V>, MapKeyOfT> _t 改成 RBTree<K, pair<const K, V>, MapKeyOfT> _t;
注意也要将这里的重命名修改一下，加const，避免实例化出来的end中iterator与Iterator类型不匹配。
map中的成员函数operator[]
map中的 [] 是通过insert实现的
当key存在时，返回已存在元素值的引用，当然也可以修改
当key不存在时，插入一个以key为键，对应值为默认构造的元素
1.首先先修改insert
将返回值改成pair<iterator,bool>，
pair<Iterator,bool> Insert(const T& data)
{
//1.不存在，则插入
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = BLACK;
//return pair<Iterator, bool>(Iterator(_root), true);
return { Iterator(_root,_root), true };
}
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
{
//2.存在,返回已经存在的节点
return { Iterator(cur,_root), false };
}
}
cur = new Node(data);
Node* newnode = cur;
//开始插入，parent为红，grandfather为黑，uncle为红，cur为红
cur->_color = RED;
//链接节点
//判断这新节点cur插入到parent的左边还是右边
if (kot(cur->_data) < kot(parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//调整颜色
//父亲的颜色为红
while (parent && parent->_color == RED)
{
Node* grandparent = parent->_parent;//parent必存在，否则parent为根
//先判断父亲在爷爷的左边还是右边,这样才能确定u的位置
if (grandparent->_left == parent)
{
// g
//p u
Node* uncle = grandparent->_right;
//情况1
//叔叔存在，且叔叔的颜色为红
if (uncle && uncle->_color == RED)
{
parent->_color = BLACK;
uncle->_color = BLACK;
//爷爷肯定为黑，把它变红
grandparent->_color = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
//情况2,叔叔不存在，或者叔叔存在但颜色为黑
else
{
//已知p为g的左边，判断c是否为p的左边
if (parent->_left == cur)
{
//g进行右单旋
RotateR(grandparent);
//变色，p变黑，g变红
parent->_color = BLACK;
grandparent->_color = RED;
}
else//p在g的左边，c在p的右边
{
//进行双旋
RotateL(parent);
RotateR(grandparent);
//接着变色，c变黑，g变红
cur->_color = BLACK;
grandparent->_color = RED;
}
break;
}
}
else//父亲在爷爷的右边
{
Node* uncle = grandparent->_left;//叔叔在爷爷的左边
//情况1，叔叔存在且为红
if (uncle && uncle->_color == RED)
{
//变色，不用旋转
parent->_color = BLACK;
grandparent->_color = RED;
uncle->_color = BLACK;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
//情况2，叔叔不存在；或者叔叔存在且为黑
//旋转+变色
else
{
//单旋
if (parent->_right == cur)//cur在parent的右边
{
//左旋
RotateL(grandparent);
//变色
parent->_color = BLACK;
grandparent->_color = RED;
}
//双旋
else//cur在parent的左边
{
//parent右旋
RotateR(parent);
//grandfather左旋
RotateL(grandparent);
//变色
cur->_color = BLACK;
grandparent->_color = RED;
}
break;
}
}
}
//直接将_root变成黑色
_root->_color = BLACK;
//3.不存在，直接插入，返回包含新节点迭代器和 true 的 pair
return { Iterator(newnode,_root), true };;
}2.紧接着实现operator[]，返回map中，pair中，value的引用
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });
return ret.first->second;
}sxm::map<string,string> ss;
ss["right"];//不存在则插入;ss["right"];为operator[]返回的值的引用，可以进行修改
ss["left"] = "左边";//插入新节点
ss["left"] = "左边，剩余";//对存在的节点修改实现红黑树的默认成员函数
class BTree
{
public:
//默认成员函数
//1.构造函数
RBTree() = default;
//2.析构函数
~RBTree()
{
Destory(_root);
_root = nullptr
}
//3.拷贝构造函数
RBTree(const RBTree<T>& rb)
{
_root = CopeTree(rb._root, nullptr);
}
private:
Node* _root = nullptr;
void Destory(Node* root)
{
//递归结束条件
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
//递归复制以node为根的子树，返回新子树的根
Node* CopeTree(Node* node, Node* parent)//这一层的新节点node，与上一层的parent
{
//递归结束条件
if (node == nullptr)
return nullptr;
//建立新节点
Node* newnode = new Node(node->_data);
newnode->_color = node->_color;
newnode->_left = CopyTree(node->_left, newnode);//对于node->_left来说，newnode为它的父亲
newnode->_right = CopyTree(node->_right, newnode);
return newnode;
}
};总代码
myset.h
#pragma once
#include "RBTree2.h"
namespace sxm
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K,const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K,const K, SetKeyOfT>::ConstIterator const_iterator;
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);
}
private:
RBTree<K,const K, SetKeyOfT> _t;
};
}mymap.h
#pragma once
#include "RBTree2.h"
namespace sxm
{
template<class K,class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>,MapKeyOfT>::ConstIterator const_iterator;
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);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}RBTree2.h
#pragma once
#include<iostream>
using namespace std;
enum Color
{
RED,
BLACK
};
template<class T>
struct RBNode
{
T _data;
RBNode<T>* _left;
RBNode<T>* _right;
RBNode<T>* _parent;
Color _color;
RBNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{ }
};
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
typedef RBNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;//当前迭代器所处节点
Node* _root;//根节点，--end
RBTreeIterator(Node* node,Node* root)
:_node(node)
,_root(root)
{ }
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->_left)
{
//右不为空
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else
{
//右为空
Node* parent = _node->_parent;
while (parent && parent->_right == _node)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
//_node=nullptr,也就是--end
//迭代器中只有当前所处节点，现在成员中应该加上根节点
if (_node == nullptr)
{
Node* max = _root;//找右子树的最大值
while (max->_right)
{
max = max->_right;
}
_node = max;
}
//左不为空，找左子树中的最大值
else if(_node->_left)
{
Node* max = _root->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* parent = _node->_parent;
while (parent && parent->_left==_node)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K,class T,class KeyOfT>
class RBTree
{
typedef RBNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur,_root);
}
Iterator End()
{
return Iterator(nullptr,_root);
}
Iterator Begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur,_root);
}
Iterator End() const
{
return ConstIterator(nullptr,_root);
}
pair<Iterator,bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = BLACK;
//return pair<Iterator, bool>(Iterator(_root), true);
return { Iterator(_root,_root), true };
}
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 { Iterator(cur,_root), false };
}
}
cur = new Node(data);
Node* newnode = cur;
//开始插入，parent为红，grandfather为黑，uncle为红，cur为红
cur->_color = RED;
//链接节点
//判断这新节点cur插入到parent的左边还是右边
if (kot(cur->_data) < kot(parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//调整颜色
//父亲的颜色为红
while (parent && parent->_color == RED)
{
Node* grandparent = parent->_parent;//parent必存在，否则parent为根
//先判断父亲在爷爷的左边还是右边,这样才能确定u的位置
if (grandparent->_left == parent)
{
// g
//p u
Node* uncle = grandparent->_right;
//情况1
//叔叔存在，且叔叔的颜色为红
if (uncle && uncle->_color == RED)
{
parent->_color = BLACK;
uncle->_color = BLACK;
//爷爷肯定为黑，把它变红
grandparent->_color = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
//情况2,叔叔不存在，或者叔叔存在但颜色为黑
else
{
//已知p为g的左边，判断c是否为p的左边
if (parent->_left == cur)
{
//g进行右单旋
RotateR(grandparent);
//变色，p变黑，g变红
parent->_color = BLACK;
grandparent->_color = RED;
}
else//p在g的左边，c在p的右边
{
//进行双旋
RotateL(parent);
RotateR(grandparent);
//接着变色，c变黑，g变红
cur->_color = BLACK;
grandparent->_color = RED;
}
break;
}
}
else//父亲在爷爷的右边
{
Node* uncle = grandparent->_left;//叔叔在爷爷的左边
//情况1，叔叔存在且为红
if (uncle && uncle->_color == RED)
{
//变色，不用旋转
parent->_color = BLACK;
grandparent->_color = RED;
uncle->_color = BLACK;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
//情况2，叔叔不存在；或者叔叔存在且为黑
//旋转+变色
else
{
//单旋
if (parent->_right == cur)//cur在parent的右边
{
//左旋
RotateL(grandparent);
//变色
parent->_color = BLACK;
grandparent->_color = RED;
}
//双旋
else//cur在parent的左边
{
//parent右旋
RotateR(parent);
//grandfather左旋
RotateL(grandparent);
//变色
cur->_color = BLACK;
grandparent->_color = RED;
}
break;
}
}
}
//直接将_root变成黑色
_root->_color = BLACK;
return { Iterator(newnode,_root), true };;
}
//bool Insert(const T& data)
//{
// if (_root == nullptr)
// {
// _root = new Node(data);
// _root->_color = BLACK;
//
// return true;
// }
// 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 false;
// }
// }
// cur = new Node(data);
// //开始插入，parent为红，grandfather为黑，uncle为红，cur为红
// cur->_color = RED;
// //链接节点
// //判断这新节点cur插入到parent的左边还是右边
// if (kot(cur->_data) < kot( parent->_data))
// {
// parent->_left = cur;
// }
// else
// {
// parent->_right = cur;
// }
// cur->_parent = parent;
// //调整颜色
// //父亲的颜色为红
// while (parent && parent->_color == RED)
// {
// Node* grandparent = parent->_parent;//parent必存在，否则parent为根
//
// //先判断父亲在爷爷的左边还是右边,这样才能确定u的位置
// if (grandparent->_left == parent)
// {
// // g
// //p u
// Node* uncle = grandparent->_right;
//
// //情况1
// //叔叔存在，且叔叔的颜色为红
// if (uncle && uncle->_color == RED)
// {
// parent->_color = BLACK;
// uncle->_color = BLACK;
// //爷爷肯定为黑，把它变红
// grandparent->_color = RED;
// //继续向上处理
// cur = grandparent;
// parent = cur->_parent;
// }
// //情况2,叔叔不存在，或者叔叔存在但颜色为黑
// else
// {
// //已知p为g的左边，判断c是否为p的左边
// if (parent->_left == cur)
// {
// //g进行右单旋
// RotateR(grandparent);
// //变色，p变黑，g变红
// parent->_color = BLACK;
// grandparent->_color = RED;
// }
// else//p在g的左边，c在p的右边
// {
// //进行双旋
// RotateL(parent);
// RotateR(grandparent);
// //接着变色，c变黑，g变红
// cur->_color = BLACK;
// grandparent->_color = RED;
// }
// break;
// }
// }
//
// else//父亲在爷爷的右边
// {
// Node* uncle = grandparent->_left;//叔叔在爷爷的左边
// //情况1，叔叔存在且为红
// if (uncle && uncle->_color == RED)
// {
// //变色，不用旋转
// parent->_color = BLACK;
// grandparent->_color = RED;
// uncle->_color = BLACK;
//
// //继续向上处理
// cur = grandparent;
// parent = cur->_parent;
// }
// //情况2，叔叔不存在；或者叔叔存在且为黑
// //旋转+变色
// else
// {
// //单旋
// if (parent->_right == cur)//cur在parent的右边
// {
// //左旋
// RotateL(grandparent);
// //变色
// parent->_color = BLACK;
// grandparent->_color = RED;
// }
// //双旋
// else//cur在parent的左边
// {
// //parent右旋
// RotateR(parent);
// //grandfather左旋
// RotateL(grandparent);
// //变色
// cur->_color = BLACK;
// grandparent->_color = RED;
// }
// break;
// }
// }
// }
// //直接将_root变成黑色
// _root->_color = BLACK;
// return true;
//}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//b链接到10的左子树
parent->_left = subLR;
if (subLR)
//前提是subLR！=nullptr
//更改subLR的父亲
subLR->_parent = parent;
//记录一下parent->_parent
Node* pparent = parent->_parent;
//10链接到5的右子树
subL->_right = parent;
parent->_parent = subL;
//parent的父节点也得指向新的孩子
//parent有两种情况，1.parent本身是根节点，没有父节点，不用改变父节点的指向,直接改变根节点
//2.parent不是根节点，改变父亲的指向parent->_parent->_left/_right=subL
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;//改变subL的父节点
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//将b链接到10的右子树
parent->_right = subRL;
if (subRL)
//前提subRL！=nullptr
//更新b的父亲
subRL->_parent = parent;
//记录parent的父亲
Node* pparent = parent->_parent;
//将10链接到15的左边
subR->_left = parent;
//更新10的父亲
parent->_parent = subR;
//如果parent不为_root的话，要注意parent->_parent的孩子已经改变
//如果parent为根的话，更新根
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
pparent->_right = subR;
subR->_parent = pparent;
}
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (key>cur->_kv.first)
{
cur = cur->_right;
}
else
return cur;
}
return nullptr;
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
private:
//高度
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;
}
//总节点个数
int _Size(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftsize = _Size(root->_left);
int rightsize = _Size(root->_right);
return leftsize + rightsize + 1;
}
Node* _root = nullptr;
};感谢阅读！
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
30
0- 0
已为社区贡献2条内容
所有评论(0)