您的位置: 首页  >  文章  >  红黑二叉树节点的插入

红黑二叉树节点的插入

分类: 文章 • 2024-05-19 15:23:10

进行红黑树节点的插入时候我们必须结合红黑树的性质，要不是真的很容易忙半天却发现写的代码漏洞百出不符合红黑树的性质

  • 主要总的来说是性质，其实笼统的来说我感觉两条性质用来验证就差不多了

    好了，列举额一下吧。

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

因为红黑树也是在搜索二叉树的基础上，我先画一颗红黑二叉树吧。
红黑二叉树节点的插入
每个节点的指向是三个方向，但是这个画起来好累啊，构造红黑树的时候一看也就明白了，这里就说明一下啊。。。

  • 红黑树节点的定义
#include <iostream>
using namespace std;


enum COLOR{ RED, BLACK };

template<class V>
struct RBTreeNode
{
	RBTreeNode(const V& value = V(), COLOR color = RED)
	: _pLeft(nullptr)
	, _pRight(nullptr)
	, _pParent(nullptr)
	, _value(value)
	, _color(color)
	{}

	RBTreeNode<V>* _pLeft;
	RBTreeNode<V>* _pRight;
	RBTreeNode<V>* _pParent;
	V _value;        // 节点值域
	COLOR _color;    // 节点的颜色
};

这里还是主要看一下插入吧，如果在把删除看一下，估计要把博客写道半夜了。
红黑树的插入时候主要分三种情况，三种情况都涉及到颜色调整的，两种都涉及到旋转，所以红黑树必须是要研究三代的，这里是必须把图画清楚的
还有新插入节点默认着色是红色的，如果是黑色，每条路径上黑色节点的个数都相等这一条很重要的性质直接就违背了

我们用pCur代表当前节点的位置，用p代表父节点的位置，用g代表祖父节点，用u代表叔父节点

  • p，u都为红色节点，g为黑色节点
    红黑二叉树节点的插入
    这种情况下插入节点的P，U都为红色，而G节点为黑色插入的节点对红黑树G的左右子树并没有造成什么影响，从这种调整来说并没有影响那条路径上的黑色节点数量，黑色节点的数量还是相等的。

  • P 为红，G为黑，U为黑或者不存在（这里分两种小情况，类似AVL树左旋右旋）
    红黑二叉树节点的插入
    这种情况我画的是pCur在P左，P在G左，这种情况下，以P为旋转中心经行左旋。

    如果我们的pCur在P右，P在G右，我们进行右旋，这两种旋转的前提都是情况2，所以就把这两种情况当作子情况归入2当中了

  • P为红，G为黑，U为黑或者不存在（前提条件类似情况2，但是三个节点所处的位置为内侧，而情况2为外侧）
    红黑二叉树节点的插入
    这种情况下是左右单旋，总之了旋转就是按我图上所画的，这种旋发，好像叫法还不一样，如果位于右子树内侧的话，旋转这是从这种旋转的右边角度来看道理上都是一个模子刻出来的

  • 插入代码

template<class V>
class RBTRee
{
	typedef RBTreeNode<V> Node;
	typedef Node* PNode;
public:
	RBTRee()
	{
		_pHead = new Node;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
		_pHead->_pParent = nullptr;
	}

