Forcible Bug Maker

Forcible Bug Maker

关注
发信
关注(28)粉丝(399)

【数据结构进阶】手撕红黑树

【数据结构进阶】手撕红黑树-LMLPHP

🔥个人主页： Forcible Bug Maker
🔥专栏： C++ || 数据结构

🌈前言

刚刚接触编程的时候就听说有的大厂HR会让手撕红黑树。心中一直对这个数据结构保持着敬畏和向往，今天在将其撕出来后，用本篇博客加以记录，望周知。

🔥红黑树的概念

红黑树，也是一种二叉搜索树，但再每个结点上增加一个存储位置表示结点的颜色，可以是RED（红）或BLACK（黑）。通过对任何一条根到叶子的路径上各个结点的着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
【数据结构进阶】手撕红黑树-LMLPHP
一颗红黑树，是具有如下性质的二叉搜索树：

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果一个结点是红色，则它的两个孩子结点是黑色（即不会有连续的红结点）
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的（此处的叶子结点指的是空结点NIL）

🔥手撕红黑树

红黑树结点的定义

红黑树的结点包含四个成员变量，模板类型T：可以存储K或者pair<K,V>类型，便于后期封装；三个指针：分别为指向左孩子结点的指针，指向右孩子结点的指针，指向父结点的指针；最后变量_col：枚举类型，可以存RED和BLACK。

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>(const T& t)
		: _data(t)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _col;
};

红黑树主体需要实现的成员函数

// T: 可能是键值对<key,value>
//    可能是一个key
// 不论节点中存储的是<key, value> || key, 都是按照key来进行比较的
// KeyOfValue: 提取data中的Key
template<class K, class T, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;
public:
	RBTree() = default;

	RBTree(const RBTree<K, T, KeyOfValue>& t);

	// 插入值为data的节点
	// 返回值含义：iterator代表新插入节点   bool：代表释放插入成功
	std::pair<iterator, bool> Insert(const T& data);
	
	// Begin和End迭代器
	iterator Begin();
	iterator End();

	// 红黑树是否为空，是返回true，否则返回false
	bool Empty()const;
	
	// 返回红黑树中有效节点的个数
	size_t Size()const;
	
	// 将红黑树中的有效节点删除
	void Clear();

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	
	// 在红黑树中查找data，存在赶回该节点对应的迭代器，否则返回End()
	iterator Find(const T& data);

	~RBTree();
private:
	Node* _root;
};

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

  1. 首先是按照二叉搜索树的方式插入结点
  2. 检测插入结点后，红黑树的性质是否遭到破坏
    因为新结点的默认颜色是红色，因此：如果父结点的颜色是黑色，就没有违反性质，不需调整；担当插入结点的父节点也是红色时，就违反了性质3（不能有连在一起的红结点），此时需要对红黑树分情况讨论调整：
  • 情况一：cur为红，p为红，g为黑，u存在且为红

【数据结构进阶】手撕红黑树-LMLPHP
解决方式：将p，u变成黑色，g变成红色，然后把g改成cur，继续向上调整。

  • 情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑（这里需要做的其实就和AVL树中的单旋很像了，我们需要把u结点旋转下来，以维持平衡）

【数据结构进阶】手撕红黑树-LMLPHP

  • 情况三（情况二的变体）：cur为红，p为红，g为黑，u不存在/u存在且为黑（其实就是双旋，除了不用调整平衡因子，其他的和AVL树的双旋并无差别）

【数据结构进阶】手撕红黑树-LMLPHP

针对每种情况进行相应的处理即可：

// 插入值为data的节点
// 返回值含义：iterator代表新插入节点   bool：代表释放插入成功
std::pair<iterator, bool> Insert(const T& data)
{
	if (_root == nullptr) {
		_root = new Node(data);
		_root->_col = BLACK;
		return std::make_pair(iterator(_root, _root), true);
	}

	KeyOfValue kov;

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur) {
		if (kov(cur->_data) < kov(data)) {
			parent = cur;
			cur = cur->_right;
		}
		else if (kov(cur->_data) > kov(data)) {
			parent = cur;
			cur = cur->_left;
		}
		else return std::make_pair(iterator(cur, _root), false);
	}

	cur = new Node(data);
	Node* InsertNode = cur;
	if (kov(parent->_data) < kov(data)) {
		parent->_right = cur;
		cur->_parent = parent;
	}
	else {
		parent->_left = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED && cur->_col == RED) {
		Node* grandParent = parent->_parent;
		Node* uncle = nullptr;
		//   g
		// p   u
		if (grandParent->_left == parent) {
			uncle = grandParent->_right;
			if (uncle == nullptr || uncle->_col == BLACK) {
				if (parent->_left == cur) {
					RotateR(grandParent);
					parent->_col = BLACK;
					grandParent->_col = RED;
				}
				else {
					RotateL(parent);
					RotateR(grandParent);
					cur->_col = BLACK;
					grandParent->_col = RED;
				}
				break;
			}
			else {
				parent->_col = BLACK;
				grandParent->_col = RED;
				uncle->_col = BLACK;
				cur = grandParent;
				parent = grandParent->_parent;
			}
		}
		//   g
		// u   p
		else {
			uncle = grandParent->_left;
			if (uncle == nullptr || uncle->_col == BLACK) {
				if (parent->_right == cur) {
					RotateL(grandParent);
					parent->_col = BLACK;
					grandParent->_col = RED;
				}
				else {
					RotateR(parent);
					RotateL(grandParent);
					cur->_col = BLACK;
					grandParent->_col = RED;
				}
				break;
			}
			else {
				parent->_col = BLACK;
				grandParent->_col = RED;
				uncle->_col = BLACK;
				cur = grandParent;
				parent = grandParent->_parent;
			}
		}
	}
	_root->_col = BLACK;
	return std::make_pair(iterator(InsertNode, _root), true);
}

