【数据结构】二叉树---红黑树的实现

目录

一.  红黑树的概念及性质

二.  红黑树结点结构的定义

三.  红黑树的插入操作

     1. 情况一

     2. 情况二

       3. 情况三

四.  红黑树的验证

五.  红黑树与AVL树的比较

---

一.  红黑树的概念及性质

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，
可以是红色或黑色。

红黑树具有以下性质：

   1. 每个结点要么是红色，要么是黑色。
   2. 根结点是黑色。
   3. 每个叶结点（NIL结点，空结点）是黑色。
   4. 如果一个结点是红色，则它的子结点必须是黑色(所有路径上不能有两个连续的红色节点)
   5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

        这些性质保证了红黑树的关键性质，从根到叶子的最长路径不会超过最短路径的两倍，从而保证了红黑树的平衡性。红黑树常被用于实现集合和映射等数据结构，因为其在插入、删除等操作上具有较好的性能表现

二.  红黑树结点结构的定义

红黑树节点结构通常包含以下几个字段：

       键值（key）：用于比较和排序节点的值。
       指向父节点的指针（parent）：指向当前节点的父节点。
       指向左节点的指针（left）：指向当前节点的左节点。
       指向右节点的指针（right）：指向当前节点的右节点。
       颜色（color）：表示节点的颜色，通常用一个位来表示，比如红色和黑色。

红黑树节点结构的定义表示如下：

在这里通过定义枚举结构来表示红、黑两种颜色

//定义结点的颜色
enum Color
{
	RED,    //表示红色
	BLACK   //表示黑色
};

//红黑树的结点定义类模板
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;    //指向左结点
	RBTreeNode<T>* _right;   //指向右节点
	RBTreeNode<T>* _parent;  //指向父节点(红黑树需要旋转，为了实现简单给出该字段)          
	T _data;        //结点值
	Color _col;     //结点的颜色

    //结点的构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)      //默认初始化红色
	{}

};

注意：这里将插入结点的默认颜色给成红色

  

       当插入一个新节点时，如果将该节点默认设置为黑色，可能会破坏红黑树的性质，需要进行额外的操作来恢复平衡。而将新插入的节点默认设置为红色，是为了满足红黑树的性质，特别是在插入节点时能够更容易地维持这些性质。红黑树的性质要求如果一个节点是红色，则其子节点必须是黑色，这是为了确保从根节点到叶子节点的每条路径上黑色节点的数量相等，从而保持树的平衡性。

       因此，将节点的默认颜色设置为红色是为了简化插入操作，并确保在插入新节点后能够更轻松地维护红黑树的平衡性。

三.  红黑树的插入操作

       因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质4，不能有连续的红色节点，此时需要对红黑树分情况来讨论：

说明：这里所用到的字段
                C 表示当前新插入节点，

                P 表示父节点(当前节点的父节点)，
                G 表示祖父节点(父节点的父节点)，

                U 表示叔叔节点(父节点的兄弟节点)

     1. 情况一

新插入节点(C)的父节点(P)是红色，且新插入节点的叔叔节点(U)(父节点的兄弟节点) 存在且是红色。
这时需要进行颜色调整和递归调整。     

颜色调整：将 P 和 U 改为 黑，G 改为 红

注意：G若为根结点，则改为黑色

           G若为子树，则继续递归向上调整

     2. 情况二

新插入节点(C)的父节点(P)是红色，但新插入结点的叔叔节点(U)是黑色或空节点：

 叔叔结点（U）不为空：

    1. 父节点(P)是其祖父节点(G)的左节点，新插入节点(C)是其父节点(P)的右节点，左单旋转

    2. 父节点(P)是其祖父节点(G)的右节点，新插入节点(C)是其父节点(P)的左节点，右单旋转

 颜色调整 ：G 改为 红，C 改为 黑            

       3. 情况三

新节点(C)的父节点(P)是红色，但新节点的叔叔节点(U)是黑色或空节点：

 叔叔结点（U）为空：

    1. 父节点(P)是其祖父节点(G)的左节点，新插入节点(C)是其父节点(P)的左节点，右单旋转

    2. 父节点(P)是其祖父节点(G)的右节点，新插入节点(C)是其父节点(P)的右节点，左单旋转