	bool Insert(const V& value)
	{
		PNode& pRoot = GetRoot();

		if (nullptr == pRoot)
		{
			pRoot = new Node(value, BLACK);
		}
		else
		{
			// 找待插入节点的位置
			PNode pCur = pRoot;
			PNode pParent = nullptr;
			while (pCur)
			{
				pParent = pCur;
				if (value == pCur->_value)
					return true;
				else if (value < pCur->_value)
					pCur = pCur->_pLeft;
				else
					pCur = pCur->_pRight;
			}

			// 插入新节点
			pCur = new Node(value);
			if (value < pParent->_value)
				pParent->_pLeft = pCur;
			else
				pParent->_pRight = pCur;

			pCur->_pParent = pParent;

			// 更新节点的颜色，满足红黑树性质
			// ....
			while (pParent && RED == pParent->_color)
			{
				PNode grandFather = pParent->_pParent;
				if (pParent == grandFather->_pLeft)
				{
					PNode uncle = grandFather->_pRight;
					if (uncle && uncle->_color == RED)
					{
						// 情况一：叔叔节点存在且为红色
						pParent->_color = BLACK;
						uncle->_color = BLACK;
						grandFather->_color = RED;
						pCur = grandFather;
						pParent = pCur->_pParent;
					}
					else
					{
						// 叔叔节点不存在 || 叔叔节点存在且为黑色
						// 情况三
						if (pCur == pParent->_pRight)
						{
							RotateLeft(pParent);
							swap(pCur, pParent);
						}

						// 情况二
						RotateRight(grandFather);
						swap(grandFather->_color, pParent->_color);
					}
				}
				else
				{
					PNode unclue = grandFather->_pLeft;
					// 右侧--情况一
					if (unclue && RED == unclue->_color)
					{
						unclue->_color = BLACK;
						pParent->_color = BLACK;
						grandFather->_color = RED;
						pCur = grandFather;
						pParent = pCur->_pParent;
					}
					else
					{
						// 叔叔节点不存在 || 叔叔节点存在且为黑色
						if (pCur == pParent->_pLeft)
						{
							RotateRight(pParent);
							swap(pParent, pCur);
						}

						RotateLeft(grandFather);
						swap(grandFather->_color, pParent->_color);
					}
				}
			}
		}

		_pHead->_pLeft = LeftMost();
		_pHead->_pRight = RightMost();
		_pHead->_pParent->_color = BLACK;
		return true;
	}

插入除了分情况旋转外，其他操作其实还是类比搜索二叉树的。

  • 最后来看一下验证是否符合红黑树二叉树性质
bool IsValidRBTree()
	{
		PNode& pRoot = GetRoot();
		if (nullptr == pRoot)
			return true;

		if (RED == pRoot->_color)
		{
			cout << "违反性质二：根节点的颜色红色" << endl;
			return false;
		}

		// 获取左左侧路径中黑色节点的个数
		size_t blackCount = 0;
		PNode pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_color)
				blackCount++;

			pCur = pCur->_pLeft;
		}

		size_t pathCount = 0;
		return _IsBalidRBTRee(pRoot, pathCount, blackCount);
	}
	bool _IsBalidRBTRee(PNode pRoot, size_t pathCount, size_t blackCount)
	{
		if (nullptr == pRoot)
			return true;

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

		if (BLACK == pRoot->_color)
			pathCount++;

		if (nullptr == pRoot->_pLeft && nullptr == pRoot->_pRight)
		{
			if (pathCount != blackCount)
			{
				cout << "违反性质四: 每条路径中黑色节点必须相同" << endl;
				return false;
			}
		}

		return _IsBalidRBTRee(pRoot->_pLeft, pathCount, blackCount) &&
			_IsBalidRBTRee(pRoot->_pRight, pathCount, blackCount);
	}

	void _InOrder(PNode pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << pRoot->_value << endl;
			_InOrder(pRoot->_pRight);
		}
	}

	PNode& GetRoot()
	{
		return _pHead->_pParent;
	}

	PNode LeftMost()
	{
		PNode pRoot = GetRoot();
		if (nullptr == pRoot)
			return _pHead;

		PNode pCur = pRoot;
		while (pCur->_pLeft)
			pCur = pCur->_pLeft;

		return pCur;
	}

	PNode RightMost()
	{
		PNode pRoot = GetRoot();
		if (nullptr == pRoot)
			return _pHead;

		PNode pCur = pRoot;
		while (pCur->_pRight)
			pCur = pCur->_pRight;

		return pCur;
	}

	void RotateLeft(PNode pParent)
	{
		PNode pSubR = pParent->_pRight;
		PNode pSubRL = pSubR->_pLeft;

		pParent->_pRight = pSubRL;
		if (pSubRL)
			pSubRL->_pParent = pParent;

		pSubR->_pLeft = pParent;
		PNode pPParent = pParent->_pParent;
		pParent->_pParent = pSubR;
		pSubR->_pParent = pPParent;

		PNode& pRoot = GetRoot();
		if (pParent == pRoot)
			pRoot = pSubR;
		else
		{
			if (pPParent->_pLeft == pParent)
				pPParent->_pLeft = pSubR;
			else
				pPParent->_pRight = pSubR;
		}
	}

	void RotateRight(PNode pParent)
	{
		PNode pSubL = pParent->_pLeft;
		PNode pSubLR = pSubL->_pRight;

		pParent->_pLeft = pSubLR;
		if (pSubLR)
			pSubLR->_pParent = pParent;

		pSubL->_pRight = pParent;
		PNode pPParent = pParent->_pParent;
		pSubL->_pParent = pPParent;
		pParent->_pParent = pSubL;

		PNode& pRoot = GetRoot();
		if (pParent == pRoot)
			pRoot = pSubL;
		else
		{
			if (pPParent->_pLeft == pParent)
				pPParent->_pLeft = pSubL;
			else
				pPParent->_pRight = pSubL;
		}
	}

