【C++/STL】手撕红黑树

2023-11-12

文章目录

1.红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

1.1红黑树的性质和规则

1.每个结点不是红色就是黑色

2.规定根节点是黑色

3.如果一共节点是红色，则它的两个孩子节点是黑色的

4.对于每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点

5.每个叶子节点都是黑色(这里的叶子结点指的是nullptr结点，在统计黑色结点数量时可以忽略)

为什么满足上面的性质就可以让最长路径不超过最短路径的2倍？

1.)上面的性质三说明了红黑树一定不存在连续的红色结点。

2.)每一条简单路径上的黑色结点数相等。

因此最短的路径一定由全是黑色结点组成(或者这条路径中红色结点最少)，最长的路径一定是一红一黑的组合。(或者一红一黑的组合最多) 而两条路径的黑色结点数相等，那么最长路径最多只能为全黑路径的2倍。

在这里插入图片描述

2.红黑树的模拟实现

2.1节点的定义

enum Colour
{
	BLACK,
	RED
};
//三叉链
template <class K,class V>
struct  RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)
	{}
};

红黑树的框架

template <class K,class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
public:
 	/*
 		对外的接口
 		insert()..
 		inOrder()...
 		.....
    */
private:
    /*
    	内部函数
    */
private:
    Node* _root
}

2.2节点的插入

步骤一：红黑树也是一种二叉搜索树，因此先按照二叉搜索树的规则找到插入数据的位置。

bool insert(const pair<K, V>& kv)
{
	//按照普通的搜索二叉树的规则插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
         }
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	cur->_parent = parent;
	if (kv.first > parent->_kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
    //新插入的结点默认为红色？
    cur->_col=RED;
    /*
    ................................
    ................................
    改变颜色，旋转等操作。
    */
}

为什么新插入的结点设置为红色？

如果我们设置为黑色，那么路径中的黑色结点数就发送了改变，由于规则4，其影响了一整棵红黑树的结构。如果我们设置为红色，如果它的parent结点是黑色，那么对红黑树的规则没有影响，当parent结点为红色时，也只是影响力父子两个结点，违反了规则3。

对下面的图，我们有下面的约定： 约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点；对于红黑树来说，调整其结构，主要看u节点的情况

1.）情况一：u存在且为红色

调整方式：将p和u变为黑色，g变为红色。

还需要注意曾祖父s节点的情况。

即将cur赋值为g,p赋值为g。进行下一步循环

cur=grandfaher;
parent=cur->_parent;

如果g是根节点，调试完成后，退出循环，并要将根的颜色改为黑色。

_root->_col=BLACK;

2.)情况二：u不存在/u存在且为黑(并且g、p、cur为一条直线)

对于u有两种情况情况：

1.u不存在，那么cur一定是新插入的节点。因为如果cur不是新插入的节点，那么原来cur和p一定有一个是黑色节点，否则违反规则四：每条路径的黑色节点数相等。 2.u存在。则u一定是黑色节点。cur原来一定是黑色结点，现在看到的红色是因为调整后有黑色变为的红色。

2：

情况2.)分为两种情况：可以简记为左左右和右右左

左左右：p为g的左孩子，cur为p的左孩子，进行右单旋；

右右左：p为g的右孩子，cur为p的右孩子，进行左单旋

(1.)p为g的左孩子，cur为p的左孩子，则g进行右单旋转

(2.)p为g的右孩子，cur为p的右孩子，则g进行左单旋转

旋转结束后变色：p、g变色–p变黑，g变红

3.)情况三：u不存在/u存在且为黑(并且g、p、cur为一条折线)

和情况2.)类似，只不过g,p,cur的关系变为了一条折线。

同样分为两种情况：可以简记为左右左右双旋；右左右左双旋转

p为g的左孩子，cur为p的右孩子，先对p进行左单旋，再对g进行右单旋；

p为g的右孩子，cur为左的右孩子，先对p进行右单旋，再对g进行左单旋；

