封装红黑树实现map/set

标签：node map 结点 set parent 迭代 typedef 红黑树 type

封装红黑树实现mymap和myset

补充一下AVL树和红黑树的对比：

#include<iostream>
using namespace std;
#include<vector>
#include<time.h>
#include"RBTree.h"
#include"AVLTree.h"

void TestTree()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin1 = clock();
	RBTree<int, int> rbt;
	for (auto e : v)
	{
		rbt.Insert({e,e});
	}
	size_t end1 = clock();
	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.insert({e,e});
	}
	size_t end2 = clock();

	cout << "RB Insert:" << end1 - begin1 << endl;
	cout << "AVL Insert:" << end2 - begin2 << endl;
	cout <<"whether RB balance:"<< rbt.IsBalance() << endl;
	cout <<"whether AVL balance:"<< t.IsBalanceTree() << endl;
	cout << "RB height:" << rbt.Height() << endl;
	cout << "AVL height:" << t.Height() << endl;
	cout << "RB size:" << rbt.Size() << endl;
	cout << "AVL size:" << t.Size() << endl;
	

}

int main()
{
	TestTree();

	return 0;
}

打印结果：

1.源码及框架分析

SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件中。

map和set的实现结构框架核⼼部分截取出来如下：

// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_set.h>
#include <stl_multiset.h>

// map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_map.h>
#include <stl_multimap.h>

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
 // typedefs:
 typedef Key key_type;
 typedef Key value_type;
private:
 typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;
 rep_type t; // red-black tree representing set

};

// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
 typedef Key key_type;
 typedef T mapped_type;
 typedef pair<const Key, T> value_type;

private:
 typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
 rep_type t; // red-black tree representing map

};

// stl_tree.h
struct __rb_tree_node_base
{
 typedef __rb_tree_color_type color_type;
 typedef __rb_tree_node_base* base_ptr;
 color_type color; 
 base_ptr parent;
 base_ptr left;
 base_ptr right;
};

// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc 
= alloc>
class rb_tree {
protected:
 typedef void* void_pointer;
 typedef __rb_tree_node_base* base_ptr;
 typedef __rb_tree_node<Value> rb_tree_node;
 typedef rb_tree_node* link_type;
 typedef Key key_type;
 typedef Value value_type;
public:
 // insert⽤的是第⼆个模板参数做形参 
 pair<iterator,bool> insert_unique(const value_type& x);
 
 // erase和find⽤第⼀个模板参数做形参 
 size_type erase(const key_type& x);
 iterator find(const key_type& x);
protected:
 size_type node_count; // keeps track of size of tree
 link_type header;
};

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
 typedef __rb_tree_node<Value>* link_type;
 Value value_field;
};

按照传统的理解，set与map应该实现两棵红黑树因为set存key，map要存pair。

实际却不是

可以看到，set怎么也有key_type和value_type两个？

rep_type t可以看到里面没有其他东西，就是一个红黑树。

看看map的：

也是有key_type和value_type，但是map正常，为什么set也这样？

我们看看，还包含了这个<stl_tree.h>

这个头文件中没有用枚举来实现颜色：

可以看到结点搞了个base基类

继承。结点里面的值叫做value_field，是由模版决定的。

所以我们并不知道这个红黑树里面到底要存什么

迭代器，这也是个基类

可以看到继承它的：

左右旋可以看到里面命名都是x、y

这是调平衡：

可以看出，x是当前结点，y是叔叔

map和set要用这一棵红黑树来实现出key和key_value的

我们回到关键的代码部分：

结点类型是模版参数决定的，也就是没有写死的。

红黑树的第二个参数决定了结点里存什么

我们可以看到，set的key_type、value_type其实都是Key的typedef

所以也可以看到，set内部在实例化红黑树的时候，传递的前两个其实都是Key。

typedef rb_tree<key_type,value_type,identity<value_type>,key_compare,Alloc> rep_type;

而在map，我们看到：

可以看到key_type是key，mapped_type是T，而value_type是pair，内部实现的红黑树传过去的参数是key和pair。

所以我们可以看到，set和map传给红黑树的第二个参数决定了结点存储的是什么类型。

这样设计的好处和优势是什么事呢？

我们把红黑树的数据类型泛型化了。迭代器和const迭代器也是类似。

通过传第二个参数Ref（传T&或者const T&）来决定是实例化普通迭代器还是const迭代器

里面进行typedef来实现