在红黑树中，由于不用调节平衡因子，双旋的复杂度大大降低，直接使用单旋并在插入过程中调整结点颜色即可。
旋转的具体内容在AVL树中（【数据结构进阶】AVL树）讲解过，这里就不赘述了。

// 左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* parentParent = parent->_parent;

	if (subRL)
		subRL->_parent = parent;
	subR->_left = parent;
	subR->_parent = parentParent;
	parent->_right = subRL;
	parent->_parent = subR;

	if (parentParent == nullptr) {
		_root = subR;
	}
	else {
		if (parentParent->_left == parent) {
			parentParent->_left = subR;
		}
		else
			parentParent->_right = subR;
	}
}

// 右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* parentParent = parent->_parent;

	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	subL->_parent = parentParent;
	parent->_left = subLR;
	parent->_parent = subL;

	if (parentParent == nullptr) {
		_root = subL;
	}
	else {
		if (parentParent->_left == parent) {
			parentParent->_left = subL;
		}
		else
			parentParent->_right = subL;
	}
}

和二叉搜索树的查找规则相同。

// 在红黑树中查找data，存在赶回该节点对应的迭代器，否则返回End()
iterator Find(const T& data)
{
	KeyOfValue kov;
	Node* cur = _root;
	while (cur) {
		if (kov(cur->_data) < kov(data))
			cur = cur->_right;
		else if (kov(cur->_data) > kov(data))
			cur = cur->_left;
		else return iterator(cur, _root);
	}
	return iterator(nullptr, _root);
}

Empty接口函数用来判断树是否为空；Size用来计算返回树结点的个数。

// 红黑树是否为空，是返回true，否则返回false
bool Empty()const
{
	return _root == nullptr;
}
// 返回红黑树中有效节点的个数
size_t Size()const
{
	return _Size(_root);
}

size_t _Size(Node* root)
{
	return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}


RBTree(const RBTree<K, T, KeyOfValue>& t)
{
	_root = _Copy(t._root);
}

Node* _Copy(Node* root)
{
	if (root == nullptr)return nullptr;
	Node* newRoot = new Node(root->_data);
	newRoot->_left = _Copy(root->_left);
	newRoot->_right = _Copy(root->_right);
	return newRoot;
}


// 将红黑树中的有效节点删除
void Clear()
{
	_Destroy(_root);
	_root = nullptr;
}

~RBTree()
{
	_Destroy(_root);
	_root = nullptr;
}

void _Destroy(Node* root)
{
	if (root == nullptr)return;
	_Destroy(root->_left);
	_Destroy(root->_right);
	delete root;
}

在IsValidRBTRee中，首先算出一条路径上的黑结点个数digit_black，然后在每条路径递归到空结点时判断黑结点个数是否相等，即可验证性质4（所有路径上黑结点个数相等）；递归的过程中，判断当前结点和父节点的颜色是否同时为红，即可验证性质3（没有连续的红结点）

// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()
{
	if (_root == nullptr)
		return true;
	Node* cur = _root;
	size_t digit_black = 0;
	while (cur) {
		if (cur->_col == BLACK)
			++digit_black;
		cur = cur->_left;
	}
	return _IsValidRBTRee(_root, digit_black, 0);
}

bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
{
	if (pRoot == nullptr) {
		if (blackCount == pathBlack)
			return true;
		else return false;
	}
	if (pRoot->_col == RED && pRoot->_parent->_col == RED) {
		return false;
	}
	if (pRoot->_col == BLACK) {
		return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack + 1)
			&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack + 1);
	}
	else {
		return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)
			&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
	}
}

这两个函数用于获取红黑树的头对象和尾迭代器。