(1.)p为g的左孩子，cur为p的右孩子，先对p进行左单旋，再对g进行右单旋；

(2.)p为g的右孩子，cur为左的右孩子，先对p进行右单旋，再对g进行左单旋

2.3旋转代码实现

//存在连续的红色节点,就需要进行调整
while (parent && parent->_col == RED)
{
	Node* grandfather = parent->_parent;
    //如果祖父结点不存在，那么就直接跳过
	if (!grandfather)
	{
		break;
	}
	Node* uncle = nullptr;
	if (parent == grandfather->_left)
	{
		uncle = grandfather->_right;
        //情况一：u存在且为红
		if (uncle && uncle->_col == RED)
		{
			parent->_col = BLACK;
			uncle->_col = BLACK;
			grandfather->_col = RED;
			cur = grandfather;
			parent = cur->_parent;
		}
		else
		{
            //情况二：u不存在或者u存在且为黑
            //左左右的情况
			if (cur == parent->_left)
			{
				//右单旋
				RouteR(grandfather);
				grandfather->_col = RED;
				parent->_col = BLACK;
				break;
			}
            //情况三：u不存在或者存在且为黑
            //左右左右的情况
			else
			{
				RouteL(parent);
				RouteR(grandfather);
				grandfather->_col = RED;
				cur->_col = BLACK;
				break;
			}
		}
	}
	else
	{
		uncle = grandfather->_left;
        //情况一：u存在且为红
		if (uncle && uncle->_col == RED)
		{
			parent->_col = BLACK;
			uncle->_col = BLACK;
			grandfather->_col = RED;
			cur = grandfather;
			parent = cur->_parent;
		}
		else
		{
            //情况二：u不存在或者u存在且为黑
            //右右左的情况
			if (cur == parent->_right)
			{
				//左单旋
				RouteL(grandfather);
				grandfather->_col = RED;
				parent->_col = BLACK;
				break;
			}
            //情况三：u不存在或者存在且为黑
            //右左右左的情况
			else
			{
				RouteR(parent);
				RouteL(grandfather);
				grandfather->_col = RED;
				cur->_col = BLACK;
				break;
			}
		}
	}
	_root->_col = BLACK;
}

2.3.1右旋和左旋

//左单旋
void RouteL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* pparent = parent->_parent;
	parent->_right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	parent->_parent = subR;
	//如果root为根
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		subR->_parent = pparent;
		if (parent == pparent->_left)
		{
			pparent->_left = subR;
		}
		else
		{
			pparent->_right = subR;
		}
	}
}

//右单旋
void RouteR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	Node* pparent = parent->_parent;
	parent->_parent = subL;
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (pparent->_left == parent)
		{
			pparent->_left = subL;
		}
		else
		{
			pparent->_right = subL;
		}
		subL->_parent = pparent;
	}
}

2.4中序遍历

中序遍历和一般的二叉搜索树方式一样。

void _inorder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_inorder(root->_left);
	cout << root->_kv.first << " ";
	_inorder(root->_right);
}
	//中序遍历
void inorder()
{
	_inorder(_root);
}

2.5验证是否为红黑树

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质，验证是否满足红黑树的5条规则。

2.5.1求最长路径和最短路径

int _maxHeight(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	int left = _maxHeight(root->_left);
	int right = _maxHeight(root->_right);
	return max(left, right) + 1;
}
int _minHeight(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	int left = _minHeight(root->_left);
	int right = _minHeight(root->_right);
	return min(left, right) + 1;
}

void Hight()
{
	cout << "最长路径：" << _maxHeight(_root) << endl;
	cout << "最短路径：" << _minHeight(_root) << endl;
}

2.5.2 isRBTree()函数