模版的本质是把我们做的事交给编译器来做

我们只写一个类模版，最后还是由编译器生成两个类

编译器实例化出key的rb_tree和pair<K,V>的rb_tree

回到这里来看

rb_tree的Key和Value不是学map时传统意义的Key和Value了，这个Value不是我们说的那种映射值value。

我们看到set里面是把Key重命名为value_type然后传递给红黑树的第二个参数；在map里则是把pair<const Key,T>重命名为value_type然后传递给红黑树的第二个参数。

map的pair<const Key,T>的T就是我们传统意义说的那个映射值value

rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型，为什么还要传第⼀个模板参数Key呢？尤其是set，两个模板参数是⼀样的，这是很多同学这时的⼀个疑问。要注意的是对于 map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形 参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，mapinsert的 是pair对象，但是find和ease的是Key对象。

set传两个模版参数是为了和map兼容

pair支持的比较：

first小它就小，如果first不小那second小就小。其中一个小就小，这不是我们期望的。

我们期望用first比较，second不参与

但因为是一个泛型所以我们不能这样写：

那么库里面是怎么解决这个问题的呢？

库里面给了第三个模版参数：KeyofValue

因为RBTree实现了泛型不知道T参数导致是K，还是pair，那么insert内部进⾏插⼊逻辑 ⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任 何时候只⽐较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较，具体 细节参考如下代码实现。

Myset.h:

#include"RBTree.h"

namespace momo
{
	template<class K, class V>
	class set
	{
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		RBTree<K, K,SetKeyofT> _t;
	};
}

Mymap.h:

#include"RBTree.h"

namespace momo
{
	template<class K, class V>
	class map
	{
		struct MapKeyofT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	private:
		RBTree<K, pair<K, V>,MapKeyofT> _t;
	};
}

RBTree.h:

