红黑树底层迭代器的实现

Dear 丶 2022-10-16 04:56 116阅读 0赞

![在这里插入图片描述][20210526234232994.png]

### 红黑树实现迭代器 ###

*  目录:
 *   *  一. 封装迭代器
     *  二.红黑树部分改变
     *  三.map的实现
     *  四.set的实现

# 目录: #

>  这篇博客是对于红黑树内部迭代器实现, [点击红黑树的具体代码][Link 1] .

## 一. 封装迭代器 ##

>  对于红黑树迭代器的实现,我们就是要利用二叉树的指向来依次的遍历对应的节点来实现红黑树的迭代器,**所存在的\_header节点就是方便迭代器的实现**

template<class V>
    struct RBTreeIterator{ 		//泛型创建对应的结构
    
    	typedef RBNode<V> Node;
    	typedef RBTreeIterator<V> Self;
    
    	Node* _node;
    
    	RBTreeIterator(Node* node)		//构造函数
    		:_node(node)
    	{ }
    
    	//解引用:*,->
    	V& operator*(){ 		//解引用直接指向对应的值
    
    		return _node->_val;
    	}
    
    	V* operator->(){ 	//指针指向也是一样的
    
    		return &_node->_val;
    	}
    
    	bool operator!=(const Self& it){ 	//!=的判断就是对于对应的node的判断
    
    		return _node != it._node;
    	}
    
    	//中序遍历
    	Self& operator++(){ 		//中序遍历就需要先遍历左子树,再根节点,最后再右子树
    
    		if (_node->_right){ 		//对每一个存在的子树进行遍历的操作
    
    			//右子树的最左节点
    			_node = _node->_right;
    			while (_node->_left){ 
    
    				_node = _node->_left;
    			}
    		}
    		else{ 
    			Node* parent = _node->_parent;
    			while (_node == parent->_right){ 
    
    				_node = parent;
    				parent = parent->_parent;
    			}
    			//避免没有右子树的情况
    			if (_node->_right != parent)
    				_node = parent;
    		}
    		return *this;		//遍历完成后将对应的this指针输出即可
    	}
    
    	Self& operator--(){ 		//减减操作就刚好相反
    							//主要根据图来理解二叉树节点的走向
    		if (_node->_left){ 
    
    			//左子树的最右节点
    			_node = _node->_left;
    			while (_node->_right){ 
    
    				_node = _node->_right;
    			}
    		}
    		else{ 
    
    			Node* parent = _node->_parent;
    			while (_node == parent->_left){ 
    
    				_node = parent;
    				parent = parent->_parent;
    			}
    			//避免没有左子树的情况
    			if (_node->_left != parent)
    				_node = parent;
    		}
    		return *this;
    	}
    };

## 二.红黑树部分改变 ##

template<class K, class V, class KeyOfValue>
    class RBTree{ 
    
    public:
    	typedef RBNode<V> Node;	//定义别名
    
    	typedef RBTreeIterator<V> iterator;	//定义出对应的迭代器
    
    	RBTree(){ }
    
    	iterator begin(){ 		//对于这里begin迭代器的实现就是指向最左边的节点
    
    		return iterator(_header->_left);		//这里使用了在迭代器结构体内构建的->
    	}
    
    	iterator end(){ 		//end迭代器就是指向最后一个节点的后面,也就是_header节点
    
    		return iterator(_header);
    	}
    
    	iterator rbegin(){ 		//反向则是指向最右边的节点,红黑树的不是直接反向的
    
    		return iterator(_header->_right);
    	}
    
    	pair<iterator, bool> insert(const V& val)	//对于原来insert节后的函数名和最终的返回值都需要修改成pair类型
    	{ 
    		//~内部代码删除
    		
    		return make_pair(iterator(node), true);
    	}
    
    	void RotateL(Node* parent){ }	//下面的都不需要改变
    	void RotateR(Node* parent){ }
    	Node* leftMost(){ }
    	Node* rightMost(){ }
    	void inorder(){ }
    	void _inorder(Node* root){ }
    	bool isBalance(){ }
    	bool _isBalance(Node* root, int& bCount, int curBCount){ }
    
    private:
    	Node* _header;
    };

## 三.map的实现 ##

template<class K, class T>
    class Map{ 
    	//通过这里的传值来体现map和set的不同
    	struct MapKeyOfValue{ 
    		const K& operator()(const pair<K, T>& val){ 
    
    			return val.first;
    		}
    	};
    
    public:
    	//在这里创建对应的迭代器
    	typedef typename RBTree<K, pair<K, T>, MapKeyOfValue>::iterator iterator;
    	//修改成pair类型
    	pair<iterator, bool> insert(const pair<K, T>& kv)	//指向改变
    	{ 
    		return _rbt.insert(kv);
    	}
    
    	iterator begin(){ 
    
    		return _rbt.begin();	//直接调用上面定义的begin迭代器
    	}
    
    	iterator end(){ 
    
    		return _rbt.end();		//调用
    	}
    
    	iterator rbegin(){ 
    
    		return _rbt.rbegin();	//调用
    	}
    
    	T& operator[](const K& key){ 
    
    		pair<iterator, bool> ret = _rbt.insert(make_pair(key, T()));	//迭代器封装
    		return ret.first->second;	//在返回对应的值,只返回键值对中后面的value
    	}
    
    private:
    	typedef RBTree<K, pair<K, T>, MapKeyOfValue> rbt;	//引入第三个模板
    	rbt _rbt;
    };

## 四.set的实现 ##

template<class K>	//set也是同样的,只不过内部是<K,K> 不是kv键值对
    class Set{ 
    
    	struct SetKeyOfValue{ 
    		const K& operator()(const K& val){ 
    
    			return val;		//内部实现和map类似
    		}
    	};
    public:
    
    	typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;
    
    	pair<iterator, bool> insert(const K& val){ 
    
    		return _rbt.insert(val);
    	}
    private:
    	typedef RBTree<K, K, SetKeyOfValue> rbt;
    	rbt _rbt;
    };

>  这篇博客是我想把红黑树挖深的总结,主要理解如何搭建红黑树的迭代器就可以了.

[20210526234232994.png]: /images/20221014/f0f688bc47d74165b21b01e013144efe.png
[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/117254371