目录

1. 红黑树的迭代器++和--

2. 改造红黑树3. set的模拟实现4. map的模拟实现5. RBTree的改造代码

博客主页 : 酷酷学

正文开始

1. 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明

打开C++的源码我们可以发现, 其实源码中的底层大概如下图所示:

这里额外增加了一个header指针, 有了这个指针可以更方便的找到根节点, 并且可以比较容易的实现反向遍历, 可以看到set和map都是双向迭代器, 但是缺点就是需要不断的维护begin()这个要返回的节点, 所以我们这里为了也是先正反向迭代器, 也避免过于麻烦, 我们暂且讲_root也一并传过来, 方便我们找到根节点

<code>template<class T,class Ref,class Ptr>

struct RBTreeIterator

{ -- -->

typedef RBTreeNode<T> Node;

typedef RBTreeIterator<T,Ref,Ptr> self;

Node* _node;

Node* _root;

RBTreeIterator(Node* node,Node* root)

:_node(node)

, _root(root)

{ }

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;

}

};

在BSTree中, 有了模板Ref, 和Ptr当我们需要const迭代器就比较方便

typedef RBTreeIterator<T,T&,T*> Iterator;

typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

Iterator Begin()

{

Node* leftMost = _root;

while (leftMost && leftMost->_left)

{

leftMost = leftMost->_left;

}

return Iterator(leftMost,_root);

}

Iterator End()

{

return Iterator(nullptr,_root);

}

ConstIterator Begin() const

{

Node* leftMost = _root;

while (leftMost && leftMost->_left)

{

leftMost = leftMost->_left;

}

return ConstIterator(leftMost, _root);

}

ConstIterator End() const

{

return ConstIterator(nullptr,_root);

}

++和–

对于++,我们由局部到整体分析,首先如果右不为空, 那么我们要访问下一个节点就是右子树的最左节点.

如果右为空, 我们就需要访问孩子是父亲左的那个祖先,因为中序的遍历的顺序为左 根 右,当前节点访问完了, 说明我这棵树的左根右访问完了, 要去访问上一棵树的根.

<code>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 = cur->_parent;

}

_node = parent;

}

return *this;

}

对于–操作,就是按照右 根 左的操作, 和++反着来, 因为我们要模拟实现反向迭代, 所以当节点为空时,也就是end()时, 我们–之后要返回到最后一个节点

self& operator--()

{

if (_node == nullptr)

{

//--end()

Node* rightMost = _root;

while (rightMost && rightMost->_right)

{

rightMost = rightMost->_right;

}

_node = rightMost;

}

else if (_node->_left)

{

Node* rightMost = _node->_left;

while (rightMost->_right)

{

rightMost = rightMost->_right;

}

_node = rightMost;

}

else

{

//找孩子是右的那个父亲

Node* cur = _node;

Node* parent = cur->_parent;

while (parent && cur == parent->_left)

{

cur = parent;

parent = cur->_parent;

}

_node = parent;

}

return *this;

}

2. 改造红黑树

对于map和set底层存放的一个是key,一个是key_value, 难道我们需要为此适配不同的红黑树吗, 其实不是, 我们来看一下源码. 这里不管是map还是set都是同一棵树, 只是对它进行了改造.

这里的key就是key, 而value_type如果是set就是key, 如果是map就是pair. 那么为什么不省略第一个key, 既然存在即合理, 因为对于set来说无所谓, 但是对于map来说呢, 如果只有pair, 那么怎么比较呢? 我们需要的比较方式是按照pair中的key来比较, 但是pair的底层比较方法并不是, 还有关于find函数, 我们实现查找难道要传递一个pair查找吗, 那如何实现英汉互译那种场景呢?既然知道pair了那还有什么必要查找呢?

C++STL底层pair的比较方法

所以我们进行改造, 统一讲key和pair改为模板T

<code>template<class K,class T,class KeyOfT>

class RBTree

