C++进阶 —— 红黑树

目录

一，红黑树的介绍

红黑树的概念

红黑树的性质

红黑树节点的定义

红黑树的结构

二，红黑树的插入

三，红黑树的验证及删除

红黑树的验证

红黑树的删除

红黑树与AVL树的比较

四，红黑树的应用

红黑树的应用

红黑树模拟实现set/map

一，红黑树的介绍

红黑树的概念

• 红黑树是一种二叉搜索树，但在每个节点上增加一个存储位表示节点颜色，可以是red或black；
• 通过任何一条从根到叶子的路径上各个节点的着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的；

 

红黑树的性质

• 每个节点不是红色，就是黑色；
• 根节点是黑色的；
• 如一个节点是红色的，则它的两个孩子节点是黑色的；
• 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；
• 每个叶节点都是黑色的(此处的叶节点指的是空节点)；

红黑树节点的定义

enum Color { RED, BLACK };

template
struct RBTreeNode
{
	RBTreeNode(const ValueType& data = ValueType(), Color color=RED)
		:_pLeft(nullptr)
		,_pRight(nullptr)
		,_pParent(nullptr)
		,_data(data)
		,_color(color)
	{}

	RBTreeNode* _pLeft;
	RBTreeNode* _pRight;
	RBTreeNode* _pParent;
	ValueType _data;
	Color _color;
};

红黑树的结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头节点；因为根节点必须为黑色，为了与根节点进行区分，将头节点给成黑色，并让头节点的_pParent指向红黑树的根节点，_pLeft指向指向红黑树中最小的节点，_pRight指向红黑树中最大的节点；

 

二，红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，红黑树的插入可分为两步：

1，按照二叉搜索树的规则插入新节点；

template
class RBTree
{
	bool Insert(const ValueType& data)
	{
		pNode& pRoot = GetRoot();
		if (pRoot == nullptr)
		{
			pRoot = new Node(data, BLACK);
			pRoot->_pParent = _pHead;
			_pHead->_pParent = pRoot;
		}
		else
		{
			pRoot->_color = BLACK;
			_pHead->_pLeft = LeftMost();
			_pHead->_pRight = RightMost();
			return true;
		}
	}
private:
	pNode& GetRoot()
	{
		return _pHead->_pParent;
	}
	pNode LeftMost();
	pNode RightMost();
private:
	pNode _pHead;
};

2，检测新节点插入后，红黑树的性质是否遭到破坏；

• 因为新节点默认是红色的，因此如果其双亲节点的颜色是黑色的，没有违反红黑树任何性质，则不需要调整；
• 但当前新插入节点的双亲节点颜色为红色时，就违反了性质，此时就需要调整，需分以下情况来分析(约定当前节点为cur，父节点为p，祖父节点为g，叔叔节点为u)；

情况一：cur为红，p为红，g为黑，u为红

• 如g是根节点，调整完后，需将g改为黑色；
• 如g是子树，g一定有双亲，如改双亲也是红色，需继续向上调整；
  • 解决方法，将p/u改为黑色，g改为红，然后把g当成cur，继续向上调整；

情况二：cur为红，p为红，g为黑，u为黑或不存在

• 如u不存在，则cur一定是新插入节点；因为如cur不是新插入节点则cur与p一定有一个节点的颜色是黑色，那么就不满足性质为每条路径黑色节点个数是相同的；
• 如u存在，则其一定是黑色，那么cur节点原来的颜色一定是黑色的，现在是红色的原因是cur子树在调整的过程中将cur由黑色改为红色了；

•  p为g左孩子，cur为p的左孩子，则进行右单旋；
• p为g右孩子，cur为p的右孩子，则进行左单旋；
• p变黑，g变红；

情况三：cur为红，p为红，g为黑，u为黑或不存在

• p为g的左孩子，cur为p的右孩子，则针对p左单旋；
• p为g的右孩子，cur为p的左孩子，则针对p右单旋；
• 转化为情况2；

三，红黑树的验证及删除

红黑树的验证

• 检测其是否满足二叉搜索树(中序遍历是否为有序序列)；
• 检测其是否满足红黑树的性质；

bool IsValidRBTree()
{
	pNode pRoot = GetRoot();
	if (pRoot == nullptr)
		return true;
	if (pRoot->_color == BLACK)
	{
		cout << "违反红黑树根节点必须为黑色" << endl;
		return false;
	}
	size_t blackCount = 0;
	pNode pCur = pRoot;
	while (pCur)
	{
		if (pCur->_color == BLACK)
			blackCount++;
		pCur = pCur->_pLeft;
	}

	size_t k = 0;
	return _IsValidRBTree(pRoot, k, blackCount);
}

