【C++】————红黑树

1.红黑树的概念

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

2.红黑树的性质

关于红黑树，都有什么性质呢？下面我们来一一列举。

1. 对于一个节点，不是红色就是黑色。
2. 根节点必须是黑色的
3. 如果一个节点是红色的，则他的两个孩子节点必须是黑色的
4. 对于每个节点，从该节点到达该其所有的后代叶节点的简单路径上，均包含相同数目的黑色节点
5. 每个叶子节点都是黑色的，此处的叶子节点指的是空节点。

那么我们来想一下，为什么满足以上所有条件之后，这个子树的最长路径中节点之和不会超过最短路径中节点个数之和的两倍。

• 最短路径：上述规定4中我们说过，每个节点到叶子节点，均包含相同个数的黑色节点，所以最短路径不就是一条只有黑色节点的路径嘛，因为黑色节点必须包含嘛，所以不包含红色就是最短的
• 最长路径：最长路径是由一条红色与黑色节点交替出现产生的路径，因为我们说了红色节点的两个子节点必须是黑色节点嘛，因此红色黑色节点必须交替出现，所以最长路径是黑色节点和红色节点交替出现的情况。
• 路径长度比较：在最长路径中，每两个黑色节点之间可能插入一个红色节点，这使得最长路径的长度大致为最短路径（纯黑色节点）的两倍。这是因为在保持黑色节点数量相同的情况下，红色节点的插入只是在黑色节点之间增加了额外的节点，而这些额外的红色节点最多只能使路径长度加倍。

3.红黑树节点的定义

代码语言：javascript复制

enum Colour
{
	RED,
	BLACK
};
 
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
{
	typedef RBTreeNode<K, V> Node;
 
private:
	Node* _root = nullptr;
};

成员变量： _left、_right 和 _parent 分别指向节点的左子节点、右子节点和父节点。 _kv 是一个 pair<K, V>，存储节点的键和值。 _col 表示节点的颜色，可以是 RED 或 BLACK。 构造函数： 接收一个 pair<K, V> 作为参数，初始化节点的键值对，并将节点的颜色初始化为 RED。其他指针成员初始化为 nullptr。

4.红黑树的插入操作

我们在进行插入操作时，新节点默认是红色。红色节点的插入可能导致红黑树的性质被破坏，但通过将新节点设为红色，我们可以更容易地通过颜色变换和旋转来恢复平衡。具体来说，红色节点的插入只会影响局部区域的平衡，而黑色节点的插入则可能影响整棵树的平衡。

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

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

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑（双旋）

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 则转换成了情况2 针对每种情况进行相应的处理即可。

据以上情况写代码：

代码语言：javascript复制

代码语言：javascript复制

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->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		// 新增节点。颜色红色给红色
		cur->_col = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		return true;
	}

5.全部代码

代码语言：javascript复制

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree() = default;

	RBTree(const RBTree<K, V>& t)
	{
		_root = Copy(t._root);
	}

	RBTree<K, V>& operator=(RBTree<K, V> t)
	{
		swap(_root, t._root);
		return *this;
	}

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

	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->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		// 新增节点。颜色红色给红色
		cur->_col = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

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

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight   1 : rightHeight   1;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;

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

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

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}

	void  RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

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

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

			subL->_parent = parentParent;
		}

		parent->_bf = subL->_bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_kv);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		return newRoot;
	}

private:
	Node* _root = nullptr;
};

root c++ 存储 parent return

0 人点赞