一.红黑树

1.红黑树的迭代器

迭代器是一个相对来说比较复杂得东西.首先我们知道模拟得迭代器,实际上就是一个节点得指针.包含++,-- 以及对节点得基本操作.

template<class T , class ref, class ptr>
struct _rb_iterator
{
	typedef RBTreeNode<T> Node;
	typedef _rb_iterator<T, ref, ptr> self;
	

	Node* _node;
	Node* _root;
	_rb_iterator(Node* node, Node* root = nullptr)
		:_node(node),_root(root)
	{ }

	typedef _rb_iterator<T, T&, T* > iterator;
	//无论模板构造的是_rb_iterator<T, T&, T* > 还是_rb_iterator<T, const T&, const T* >  
	///iterator都是_rb_iterator<T, T&, T* >
	//这就是实现了 ,将普通迭代器,转换为从上图迭代器.
	_rb_iterator(const iterator& it) 
		:_node(it._node),_root(it._root){
	}
	//原本的迭代器是,const迭代器和 普通迭代器不是相同的类型,不是同一个类型的东西.
	//这里使用了将一个普通迭代器 构造出来一个const迭代器

	ref operator*()
	{
		return _node->_data;
	}
	ptr operator->()
	{
		return &(_node->_data);
	}

	self& operator++()
	{
		//迭代器在当前节点的时候说明左子树已经全部 遍历完成,
		//下一步是 右子树或者 祖先节点(nullptr)
		if (_node == nullptr)
		{
			cout << "end() 不能 ++" << endl;
			return *this;
		}
		if (_node->_right != nullptr)
		{
			//下一步是遍历右子树的最小节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else {
			//下一步是遍历祖先.
			Node* cur = _node;
			Node* parent = cur->_parent;
			
			while (parent && parent->_left != cur)
			{
				cur = cur->_parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	self& operator--()
	{
		//这里假设 end() 和 iterator(nullptr)相同
		if (_node == nullptr)
		{
			//就是本来是 : end() ,现在需要 --
			Node* root = _root;
			while (root->_right)
			{
				root = root->_right;
			}
			_node = root;
			return *this;
		}

		//node 不是空
		if (_node->_left)
		{
			//node的左节点不是空
			//找到左树的最大节点

			Node* max = _node->_left;
			while (max->_right)
			{
				max = max->_right;
			}

			_node = max;
		}
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;

			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	bool operator!=(const self& it) const
	{
		return _node != it._node;
	}

	bool operator==(const self& it) const
	{
		return _node == it._node;  
	}
};

前面是迭代器基本得具体实现,其中得++和--得逻辑很新,建议反复观看,怎么通过父指针找到下一个节点.

2.红黑树的修改

前面的文章中我们讲解了红黑树的结构和实现.这一节课我们直接使用上一个文章中实现的红黑树,因为set和map都是底层都是使用红黑树实现的,而且使用的都是同一个红黑树模板实现的,这里就要稍微修改一下我们上节课实现的红黑树模板了,使他能够实现set和map共用一个红黑树.

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	

public:
	//这个需要共有化,因为在外部需要从定义.
	typedef _rb_iterator<T, T&, T*> iterator;
	typedef _rb_iterator<T, const T&, const T*> const_iterator;
	
	
	RBTree()
		:_root(nullptr)
	{}


	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		cout << "iterator begin" << endl;
		return iterator(cur, _root);
	}

	iterator end()
	{
		cout << "iterator end" << endl;
		return iterator(nullptr, _root);
	}

	const_iterator begin() const 
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		cout << "const_iterator begin" << endl;
		return const_iterator(cur, _root);
	}

	const_iterator end() const 
	{
		cout << "const_iterator end" << endl;		
		return const_iterator(nullptr, _root);
	}

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

		Node* parent = nullptr;
		Node* cur = _root;
		//找到要插入的位置
		while (cur)
		{
			if (kot(data) > kot(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(data) < kot(cur->_data)) {
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return  pair<iterator, bool>(iterator(cur, _root), false);;
			}
		}
		
		//插入
		
		cur = new Node(data);
		cur->_col = RED;
		Node* ret = cur;
		//默认给红色
		//因为插入黑了一定违背规则
		//插入红色亦可能违背规则,有可能不违背规则
		//减少调整
		if (kot(parent->_data)> kot(data))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//此处cur是当前插入节点
		//parent是cur的父节点
		//开始调节
		//开始检测是否符合规则,并且进行处理

		//如果父节点的颜色是黑色的话不需要调节,直接退出


		//如果父节点的颜色是红色的话 需要一直向上调节
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{//左边的三种情况

				//情况一:叔叔存在且为红
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况二或者情况三:叔叔不存在 / 叔叔存在且为黑
				{
					if (parent->_left == cur)
					{//情况二
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (parent->_right == cur)
					{//情况三
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						parent->_col = grandfather->_col = RED;
					}
					else 
					{
						assert(false);
					}

				}


			}
			else if (grandfather->_right == parent)
			{//右边的三种情况

				//情况一:叔叔存在且为红
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况二或者情况三:  叔叔不存在 / 叔叔存在且为黑
				{
					if (parent->_left == cur)
					{//情况三
						RotateR(parent);
						RotateL(grandfather);
						parent->_col = RED;
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (parent->_right == cur)
					{//情况二
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						assert(false);
					}
				}
			}
			else
			{
				assert(false);
			}
		}

		_root->_col = BLACK;
		return  pair<iterator, bool>(iterator(ret, _root), true);;
		
	}

	void print()
	{
		int count = 0;
		_print(_root, count);
		cout << endl;
	}

先给出修改完成后的容貌. 观察上面的修改之后的红黑树模板.(没有实现删除部分).我们在使用set和map的时候发现set是只有一个key,而相反map是key和val组成的一个键值对.

//再map中红黑树模板这样使用
RBTree<K, pair<const K,V>, KeyOfT > _rb_tree;

//再set中红黑树模板这样使用
RBTree<K, K, KeyOfT > _rb_tree;

这就实现了怎么共用一个模板实现两个不同的容器.

还有就是end和begin得具体指向那个节点得问题,再stl库中得实现不是这样写的,这个仁者见仁智者见智,我的方法肯定有缺陷,库里面在红黑树得前面根节点添加了一个哨兵位得头节点,end()指向得是哨兵位得头节点,我为了防便直接使用得是nullptr代替得.建议大家在修改红黑树得时候加上哨兵位得头节点.

二.set的具体实现

	template<class K>
	class set
	{
		struct KeyOfT
		{
			const K& operator()(const K& val)
			{
				return val;
			}
		};

	public:
		//typedef typename RBTree<K, K, KeyOfT >::iterator iterator;
		//是否是const迭代器底层都应该使用const迭代器,因为,set是不允许修改的, 无论是T&和 T*都没有修改权限.
		typedef typename RBTree<K, K, KeyOfT >::const_iterator iterator;
		//iterator应该使用const_iterator
		typedef typename RBTree<K, K, KeyOfT >::const_iterator const_iterator;

		iterator begin() const
		{
			return _rb_tree.begin();
		}
		iterator end() const
		{
			return _rb_tree.end();
		}
        //在后面加上const,使end和begin在普通调用得const调用都是一样得.
        //都返回const_iterator迭代器.

		pair<iterator,bool> insert(const K& val)
		{
			//pair< typaname RBTree<K, K, KeyOfT>::iterator, bool> p  = _rb_tree.insert(val);
			//return pair<iterator, bool>(p.first, p.second);
			return _rb_tree.insert(val);  
			//这里要在迭代器那层实现将 普通迭代器 构造成为 const迭代器.
			//虽然普通迭代器 和 const迭代器 都是 同一个类模板,但是模板参数不相同,所以类型不相同,不能通过强制类型转换就行转换的
			//有些内置类型是可以相互转换的,
			//但是自定义类型大多是不能1相互转换的, 只有父子类之间可以相互转换.

		}

		void print()
		{
			_rb_tree.print();
		}

	private:
		//第一个K是 key比较元素的类型
		//第二个K是 每个节点的元素 ,set就只含有一个 key
		//第三个通过仿函数取消 set 和 map 公用一个 insert的时候一个差异化的问题.
		//insert插入的都是 T(Node的data) set的data是 k 可以直接比较
		//但是 map的 insert插入的是 pair<K,T> 他的比较函数不符合需求,所以需要我们通过仿函数的返回值来去掉差异化.
		RBTree<K, K, KeyOfT > _rb_tree;  
	};

这里有几个问题需要想明白得,set是通过底层都是const迭代器来是是实现不允许修改key,这样就会引发各种各样的问题,比如insert在返回的时候 pari第一个参数的iterator就会变成const_iterator,然而红黑树的insert底层返回的是普通的iteratort所以就会出现问题.所以在迭代器中要写一个特殊的构造函数.实现普通迭代器构造const迭代器,的功能.(看上面的迭代器实现).

三.map的具体实现

	template< class K, class V>
	class map
	{
		struct KeyOfT
		{
			const K& operator()(const pair<K,V>& val)
			{
				return val.first;
			}
		};
		

	public:
		typedef  typename RBTree<K, pair<const K, V>, KeyOfT >::iterator iterator;
		typedef  typename RBTree<K, pair<const K, V>, KeyOfT >::const_iterator const_iterator;

		iterator begin()
		{
			return _rb_tree.begin();
		}
		iterator end()
		{
			return _rb_tree.end();
		}

		const_iterator begin() const
		{
			return _rb_tree.begin();
		}
		const_iterator end() const
		{
			return _rb_tree.end();
		}
        //const类型调用红黑树的const类型begin和end函数
        //普通的迭代器调用普通的类型的begin和end


		pair<iterator,bool> insert(const pair<K,V>& val)
		{
			return _rb_tree.insert(val);
		}

		void print()
		{
			_rb_tree.print();
		}

		V& operator[](const K& key)
		{
			return _rb_tree.insert(make_pair(key, V())).first->second;
		}

	private:
		//第一个K是 key比较元素的类型
		//第二个pair是 每个节点的元素 ,map节点中data存的是 pair
		//第三个通过仿函数取消 set 和 map 公用一个 insert的时候一个差异化的问题.
		//insert插入的都是 T(Node的data) set的data是 k 可以直接比较
		//但是 map的 insert插入的是 pair<K,T> 他的比较函数不符合需求,所以需要我们通过仿函数的返回值来去掉差异化.
		RBTree<K, pair<const K,V>, KeyOfT > _rb_tree;
	};

map的实现没有那么难 ,就是需要我们重载[]的一些东西.就需要insert的返回值的支持.然后使用迭代器即可.没有set那么绕

08-28 01:56