是否是红黑二叉树验证时候需要验证的性质其实主要是四条，但是最主要验证的还是每条路径上黑色节点的数量是否相等。验证相等时候我们选取最左侧的路径作为对比路径，计算出左侧节点的黑色节点个数，然后与验证路径对比，如果相符就满足。

  • 完整代码


#include <iostream>
using namespace std;


enum COLOR{ RED, BLACK };

template<class V>
struct RBTreeNode
{
	RBTreeNode(const V& value = V(), COLOR color = RED)
	: _pLeft(nullptr)
	, _pRight(nullptr)
	, _pParent(nullptr)
	, _value(value)
	, _color(color)
	{}

	RBTreeNode<V>* _pLeft;
	RBTreeNode<V>* _pRight;
	RBTreeNode<V>* _pParent;
	V _value;        // 节点值域
	COLOR _color;    // 节点的颜色
};


template<class V>
class RBTRee
{
	typedef RBTreeNode<V> Node;
	typedef Node* PNode;
public:
	RBTRee()
	{
		_pHead = new Node;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
		_pHead->_pParent = nullptr;
	}

	bool Insert(const V& value)
	{
		PNode& pRoot = GetRoot();

		if (nullptr == pRoot)
		{
			pRoot = new Node(value, BLACK);
		}
		else
		{
			// 找待插入节点的位置
			PNode pCur = pRoot;
			PNode pParent = nullptr;
			while (pCur)
			{
				pParent = pCur;
				if (value == pCur->_value)
					return true;
				else if (value < pCur->_value)
					pCur = pCur->_pLeft;
				else
					pCur = pCur->_pRight;
			}

			// 插入新节点
			pCur = new Node(value);
			if (value < pParent->_value)
				pParent->_pLeft = pCur;
			else
				pParent->_pRight = pCur;

			pCur->_pParent = pParent;

			// 更新节点的颜色，满足红黑树性质
			// ....
			while (pParent && RED == pParent->_color)
			{
				PNode grandFather = pParent->_pParent;
				if (pParent == grandFather->_pLeft)
				{
					PNode uncle = grandFather->_pRight;
					if (uncle && uncle->_color == RED)
					{
						// 情况一：叔叔节点存在且为红色
						pParent->_color = BLACK;
						uncle->_color = BLACK;
						grandFather->_color = RED;
						pCur = grandFather;
						pParent = pCur->_pParent;
					}
					else
					{
						// 叔叔节点不存在 || 叔叔节点存在且为黑色
						// 情况三
						if (pCur == pParent->_pRight)
						{
							RotateLeft(pParent);
							swap(pCur, pParent);
						}

						// 情况二
						RotateRight(grandFather);
						swap(grandFather->_color, pParent->_color);
					}
				}
				else
				{
					PNode unclue = grandFather->_pLeft;
					// 右侧--情况一
					if (unclue && RED == unclue->_color)
					{
						unclue->_color = BLACK;
						pParent->_color = BLACK;
						grandFather->_color = RED;
						pCur = grandFather;
						pParent = pCur->_pParent;
					}
					else
					{
						// 叔叔节点不存在 || 叔叔节点存在且为黑色
						if (pCur == pParent->_pLeft)
						{
							RotateRight(pParent);
							swap(pParent, pCur);
						}

						RotateLeft(grandFather);
						swap(grandFather->_color, pParent->_color);
					}
				}
			}
		}

		_pHead->_pLeft = LeftMost();
		_pHead->_pRight = RightMost();
		_pHead->_pParent->_color = BLACK;
		return true;
	}