bool isRBTree()
{
	//记录最左边一条路径的黑色节点个数
	int blacksize = 0;
	Node* cur = _root;
	if (cur == nullptr)
	{
		return true;
	}
	if (_root->_col == RED)
	{
		cout << "违反规则二：红黑树的根必须是黑色" << endl;
		return false;
	}
	int maxlength = _maxHeight(_root);
	int minlength = _minHeight(_root);
	Hight();
	if (maxlength > 2 * minlength)
	{
		return false;
	}
	while (cur)
	{
		if (cur->_col == BLACK)
		{
		blacksize++;
		}
		cur = cur->_left;
	}
	int k = 0;
	return _isRBTree(_root,k,blacksize);
}

_isRBTree()

bool _isRBTree(Node* root,int k,int blacksize)
{
	//比较该路径和最左边路径的黑色节点数是否相等
	if (root == nullptr)
	{
		if (k != blacksize)
		{
			cout << "违反规则四：每条路径的黑色结点数相等" << endl;
			return false;
		}
			return true;
	}
	//判断是否右联系的红色结点
	if (root->_col == RED && root->_parent && root->_parent->_col == RED)
	{
		cout << "违反规则三：没有连续的红色结点" << endl;
		return false;
	}
	if (root->_col == BLACK)
	{
		k++;
	}
	return _isRBTree(root->_left, k, blacksize) && _isRBTree(root->_right, k, blacksize);
}

2.6实现结果

int main()
{
	srand(time(0));
	RBTree<int, int>rbt;
	int N = 100;
	int n = 0;
	for (int i = 0;i < N;i++)
	{
		n = rand();
		rbt.insert(make_pair(i, n));
	}
	bool ret=rbt.isRBTree();
	cout << ret << endl;
	//rbt.inorder();
	return 0;
}

在这里插入图片描述

3.红黑树迭代器的封装

红黑树的迭代器，本质上是对红黑树结点指针的封装。
实现代码：

struct  RBTreeNode
	{
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		T _data;
		Colour _col;
		RBTreeNode(const T& data)
			:_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)
		{}
	};

	//迭代器,实际上是对红黑树结点类型的指针进行了一层封装
template <class T,class Ref,class Ptr>
struct _RBTreeIterator
{
public:
	typedef RBTreeNode<T> Node;
	typedef _RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node;
	//构造函数
	_RBTreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);
			return tmp;
	}
	Self& operator++()
	{

		if (_node->_right == nullptr)
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		//在右子树的最左结点
		else
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);
		return tmp;
	}
	Self& operator--()
	{
		if (_node->_left == nullptr)
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		//左子树的最右子树
		else
		{
			Node* subLR = _node->_left;
			while (subLR->_right)
			{
				subLR = subLR->_right;
			}
			_node = subLR;
		}
		return *this;
	}
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
	bool operator!= (const Self& s) const
	{
		return _node != s._node;
	}
};

在这里插入图片描述

4.红黑树的补充接口和insert()的改造

在STL库中，insert()的返回值是返回的一个pair<iteraror,bool>的类型，在自己模拟实现的时候，insert()也返回该类型。
同时，为了配合迭代器的使用，还需要加上begin(),end()等API


