红黑树万字详解

来源：叨叨游戏网

前言

红黑树在AVL树的基础上做了进一步改进，主要体现在不需要频繁调整树的结构，
它是怎么做到的呢？让我们来看看吧~

1. 红黑树概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接衡的。

2. 红黑树性质

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
因为节点只有两种颜色，红色和黑色，一条路径最长的情况下是红色和黑色交替出现（规则3），而最短的情况是全部为黑色，由于规则4，两条路径具有相同的黑色节点数，所以此时两条路径节点数比值为2

3. 红黑树节点定义

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
	RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
	: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
	, _data(data), _color(color)
	{}
	RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
	RBTreeNode<ValueType>* _pRight; // 节点的右孩子
	RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
	ValueType _data; // 节点的值域
	Color _color; // 节点的颜色
};

这里可以发现，新节点默认是红色的，为什么呢？
因为我们在插入一个新节点时，会与红黑树规则发生冲突：

如果插入的节点为黑色，则与规则4冲突，因为本来树是平衡的，新增一个黑色节点意味着这棵子树的黑色节点增加了，如果需要再次保证平衡，需要付出很大的代价
如果插入节点为红色，则与规则3冲突，此时影响是局部的，只需要观察附近的情况即可

4. 红黑树的插入操作

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

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

bool Insert(const std::pair<K,V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv,BLACK);
		return true;
	}
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			if (cur->_right == nullptr)
			{
				Node* new_node = new Node(kv);
				cur->_right = new_node;
				new_node->_parent = cur;
				cur = new_node;
				break;
			}
			else cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			if (cur->_left == nullptr)
			{
				Node* new_node = new Node(kv);
				cur->_left = new_node;
				new_node->_parent = cur;
				cur = new_node;
				break;
			}
			else cur = cur->_left;
		}
		else return false;
	}
	//调整树的平衡
	
	//此时cur指向新增节点
	Node* parent = cur->_parent;
	//如果新增节点的父节点为空或者是黑色，则不违反规则3，树达到平衡
	while (parent && parent->_col == RED) 
	{
	//...
	}
	return true;

检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

旋转操作请复习的旋转

bool Insert(const std::pair<K,V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv,BLACK);
		return true;
	}
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			if (cur->_right == nullptr)
			{
				Node* new_node = new Node(kv);
				cur->_right = new_node;
				new_node->_parent = cur;
				cur = new_node;
				break;
			}
			else cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			if (cur->_left == nullptr)
			{
				Node* new_node = new Node(kv);
				cur->_left = new_node;
				new_node->_parent = cur;
				cur = new_node;
				break;
			}
			else cur = cur->_left;
		}
		else return false;
	}
	Node* parent = cur->_parent;
	while (parent && parent->_col == RED)
	{
		assert(parent->_parent != nullptr);
		Node* grand = parent->_parent; 
		//如果parent为红，说明不是根节点，则一定有父节点
		Node* uncle = grand->_left == parent ? grand->_right : grand->_left; //找到uncle节点
		if (uncle == nullptr || uncle->_col == BLACK) 
		//uncle为空或者为黑则是情况二
		{
			if (parent == grand->_left)
			{
				if (cur == parent->_left)
				{
					_RotateR(grand);
				}
				else
				{
					_RotateLR(grand);
				}
			}
			else
			{
				if (cur == parent->_left)
				{
					_RotateRL(grand);
				}
				else
				{
					_RotateL(grand);
				}
			}
			break;
		}
		else//uncle为红节点
		{
			parent->_col = BLACK;
			uncle->_col = BLACK;
			if (grand != _root)
			{
				grand->_col = RED;
				cur = grand;
				parent = cur->_parent;
			}
			else break;
		}
	}
	return true;
}
void _RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* pparent = parent->_parent;

	subR->_parent = pparent;
	subR->_left = parent;

	if (pparent == nullptr)
	{
		_root = subR;
	}
	else
	{
		if (pparent->_left == parent)
			pparent->_left = subR;
		else
			pparent->_right = subR;
	}
	parent->_parent = subR;
	parent->_right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_col = BLACK;
	parent->_col = RED;
}
void _RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subRL = subL->_right;
	Node* pparent = parent->_parent;

	subL->_parent = pparent;
	subL->_right = parent;

	if (pparent == nullptr)
	{
		_root = subL;
	}
	else
	{
		if (pparent->_left == parent)
			pparent->_left = subL;
		else
			pparent->_right = subL;
	}
	parent->_parent = subL;
	parent->_left = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subL->_col = BLACK;
	parent->_col = RED;
}
void _RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	_RotateR(subR);
	_RotateL(parent);
	parent->_col = RED;
	subR->_col = RED;
	subRL->_col = BLACK;
}
void _RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	_RotateL(subL);
	_RotateR(parent);
	parent->_col = RED;
	subL->_col = RED;
	subLR->_col = BLACK;
}