	void InOrder()
	{
		_InOrder(GetRoot());
	}

	bool IsValidRBTree()
	{
		PNode& pRoot = GetRoot();
		if (nullptr == pRoot)
			return true;

		if (RED == pRoot->_color)
		{
			cout << "违反性质二：根节点的颜色红色" << endl;
			return false;
		}

		// 获取左左侧路径中黑色节点的个数
		size_t blackCount = 0;
		PNode pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_color)
				blackCount++;

			pCur = pCur->_pLeft;
		}

		size_t pathCount = 0;
		return _IsBalidRBTRee(pRoot, pathCount, blackCount);
	}

private:
	bool _IsBalidRBTRee(PNode pRoot, size_t pathCount, size_t blackCount)
	{
		if (nullptr == pRoot)
			return true;

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

		if (BLACK == pRoot->_color)
			pathCount++;

		if (nullptr == pRoot->_pLeft && nullptr == pRoot->_pRight)
		{
			if (pathCount != blackCount)
			{
				cout << "违反性质四: 每条路径中黑色节点必须相同" << endl;
				return false;
			}
		}

		return _IsBalidRBTRee(pRoot->_pLeft, pathCount, blackCount) &&
			_IsBalidRBTRee(pRoot->_pRight, pathCount, blackCount);
	}

	void _InOrder(PNode pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << pRoot->_value << endl;
			_InOrder(pRoot->_pRight);
		}
	}

	PNode& GetRoot()
	{
		return _pHead->_pParent;
	}

	PNode LeftMost()
	{
		PNode pRoot = GetRoot();
		if (nullptr == pRoot)
			return _pHead;

		PNode pCur = pRoot;
		while (pCur->_pLeft)
			pCur = pCur->_pLeft;

		return pCur;
	}

	PNode RightMost()
	{
		PNode pRoot = GetRoot();
		if (nullptr == pRoot)
			return _pHead;

		PNode pCur = pRoot;
		while (pCur->_pRight)
			pCur = pCur->_pRight;

		return pCur;
	}

	void RotateLeft(PNode pParent)
	{
		PNode pSubR = pParent->_pRight;
		PNode pSubRL = pSubR->_pLeft;

		pParent->_pRight = pSubRL;
		if (pSubRL)
			pSubRL->_pParent = pParent;

		pSubR->_pLeft = pParent;
		PNode pPParent = pParent->_pParent;
		pParent->_pParent = pSubR;
		pSubR->_pParent = pPParent;

		PNode& pRoot = GetRoot();
		if (pParent == pRoot)
			pRoot = pSubR;
		else
		{
			if (pPParent->_pLeft == pParent)
				pPParent->_pLeft = pSubR;
			else
				pPParent->_pRight = pSubR;
		}
	}

	void RotateRight(PNode pParent)
	{
		PNode pSubL = pParent->_pLeft;
		PNode pSubLR = pSubL->_pRight;

		pParent->_pLeft = pSubLR;
		if (pSubLR)
			pSubLR->_pParent = pParent;

		pSubL->_pRight = pParent;
		PNode pPParent = pParent->_pParent;
		pSubL->_pParent = pPParent;
		pParent->_pParent = pSubL;

		PNode& pRoot = GetRoot();
		if (pParent == pRoot)
			pRoot = pSubL;
		else
		{
			if (pPParent->_pLeft == pParent)
				pPParent->_pLeft = pSubL;
			else
				pPParent->_pRight = pSubL;
		}
	}
private:
	PNode _pHead;
};


void TestRBTree()
{
	int array[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	RBTRee<int> t;
	for (auto e : array)
		t.Insert(e);

	t.InOrder();

	if (t.IsValidRBTree())
	{
		cout << "valid rbtree" << endl;
	}
	else
	{
		cout << "invalid rbtree" << endl;
	}
}
int main()
{
	TestRBTree();
	return 0;

}

验证一下
红黑二叉树节点的插入

相关推荐