// Begin和End迭代器
iterator Begin() 
{
	return iterator(_LeftMost(), _root);
}
iterator End()
{
	return iterator(nullptr, _root);
}

// 获取红黑树最左侧节点
Node* _LeftMost()
{
	if (_root == nullptr)
		return nullptr;
	Node* parent = _root;
	Node* cur = parent->_left;
	while (cur) {
		parent = cur;
		cur = cur->_left;
	}
	return parent;
}

红黑树的迭代器接口

迭代器的好处是可以方便遍历，使数据结构的底层实现变的透明，从而降低代码编写的复杂程度。

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	RBTreeIterator(Node* pNode,Node* root)
		: _pNode(pNode)
		,_root(root)
	{}

	// 让迭代器具有类似指针的行为
	Ref operator*();
	Ptr operator->();

	// 然迭代器可以移动：前置/后置++  
	Self& operator++();
	Self operator++(int);
	
	// 然迭代器可以移动：前置/后置-- 
	Self& operator--();
	Self operator--(int);

	// 让迭代器可以比较
	bool operator!=(const Self& s)const;
	bool operator==(const Self& s)const;

private:
	Node* _pNode;
	Node* _root;
};


// 让迭代器具有类似指针的行为
Ref operator*()
{
	return _pNode->_data;
}
Ptr operator->()
{
	return &(_pNode->_data);
}

二叉树的中序遍历并不难实现，但是要实现从任意一个结点按中序遍历跑到下一个结点，这就有相当难度了。
具体逻辑为：

  1. 右子树不为空，访问右子树的最左结点。
  2. 右子树为空（代表当前结点所在子树访问完了），沿着到根节点的路线，孩子是父亲左的那个祖先结点，就是下一个要访问的结点。
// 迭代器可以移动：前置/后置++  
Self& operator++()
{
	if (_pNode->_right) {
		_pNode = _pNode->_right;
		while (_pNode->_left) 
			_pNode = _pNode->_left;
	}
	else {
		Node* cur = _pNode;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right) {
			cur = parent;
			parent = parent->_parent;
		}
		_pNode = parent;
	}
	return *this;
}

Self operator++(int)
{
	Node* rem = _pNode;
	if (_pNode->_right) {
		_pNode = _pNode->_right;
		while (_pNode->_left)
			_pNode = _pNode->_left;
	}
	else {
		Node* cur = _pNode;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right) {
			cur = parent;
			parent = parent->_parent;
		}
		_pNode = parent;
	}
	return Self(rem);
}

这时候要判断当前迭代器是否指向尾End()，同时判断树是否为空，这就要用到传入迭代器对象中的_root了。在找到End()的前一个结点之后，按照和operator++()相反的逻辑即可实现operator--()。
具体逻辑为：

  1. 左子树不为空，访问左子树的最右结点。
  2. 左子树为空（代表当前结点所在子树访问完了），沿着到根结点的路线，孩子是父亲右的那个祖先结点，就是下一个要访问的结点。
// 迭代器可以移动：前置/后置-- 
Self& operator--()
{
	if (_pNode == nullptr) {
		if (_root == nullptr)
			assert(false);
		Node* parent = _root;
		Node* cur = parent->_right;
		while (cur) {
			parent = cur;
			cur = cur->_right;
		}
		_pNode = parent;
		return *this;
	}
	if (_pNode->_left) {
		_pNode = _pNode->_left;
		while (_pNode->_right)
			_pNode = _pNode->_right;
	}
	else {
		Node* cur = _pNode;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_left) {
			cur = parent;
			parent->_parent;
		}
		_pNode = parent;
	}
	return *this;
}

Self operator--(int)
{
	if (_pNode == nullptr) {
		if (_root == nullptr)
			assert(false);
		Node* parent = _root;
		Node* cur = parent->_right;
		while (cur) {
			parent = cur;
			cur = cur->_right;
		}
		_pNode = parent;
		return Self(nullptr);
	}
	Node* rem = _pNode;
	if (_pNode->_left) {
		_pNode = _pNode->_left;
		while (_pNode->_right)
			_pNode = _pNode->_right;
	}
	else {
		Node* cur = _pNode;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_left) {
			cur = parent;
			parent->_parent;
		}
		_pNode = parent;
	}
	return Self(rem);
}

底层就是用指针作比较。

// 让迭代器可以比较
bool operator!=(const Self& s)const
{
	return _pNode != s._pNode;
}

bool operator==(const Self& s)const
{
	return _pNode == s._pNode;
}

🌈结语

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
红黑树的底层实现到这里就要结束了，本篇的数据结构较为复杂，模板的使用也有很多容易出错的点，需要多加体会。感谢大家的支持♥

08-02 02:21
Powered by LMLPHP ©2024 Forcible Bug Maker 0.012109