{ -- -->

typedef RBTreeNode<T> Node;

public:

typedef RBTreeIterator<T,T&,T*> Iterator;

typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

pair<Iterator,bool> Insert(const T& data)

{

//

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, _root), false);

}

}

}

Iterator Find(const K& key)

{

//

}

private:

Node* _root = nullptr;

};

对于比较逻辑, 我们可以创建一个仿函数进行实现

map:

template<class K,class V>

class map

{

struct MapKeyOfT

{

const K& operator()(const pair<K, V>& kv)

{

return kv.first;

}

};

set:

template<class K>

class set

{

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

3. set的模拟实现

<code>#include"RBTree.h"

namespace my

{ -- -->

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>::Iterator 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);

}

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;

cout << *it << " ";

}

cout << endl;

}

void test_set()

{

set<int> s;

int a[] = { 4,2,6,1,3,5,15,7,16,14 };

for (auto e : a)

{

s.insert(e);

}

for (auto e : s)

{

cout << e << " ";

}

set<int>::iterator it = s.end();

while (it != s.begin())

{

--it;

cout << *it << " ";

}

cout << endl;

}

}

4. map的模拟实现

<code>#include"RBTree.h"

namespace my

{ -- -->

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);

}

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;

};

void test_map()

{

map<string, string> dict;

dict.Insert({ "sort","排序" });

dict.Insert({ "left","左边" });

dict.Insert({ "right","右边" });

map<string, string>::iterator it = dict.begin();

while (it != dict.end())

{

cout << it->first<<it->second << endl;

++it;

}

dict["left"] = "左边,剩余";

dict["insert"];

dict["string"] = "字符串";

cout << endl;

for (const auto& e : dict)

{

cout << e.first << e.second << endl;

}

}

}

5. RBTree的改造代码

<code>#pragma once

#include<iostream>

#include<vector>

#include<assert.h>

using namespace std;

enum Colour

{ -- -->

RED,

BLACK

};

template<class T>

struct RBTreeNode

{

T _data;

RBTreeNode* _left;

RBTreeNode* _right;

RBTreeNode* _parent;

Colour _col;

RBTreeNode(const T& data)

: _data(data)

, _left(nullptr)

, _right(nullptr)

, _parent(nullptr)

{ }

};

template<class T,class Ref,class Ptr>

struct RBTreeIterator

{

typedef RBTreeNode<T> Node;

typedef RBTreeIterator<T,Ref,Ptr> self;

Node* _node;

Node* _root;

RBTreeIterator(Node* node,Node* root)

:_node(node)

, _root(root)

{ }

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 = cur->_parent;

}

_node = parent;

}

return *this;

}

self& operator--()

{

if (_node == nullptr)

{

//--end()

Node* rightMost = _root;

while (rightMost && rightMost->_right)

{

rightMost = rightMost->_right;

}

_node = rightMost;

}

else if (_node->_left)

{

Node* rightMost = _node->_left;

while (rightMost->_right)

{

rightMost = rightMost->_right;

}

_node = rightMost;

}

else

{

//找孩子是右的那个父亲

Node* cur = _node;

Node* parent = cur->_parent;

while (parent && cur == parent->_left)

{

cur = parent;

parent = cur->_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<T> Node;

public:

typedef RBTreeIterator<T,T&,T*> Iterator;

typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

Iterator Begin()

{

Node* leftMost = _root;

while (leftMost && leftMost->_left)

{

leftMost = leftMost->_left;

}

return Iterator(leftMost,_root);

}

Iterator End()

{

return Iterator(nullptr,_root);

}

ConstIterator Begin() const

{

Node* leftMost = _root;

while (leftMost && leftMost->_left)

{

leftMost = leftMost->_left;

}

return ConstIterator(leftMost, _root);

}

ConstIterator End() const

{

return ConstIterator(nullptr,_root);

}

RBTree() = default;

RBTree(const RBTree& t)

{

_root = Copy(t._root);

}

RBTree& operator=(RBTree 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);

}

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, _root), false);

}

}

cur = new Node(data);