//……
template<class K, class T,class KeyofT>
class RBTree
{
	using Node = RBTreeNode<T>;//typedef结点
public:
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}

		KeyofT kot;
		Node* cur = _root;
		Node* parent = nullptr;//记录父亲
		while (cur)
		{
			if (kot(cur->_data) < kot(data))//pair是支持比较的但是并非期望的
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
                //……

iterator

看看源码：

可以看出就是typedef红黑树的，所以迭代器的关键就在红黑树这一层

可以看到源码在迭代器这里也搞了一层抽象，也就是搞了个基类

这个基类里面包含一个结点的指针

然后基类里还写了increment和decrement

可以看到，重载了operator*，也就是说解引用迭代器得到结点里面的值，对于set就是拿到key，对于map就是拿到pair

++/–

红黑树的迭代器和链表的迭代器是十分类似的。在结构和特性上都没什么区别。

它与链表迭代器最大的不同在于++ --的逻辑不同

链表的++是很简单的，就是从一个结点走到下一个结点，node=node->next就可以了

搜索树走中序遍历是最有意义的，所以它迭代器走的是中序遍历

中序遍历对于搜索树的重要性原因

数据有序性的体现

• 当对二叉搜索树进行中序遍历时，得到的节点序列是按照节点值从小到大（或从大到小，取决于树的定义）的顺序排列的。这是因为二叉搜索树的性质决定了左子树节点值小于根节点值，右子树节点值大于根节点值。通过中序遍历，正好可以按照从小到大的顺序依次访问节点。例如，对于二叉搜索树（3 为 5 的左子节点，7 为 5 的右子节点），中序遍历的结果是，呈现出有序的状态。
• 这种有序性使得中序遍历在很多场景下非常有用。比如在数据排序方面，如果有一组数据存储在二叉搜索树中，通过中序遍历就可以快速地获取排好序的数据，而不需要额外的排序操作。

方便查找和范围查询

• 由于中序遍历后的序列是有序的，在进行查找操作时可以利用这种有序性。例如，要查找一个值是否在二叉搜索树所代表的数据集合中，可以通过中序遍历得到的有序序列，使用二分查找等高效的查找算法。
• 对于范围查询，比如要查找所有介于某个区间内的值，中序遍历后的有序序列可以方便地定位到这个区间的起始和结束位置，从而快速提取出符合条件的节点。相比其他遍历方式（如前序遍历和后序遍历），中序遍历更符合这种范围查询的需求。前序遍历的顺序是根节点 - 左子树 - 右子树，后序遍历的顺序是左子树 - 右子树 - 根节点，它们得到的序列都没有这种自然的有序性用于范围查询。

与数据库索引结构的联系

• 在数据库的索引结构中，B 树（B - tree）和 B + 树是常用的索引结构，它们是平衡的多路搜索树。B + 树的叶子节点形成一个有序链表，中序遍历 B + 树的叶子节点可以得到按照索引键值排序的数据。这种有序性和二叉搜索树中序遍历的有序性类似，使得在数据库进行范围查询和排序操作时能够高效地利用索引结构。例如，在一个数据库表的索引列构建了 B + 树索引，通过中序遍历 B + 树的叶子节点，可以快速地获取按照索引列排序的数据，用于查询和排序等操作。

怎么走中序遍历？以前我们都是递归走，但现在不是递归了，递归是一下调用一个函数，把整棵树走完了，但现在我们要的是一个结点一个结点地走。

有一种方式是利用栈，但这里我们不用栈来模拟实现。

刚才我们看的increment和decrement其实就是用来做这个的，++就是调用increment，–调用decrement

——

第一个位置的迭代器在哪里？或者说begin返回哪个结点呢？中序的第一个

最左结点就是中序的第一个。

iterator实现思路分析

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现迭代器像指针⼀样访问的⾏为。

• 这⾥的难点是operator++和operator–的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛ 的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10 所在结点的迭代器。

• 迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。

• 迭代器++时，如果it指向的结点的右⼦树不为空，代表当前要访问下⼀个结点是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。

• 迭代器++时，如果it指向的结点的右⼦树空，代表当前结点所在的⼦树访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上 找。

右子树空的情况有多种：

这个15和25都是右子树为空的情况

如果“我”是父亲的左，下一个访问的是父亲，如果我是父亲的右，我访问完了父亲也访问完了，要再往上一层去找。不一定是爷爷，可能是曾祖父、曾曾祖父…我们要找的是孩子是父亲的左的那个祖先！

（因为我们访问的顺序是中序，左根右，所以如果我是父亲的右，说明左根右已经走到右了所以父亲也已经访问完了，要再往上层走：

此时10是18的左，我们找到了祖先里是父亲左的那个，所以从15这个结点++我们要到18.

所以这里不需要利用栈，不需要记录什么东西，有三叉链，就可以这样做。这是结构优势。

• 如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结 点的⽗亲；

• 如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完 了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找 到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。

• end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18 到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这时⽗亲为空了，那我们就把it中的结点指针 置为nullptr，我们⽤nullptr去充当end。需要注意的是stl源码红⿊树增加了⼀个哨兵位头结点 做为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤ nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是–end()判断到结点时空，特殊处理⼀下，让迭代器结点指向最右结点。具体参考迭代器–实现。

template<class T,class Ref,class Ptr>//因为要const的也能用这个实例化
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

	RBTreeIterator(Node* node)
		:_node(node)
	{}



	Ref operator*()
	{
		return _node->_data;//“解引用”迭代器就像解引用指针得到的是节点里面存储的值，key或者pair值
	}

	Ptr operator->()
	{
		return &_node->_data;//operator->就是返回结点里面数据的指针，这样迭代器就可以用->了
	}

	bool operator== (const Self& s) const
	{
		return _node == s._node;
	}

	bool operator!= (const Self& s) const

	{
		return _node != s._node;
	}


};

template<class K, class T,class KeyofT>
class RBTree
{
	using Node = RBTreeNode<T>;//typedef结点

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);
	}
	Iterator End()
	{
		return Iterator(nullptr);
	}
    //……

类模板取内嵌类的问题！

typedef typename RBTree<K, K, SetofKey>::Iterator iterator;//内嵌类型要加typename，与静态成员变量作区分，否则编译器分不清，因为实例化了才会去里面找，为了让编译时语法先过（因为变量不能typedef，类型才可以）

现在我们就差一个++的逻辑了

Self operator++()
{
	if (_node->_right)//右不为空的情况
	{
		//找右树最左结点
		Node* min = _node->_right;
		while (min->_left)
		{
			min = min->_left;
		}

		_node = min;
	}
	else//右为空，找祖先里面孩子是父亲左的那个祖先
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;//这个parent可能为空，相当于it指向end()了
	}
	return *this;
}

小问题（不符合搜索树不能修改的性质）

template<class K, class T,class KeyofT>
class RBTree
{
	
public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
    //……

template<class T,class Ref,class Ptr>//因为要const的也能用这个实例化
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;
    