颜色调整 ：P 改为 黑，G 改为 红

	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data> data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

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

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//一：父节点在祖父节点的左侧
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况1：叔叔节点存在且为红；
				if (uncle && uncle->_col == RED)
				{
					//父和叔叔节点变为黑色，祖父节点变为红色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					//情况2：叔叔不存在 或 叔叔存在且为黑色
					//旋转 + 变色
					if (cur == parent->_left) //cur在parent的左
					{
						RotateR(grandfather);   //以grandfather进行右单旋转
						parent->_col = BLACK;   //调整颜色
						grandfather->_col = RED;
					}
					else                      //cur在parent的右
					{
						RotateL(parent);         //以parent进行左旋
						RotateR(grandfather);    //以grandfather进行右旋
						cur->_col = BLACK;       //调整颜色
						grandfather->_col = RED; 
					}
					break;
				}
			}
			else  //二：父节点在祖父节点的右侧
			{
				Node* uncle = grandfather->_left;
				//情况1：叔叔节点存在且为红；
				if (uncle && uncle->_col == RED)
				{
					//父和叔叔节点变为黑色，祖父节点变为红色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					//情况2：叔叔不存在 或 叔叔存在且为黑色
					//旋转 + 调整颜色
					// cur在parent的右
					if (cur == parent->_right)
					{
						RotateL(grandfather);   //以grandfather进行右单旋转
						parent->_col = BLACK;   //调整颜色
						grandfather->_col = RED;
					}
					else  // cur在parent的左
					{
						RotateR(parent);         //以parent进行右旋
						RotateL(grandfather);    //以grandfather进行左旋
						cur->_col = BLACK;       //调整颜色
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;                  
		return true;
	}


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

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

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

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

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

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

四.  红黑树的验证

红黑树的验证分为两步：

     1. 验证其是否满足二叉搜索树

                中序遍历是否为有序序列

     2. 验证其是否满足红黑树的性质

              1. 根是黑色的
              2. 没有连续的红色节点
              3. 每条路径的黑色节点的数量相等

	//中序遍历 验证是否有序
    void InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		InOrder(root->_left);
		cout << root->_data << " ";
		InOrder(root->_right);

	}

    //验证是否满足红黑树的性质
    bool IsValidRBTRee()
	{
		if (_root && _root->_col == RED)
			return false;

		int refBlackNum = 0;  //作为路径上黑色节点的参考值
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				refBlackNum++;
			cur = cur->_left;
		}
		return _IsValidRBTRee(_root, 0, refBlackNum);
	}

    // 检测红黑树是否为有效的红黑树
	bool _IsValidRBTRee(Node* root, int blackNum, int refBlackNum)
	{
		if (root == nullptr)  //每条路径的黑色节点的数量是否相等
		{
			if (blackNum != refBlackNum)
			{
				cout << "黑色节点的数量不相等" << endl;
				return false;
			}
			cout << blackNum << endl;   
			return true;
		}

        //是否存在连续的红节点
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}
        
        // 统计黑色节点的个数
		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return _IsValidRBTRee(root->_left, blackNum, refBlackNum)
			&& _IsValidRBTRee(root->_right, blackNum, refBlackNum);
	}

五.  红黑树与AVL树的比较

红黑树和AVL树是两种常见的自平衡二叉搜索树结构。它们都可以保持树的平衡，以确保在插入和删除操作后，树的高度始终保持在较小的范围内，从而保证了检索、插入和删除操作的时间复杂度为O(logn)。

 一，对平衡性要求：  

        1. AVL树要求严格的平衡性，即任意节点的左右子树的高度差的绝对值不超过1。

        2. 红黑树放宽了对平衡性的要求，它通过引入红黑节点的颜色来保持大致平衡，即任意节点的黑结点高度相等

二，插入和删除操作的性能：

        1. AVL树对插入和删除操作的平均性能略低于红黑树，因为AVL树需要更频繁地进行旋转操作来保持严格的平衡。

        2. 红黑树在插入和删除操作时的性能相对较好，因为它对平衡性的要求较松，旋转的次数相对较少

三，查询性能：

        由于两种树结构的高度始终保持在较小范围内，它们的查询性能相似，都为O(logn)

---