5. 红黑树的验证

红黑树验证分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)

void InorderPrint()
{
	_Inorder(_root);
	std::cout << std::endl;
}
void _Inorder(Node* root)
{
	if (root == nullptr) return;
	_Inorder(root->_left);
	std::cout << root->_kv.first  << " ";
	_Inorder(root->_right);
}

检测其是否满足红黑树的性质

bool IsLegal()
{
	//判断规则2
	if (_root && _root->_col == RED) return false; 
	return _IsLegal(_root);
}
bool _IsLegal(Node* root)
{
	if (root == nullptr) return true;
	//判断规则3
	if (root->_parent && root->_col == RED)
	{
		return root->_parent->_col != RED;
	}
	//判断规则4
	int lbcount = get_bcount(root->_left);
	int rbcount = get_bcount(root->_right);
	return lbcount == rbcount;
}
//获取黑节点个数
int get_bcount(Node* root)
{
	if (root == nullptr) return 0;
	if (root->_col == BLACK)
	{
		return 1 + get_bcount(root->_left);
	}
	return get_bcount(root->_left);
}

6. 红黑树与AVL树比较

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

7. 红黑树的应用

C++ STL库 – map/set、mutil_map/mutil_set
Java 库
linux内核
其他一些库

8. 红黑树模拟实现STL中的map与set

8.1 红黑树节点

	enum Color {
		BLACK, 
		RED
	};
	template<class T>
	struct RBTreeNode {
		RBTreeNode<T>* _parent;
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		T _data;
		Color _col;
		RBTreeNode(const T& data = T(), Color col = RED, RBTreeNode<T>* left = nullptr,
			RBTreeNode<T>* right = nullptr, RBTreeNode<T>* parent = nullptr)
			:_data(data),
			_col(col),
			_left(left),
			_right(right),
			_parent(parent)
		{}
	};

只需要一个模板参数，我会为您讲解为什么要这样设计

8.2 红黑树的框架

template<class K,class T,class KOfT,class Compare>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T*, T&> iterator;
	typedef __RBTreeIterator<T, const T*, const T&> const_iterator;
	
	iterator begin();
	iterator end();
	const_iterator cbegin() const;
	const_iterator cend() const;
public:
	RBTree() = default;
	
	std::pair<iterator,bool> Insert(const T& data);
	bool IsLegal();
	void InorderPrint();
	~RBTree();
private:
	void _Destructor(Node* root);
	bool _IsLegal(Node* root);
	int get_bcount(Node* root);
	void _Inorder(Node* root);

	void _RotateL(Node* parent);
	void _RotateR(Node* parent);
	void _RotateRL(Node* parent);
	void _RotateLR(Node* parent);
	
private:
	Node* _root = nullptr;
};

由于我们需要用红黑树来封装出map和set两种容器，它们一个只存储key值，一个存储KV，所存的东西不同

红黑树第二个模板参数用来指明底层所要存储数据的类型，
第一个参数则表示key的类型，虽然insert()用不上，但是比如find()、erase()就很需要这个参数
第三个模板参数是仿函数类型，用于从T类型的对象中取出key值
第四个模板参数也是仿函数类型，用于比较key值的大小

这样设计体现了代码的复用，一份红黑树代码，就可以同时封装出map和set，非常之秒~

8.3 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题:

begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，
因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置
STL的处理办法是多构造一个头节点，其左指针指向中序遍历的第一个节点，右指针指向中序遍历的最后一个节点，父指针指向根节点，根节点的父指针指向头节点
operator++()与operator–()
对于正向迭代器来说，++操作是找中序遍历的下一个元素，–操作是找中序遍历是上一个元素

除了STL的方法：构造一个额外的头节点来实现迭代器
我们也可以不额外增加头节点来实现，接下来我将演示不增加头节点的实现方法

template <class T,class Ptr,class Ref>
class __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ptr, Ref> Self;
public:
	__RBTreeIterator(Node* ptr)
		:_ptr(ptr)
	{}
	Self& operator++()
	{
		//如果右子树为空，说明以_ptr为根的子树已经遍历完
		//要找到第一个为_ptr为parent的左子树的节点
		if (_ptr->_right == nullptr) 
		{
			Node* parent = _ptr->_parent;
			while (parent && parent->_right == _ptr)
			{
				_ptr = parent;
				parent = _ptr->_parent;
			}
			_ptr = parent;
		}
		//如果右子树不为空，中序遍历的下一个节点为右子树的最左节点
		else
		{
			_ptr = _ptr->_right;
			while (_ptr->_left)
			{
				_ptr = _ptr->_left;
			}
		}
		return *this;
	}
	Self& operator--()
	{
		if (_ptr->_left == nullptr)
		{
			Node* parent = _ptr->_parent;
			while (parent && parent->_left == _ptr)
			{
				_ptr = parent;
				parent = _ptr->_parent;
			}
			_ptr = parent;
		}
		else
		{
			_ptr = _ptr->_left;
			while (_ptr->_right)
			{
				_ptr = _ptr->_right;
			}
		}
		return *this;
	}
	Ref operator*() const
	{
		return _ptr->_data;
	}
	Ptr operator->() const 
	{
		return &(_ptr->_data);
	}
	bool operator==(const Self& other) const 
	{
		return _ptr == other._ptr;
	}
	bool operator!=(const Self& other) const
	{
		return _ptr != other._ptr;
	}
private:
	Node* _ptr;
};

最重要的是迭代器的++和–操作

假设我们现在遍历到8这个节点，迭代器++应该找到11这个节点，即右子树中序遍历的第一个节点
假设我们现在遍历到11这个节点，那么下一个节点应该是13，即第一个所指节点为父节点的左子树的父节点
当我们遍历到27时，我们会不断向上遍历由于没有所指节点为父节点的左子树的父节点了，所以要额外判断一下父节点不为空
begin()为中序遍历的第一个节点
end()为nullptr

8.4 封装set

template<class K,class Compare = std::less<K>>
class set {	
	//从T中取出Key值，仿函数
	struct SetKeyOfT {
		const K& operator()(const K& data)
		{
			return data;
		}
	};
public:
	using typename RBTree<K, K, SetKeyOfT, Compare>::iterator = iterator;
	iterator begin()
	{
		return _tree.begin;
	}
	iterator end()
	{
		return _tree.end();
	}
public:
	std::pair<iterator, bool> insert(const K& key)
	{
		return _tree.Insert(key);
	}
private:
	RBTree<K, K,SetKeyOfT,Compare> _tree;
};

8.5 封装map

template<class K,class V,class Compare = std::less<K>>
class map {
	//从KV中取出Key值，仿函数
	struct MapKeyOfT {
		const K& operator()(const std::pair<K,V>& kv)
		{
			return kv.first;
		}
	};
public:
	typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT, Compare>::iterator iterator;

	iterator begin()
	{
		return _tree.begin();
	}
	iterator end()
	{
		return _tree.end();
	}
public:
	std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
	{
		return _tree.Insert(kv);
	}
	V& operator[](const K& key)
	{
		iterator it = insert(std::make_pair(key, V())).first;
		return it->second;
	}
private:
	RBTree<K, std::pair<K, V>, MapKeyOfT, Compare> _tree;
};

可以看出map和set底层就是红黑树，利用了红黑数的接口，完成了代码的复用，设计非常的优美~

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文