bool _IsValidRBTree(pNode pRoot, size_t k, const size_t blackCount)
{
	if (pRoot == nullptr)
	{
		if (blackCount != k)
		{
			cout << "违反性质每条路径中黑色节点个数必须相同" << endl;
			return false;
		}
		return true;
	}

	if (pRoot_color == BLACK)
		k++;

	pNode pParent = pRoot->_pParent;
	if (pParent && pParent->_color == RED && pRoot->_color == RED)
	{
		cout << "违反性质没有连在一起的红色节点" << endl;
		return false;
	}

	return _IsValidRBTree(pRoot->_pLeft, k, const blackCount) &&
		   _IsValidRBTree(pRoot->_pRight, k, const blackCount)
}

红黑树的删除

可参考《算法导论》或《STL源码剖析》；

或参考博客，红黑树 - _Never_ - 博客园；

红黑树与AVL树的比较

• 红黑树和AVL树都是高效的平衡二叉树。增删查改的时间复杂度都为O(logN)；
• 红黑树不追求绝对平衡，只需保证最长路径不超过最短路径的2倍，相对而言减低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优；
• 红黑树实现比较减低，实际运用中红黑树更多；

四，红黑树的应用

红黑树的应用

• C++ STL库
  • set/multiset、map/multimap
• Java库
• Linux内核
• 其他一些库

红黑树模拟实现set/map

红黑树的迭代器（迭代器的好处是方便迭代）

• begin()/end()，STL规定begin()/end()是一段前闭后开的区间，而对于红黑树的遍历得到是有序序列，因此begin()可放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(即最右侧节点)的下一个位置；下一个位置不可给成nullptr，因为对迭代器--操作时需找到最后一个元素，所以最好方式是将end()放在头节点的位置；

•  operator++()或operator--()

void Increasement()
{
	if (_pNode->_pRight)
	{
		_pNode = _pNode->_pRight;
		while (_pNode->_pLeft)
		{
			_pNode = _pNode->_pLeft;
		}
	}
	else
	{
		pNode pParent = _pNode->_pParent;
		while (pParent->_pRight == _pNode)
		{
			_pNode = pParent;
			pParent = _pNode->_pParent;
		}

		fi(_pNode->_pRight != pParent)
			_pNode = pParent;
	}
}

void Decreasement()
{
	//_pNode在head的位置
	if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED)
		_pNode = _pNode->_pRight;

	else if(_pNode->_pLeft)
	{
		//_pNode左子树存在
		_pNode = _pNode->_pLeft;
		while (_pNode->_pRight)
		{
			_pNode = _pNode->_pRight;
		}
	}
	else
	{
		//_pNode左子树不存在
		pNode pParent = _pNode->_pParent;
		while (_pNode == pParent->_pLeft)
		{
			_pNode = pParent;
			pParent = _pNode->_pParent;
		}
		_pNode = pParent;
	}
}

改造红黑树

//因关联式容器中存储的是键值对
//K为key的类型
//ValueType, 如是map，则为pair，如是set，则为K
//KeyofValue，通过value来获得key的一个仿函数类
template 
class RBTree
{
	typedef RBTreeNode Node;
	typedef Node* pNode;
public:
	typedef RBTreeIterator Iterator;
public:
	RBTree();
	~RBTree();

	Iterator begin() { return Iterator(_pHead->_pLeft); }
	Iterator end() { return Iterator(_pHead); }

	pair Insert(const ValueType& data)
	{
		//插入节点并调整
		return make_pair(Iterator(pNewNode), true);
	}

	void clear();
	Iterator find(const k& key);

	size_t size() const;
	size_t empty() const;

private:
	pNode _pHead;
	size_t _size;
};

set的模拟实现

• set的底层结构就是红黑树，因此在set中直接封装了一颗红黑树；

template
class set
{
	typedef K ValueType;
	struct KeyOfValue
	{
		const K& operator()(const ValueType& key)
		{
			return key;
		}
	};

	typedef RBTree RBTree;
public:
	typedef typename RBTree::Iterator iterator;
public:
	set() {};

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

	size_t size() const { return _t.size() };
	bool empty() const { return _t.empty() };
	void clear() { return _t.clear() };

	pair insert(const ValueType& data)
	{
		return _t.Insert(data);
	}

	iterator find(const K& key);
private:
	RBTree _t;
}

map的模拟实现

• map的底层结构就是红黑树，因此在map中直接封装了一颗红黑树；

template
class map
{
	typedef pair(K, V) ValueType;
	struct KeyOfValue
	{
		const K& operator()(const ValueType& v)
		{
			return v.first;
		}
	};

	typedef RBTree RBTree;
public:
	typedef typename RBTree::Iterator iterator;
public:
	map() {};

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

	size_t size() const { return _t.size() };
	bool empty() const { return _t.empty() };
	void clear() { return _t.clear() };

	V& operator[](const K& key)
	{
		return (*(_t.Insert(ValueType(key, V())))).first).second;
	}
	const V& operator[](const K& key)const;

	pair insert(const ValueType& data)
	{
		return _t.Insert(data);
	}

	iterator find(const K& key)
	{
		return _t.find(key);
	}
private:
	RBTree _t;
}