    Ref operator*()
    {
        return _node->_data;//“解引用”迭代器就像解引用指针得到的是节点里面存储的值，key或者pair值
    }

但是搜索树是不支持修改的，而我们现在重载的*返回的是Ref，也就是引用，就可以被修改。

源码的实现方式比较复杂也有坑（insert返回值）。

可以看到set这里把const迭代器直接同时作为普通迭代器和const迭代器的底层

一种简单的解决方式是：

namespace momo
{
	template<class K>
	class set
	{	
        //……
    private:
        RBTree<K, const K,SetKeyofT> _t;
};

古怪的报错

这里真正的问题在于我们set里面的_t是const K的但是typedef处没改

public:
	typedef typename RBTree<K, K, SetKeyofT>::Iterator iterator;
	typedef typename RBTree<K, K, SetKeyofT>::ConstIterator const_iterator;

iterator的类型就不匹配了

但是map就不能这样改了，因为pair第二个参数是pair，而我们是要pair的first不能修改，second可以修改。

这里我们就参考库里面的巧妙做法

所以我们就在map里把map的数据成员改成这样：

迭代器typedef也得跟着改

实现–

也就是rbegin rend

–就是右根左的顺序

it如果走到这个位置，说明右子树已经访问完了：

左不为空就访问左，访问的是左的最大结点，也就是左的最大结点

如果左为空，那就去找祖先里第一个孩子为右的祖先

如果现在走到25这里，25访问完了，因为25是父亲的左，右根左所以父亲也结束了，所以去找祖先里第一个孩子为右的祖先

和++逻辑反过来

Self operator--()
{
	if (_node->_left)
	{
		//左不为空，中序左子树最后一个（最大）
		Node* rightMost = _node->_left;
		while (rightMost->_right)
		{
			rightMost = rightMost->_right;
		}
		_node = rightMost;
	}
	else
	{
		//左子树为空，向上找孩子为父亲右的那个祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (cur == parent->_left)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = cur;
	}
	return *this
}

哨兵位

要注意的是库里面源码是有哨兵位的。

（这个link_type就是结点指针）

哨兵位的左指向最左结点，右指向最右结点。

现在end()就不是空了，而是header

可以看到leftmost()直接就能返回最左节点，不用去找了（最差高度次，也还好）

哨兵位和原本的头结点互为parent，所以比如it在50，一直++自然走到header，所以哨兵位会变成end()

如果我们要header，也会有相应的代价，因为我们要维护header的_left和 _right，插入、删除、旋转都得维护（比如旋转完根变了）。

不用header也会有缺陷，在于

没有反向迭代器但实现了倒着遍历，

如果是有哨兵位的版本，那么end()–我们需要走到实际的最后一个结点，所以这里我们是要header–后走到50这个结点

所以就写一个这样的判断：

源码把哨兵位给成红色，能够与黑色的根节点进行区分。所以节点为红，且结点的parent的parent等于自己，这就是哨兵位。

为什么不直接判断header？因为树里面才有header这个成员变量，迭代器里面没有header这个成员变量，迭代器里面只有_node。

我们也可以用特殊处理来解决end()–的问题：

Self operator--()
{
	if (_node == nullptr)//--end();
	{
		//如果有header哨兵位版本，确实找最右结点更方便
		//要找最右结点，但是迭代器里连根都没有，要传过来
		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 = parent->_parent;
		}
		_node = parent;
	}
	return *this
}

operator[]

map的返回值不是一个单纯的bool值：

而是返回的是一个pair

这个返回值pair的first也就是这个迭代器，如果insert成功返回的是新插入的元素迭代器或者是如果插入失败（说明这个key已存在），返回这个相同key值的元素的迭代器。

我们需要将insert的返回值进行修改

pair<Iterator, bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;

		//return pair<Iterator, bool>(Iterator(_root, _root), true);
		return { Iterator(_root, _root), true };
	}

V& operator[](const K& key)/
{
	pair<iterator, bool> ret = insert({ key, V() });
	return ret.first->second;
}

剩下就没有什么了

析构函数、反向迭代器、拷贝函数……

这个析构是一个后序的

拷贝是深拷贝：

这是一个前序的拷贝，先拷贝根再递归拷贝左子树和右子树

本文结束

标签：node,map,结点,set,parent,迭代,typedef,红黑树,type
From： https://blog.csdn.net/2301_82135086/article/details/144635126