template<class K,class T,class compare>
class RBTree
	{
	public:
		typedef _RBTreeIterator<T, T&, T*> iterator;
		typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
		Compare _com;
		typedef RBTreeNode<T> Node;
		iterator begin()
		{
			Node* cur = _root;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			return iterator(cur);
		}
		iterator end()
		{
			return iterator(nullptr);
		}
		const_iterator begin()const
		{
			Node* cur = _root;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			return const_iterator(cur);
		}
		const_iterator end()const
		{
			return const_iterator(nullptr);
		}

		iterator find(const K&key)
		{
			Node* cur = _root;
			Compare _com;
			while (cur)
			{
				if (_com(_root->_data) == key)
				{
					return iterator(cur);
				}
				else if (_com(_root->_data) < key)
				{
					cur = cur->_right;
				}
				else
				{
					cur = cur->_left;
				}
			}
			return iterator(nullptr);
		}
		//插入
		pair<iterator,bool> insert(const T& data)
		{
			//按照普通的搜索二叉树的规则插入
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_col = BLACK;
				return make_pair(iterator(_root),true);
			}
			Node* parent = nullptr;
			Node* cur = _root;
			//比较K
			while (cur)
			{
				if (_com(cur->_data) > _com(data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (_com(cur->_data) < _com(data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return  make_pair(iterator(cur),false);
				}
			}
			cur = new Node(data);
			Node* newnode = cur;
			cur->_parent = parent;
			if (_com(data) > _com(parent->_data))
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			//cur是插入的节点
			cur->_col = RED;
			//存在连续的红色节点,就需要进行调整
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (!grandfather)
				{
					break;
				}
				Node* uncle = nullptr;
				if (parent == grandfather->_left)
				{
					uncle = grandfather->_right;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_left)
						{
							//右单旋
							RouteR(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;
							break;
						}
						else
						{
							RouteL(parent);
							RouteR(grandfather);
							grandfather->_col = RED;
							cur->_col = BLACK;
							break;
						}
					}
				}
				else
				{
					uncle = grandfather->_left;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_right)
						{
							//左单旋
							RouteL(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;
							break;
						}
						else
						{
							RouteR(parent);
							RouteL(grandfather);
							grandfather->_col = RED;
							cur->_col = BLACK;
							break;
						}
					}
				}
				_root->_col = BLACK;
			}
			return make_pair(iterator(newnode), true);
		}
		/*
		上面的其余接口实现
		.............................
		.............................
		.............................
		*/
};

在这里插入图片描述

5.封装Map

Map的底层是一棵红黑树，只是在传递红黑树存储类型的时候需要传递pair<K,V>类型。

template <class K,class V>
class Map
{
public:
	struct keyof
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
	typedef typename RBTree<K, pair<K, V>, keyof>::iterator iterator;
	typedef typename RBTree<K, pair<K, V>, keyof>::const_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();
	}
	iterator find()
	{
		return _t.find();
	}
	pair<iterator, bool>insert(const pair<K, V>& kv)
	{
		return _t.insert(kv);
	}
	V& operator[](const K& key)
	{
		auto it = _t.insert();
		return it.first->second;
	}
private:
	RBTree<K, pair<K, V>, keyof> _t;
};

6.封装Set

Set类型的底层也是一棵红黑树，只是存储的类型就是K

template<class K>
class Set
{
	//一个用于提取K的仿函数
public:
	struct  Keyof
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	typedef typename RBTree<K, K, Keyof>::const_iterator iterator;
	typedef typename RBTree<K, K, Keyof>::const_iterator const_iteraotr;
	iterator begin()const
	{
		return _t.begin();
	}
	iterator end() const
	{
		return _t.end();
	}
	pair<iterator, bool>insert(const K& key)
	{
		auto it=_t.insert(key);
		return pair<iterator, bool>(iterator(it.first._node), it.second);
	}
	iterator find(const K& key)
	{
		return _t.find(key);
	}
	//set的底层是一棵红黑树
private:
	RBTree<K, K, Keyof> _t;
};

7.实现结果调试

void testset()
{
	cout << "testset:" << endl;
	Set<int> st;
	st.insert(1);
	st.insert(2);
	Set<int>::iterator it = st.begin();
	while (it != st.end())
	{
		cout << *it << endl;
		it++;
	}
	cout << endl;
	st.insert(3);
	for (auto i : st)
	{
		cout << i << " " << endl;
	}
}
void testmap()
{
	cout << "testmap:" << endl;
	Map<int, int>mp;
	mp.insert(make_pair(1, 1));
	mp.insert(make_pair(4, 4));
	mp.insert(make_pair(7, 7));
	mp.insert(make_pair(8, 8));
	mp.insert(make_pair(2, 2));
	mp.insert(make_pair(3, 3));
	Map<int, int>::iterator it = mp.begin();
	while (it != mp.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;
	for (auto i : mp)
	{
		cout << i.first << ":" << i.second << endl;
	}
	cout << endl;
}

在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)