Node* newnode = cur;

// 新增节点。颜色红色给红色

cur->_col = RED;

if (kot(parent->_data) < kot(data))

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

// g

// p u

if (parent == grandfather->_left)

{

Node* uncle = grandfather->_right;

if (uncle && uncle->_col == RED)

{

// u存在且为红 -》变色再继续往上处理

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

cur = grandfather;

parent = cur->_parent;

}

else

{

// u存在且为黑或不存在 -》旋转+变色

if (cur == parent->_left)

{

// g

// p u

//c

//单旋

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// p u

// c

//双旋

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

else

{

// g

// u p

Node* uncle = grandfather->_left;

// 叔叔存在且为红，-》变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else // 叔叔不存在，或者存在且为黑

{

// 情况二：叔叔不存在或者存在且为黑

// 旋转+变色

// g

// u p

// c

if (cur == parent->_right)

{

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

//g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

_root->_col = BLACK;

return make_pair(Iterator(newnode, _root), true);

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

int Height()

{

return _Height(_root);

}

int Size()

{

return _Size(_root);

}

bool IsBalance()

{

if (_root == nullptr)

return true;

if (_root->_col == RED)

{

return false;

}

// 参考值

int refNum = 0;

Node* cur = _root;

while (cur)

{

if (cur->_col == BLACK)

{

++refNum;

}

cur = cur->_left;

}

return Check(_root, 0, refNum);

}

Iterator Find(const K& key)

{

Node* cur = _root;

while (cur)

{

if (cur->_kv.first < key)

{

cur = cur->_right;

}

else if (cur->_kv.first > key)

{

cur = cur->_left;

}

else

{

return Iterator(cur, _root);

}

}

return End();

}

private:

bool Check(Node* root, int blackNum, const int refNum)

{

if (root == nullptr)

{

//cout << blackNum << endl;

if (refNum != blackNum)

{

cout << "存在黑色节点的数量不相等的路径" << endl;

return false;

}

return true;

}

if (root->_col == RED && root->_parent->_col == RED)

{

cout << root->_kv.first << "存在连续的红色节点" << endl;

return false;

}

if (root->_col == BLACK)

{

blackNum++;

}

return Check(root->_left, blackNum, refNum)

&& Check(root->_right, blackNum, refNum);

}

int _Size(Node* root)

{

return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;

}

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;

}

void _InOrder(Node* root)

{

if (root == nullptr)

{

return;

}

_InOrder(root->_left);

cout << root->_kv.first << ":" << root->_kv.second << endl;

_InOrder(root->_right);

}

void RotateL(Node* parent)

{

Node* subR = parent->_right;

Node* subRL = subR->_left;

parent->_right = subRL;

if (subRL)

subRL->_parent = parent;

Node* parentParent = parent->_parent;

subR->_left = parent;

parent->_parent = subR;

if (parentParent == nullptr)

{

_root = subR;

subR->_parent = nullptr;

}

else

{

if (parent == parentParent->_left)

{

parentParent->_left = subR;

}

else

{

parentParent->_right = subR;

}

subR->_parent = parentParent;

}

}

void RotateR(Node* parent)

{

Node* subL = parent->_left;

Node* subLR = subL->_right;

parent->_left = subLR;

if (subLR)

subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;

parent->_parent = subL;

if (parentParent == nullptr)

{

_root = subL;

subL->_parent = nullptr;

}

else

{

if (parent == parentParent->_left)

{

parentParent->_left = subL;

}

else

{

parentParent->_right = subL;

}

subL->_parent = parentParent;

}

}

void Destroy(Node* root)

{

if (root == nullptr)

return;

Destroy(root->_left);

Destroy(root->_right);

delete root;

}

Node* Copy(Node* root)

{

if (root == nullptr)

return nullptr;

Node* newRoot = new Node(root->_kv);

newRoot->_left = Copy(root->_left);

newRoot->_right = Copy(root->_right);

return newRoot;

}

Node* _root = nullptr;

};

完