图文详解红黑树

分手后的思念是犯贱 2023-01-11 01:12 126阅读 0赞

### 文章目录 ###

*  1.红黑树的概念
 *  2.红黑树的性质
 *  3.红黑树节点的定义
 *  4.红黑树的结构
 *  5.红黑树的插入操作
 *  6.红黑树的验证
 *  7.红黑树的删除
 *  8.红黑树与AVL树的比较

# 1.红黑树的概念 #

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

# 2.红黑树的性质 #

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

# 3.红黑树节点的定义 #

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

# 4.红黑树的结构 #

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 parent域指向红黑树的根节点，left域指向红黑树中最小的节点，right域指向红黑树中最大的节点，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]

# 5.红黑树的插入操作 #

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

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

template<class T>
    class RBTree
    {
        
    	typedef RBTreeNode<T> Node;
    public:
    	RBTree()
    	{
        
    		head = new Node();
    		head->left = head;
    		head->right = head;
    	}
    	~RBTree()
    	{
        
    		_Destroy(head->parent);
    	}
    	bool Insert(const T& data)
    	{
        
    		// 红黑树也是二叉搜索树
    		// 1. 按照二叉搜索树的规则插入新节点
    		Node*& root = GetRoot();
    		if (nullptr == root)
    		{
        
    			root = new Node(data, BLACK);
    			head->left = root;
    			head->right = root;
    			root->parent = head;
    			return true;
    		}
    		// 找待插入节点在二叉搜索树的中位置，并且保存其双亲
    		Node* cur = root;
    		Node* parent = head;
    		while (cur)
    		{
        
    			parent = cur;
    			if (data < cur->data)
    				cur = cur->left;
    			else if (data > cur->data)
    				cur = cur->right;
    			else
    				return false;
    		}
    		// 插入新节点
    		cur = new Node(data);
    		if (data < parent->data)
    			parent->left = cur;
    		else
    			parent->right = cur;
    		cur->parent = parent;
    		//检测新节点插入后，红黑树的性质是否造到破坏
    		//若满足直接退出，否则对红黑树进行旋转着色处理
    		//...
    
            // 根节点的颜色可能被修改，将其改回黑色
    		root->color = BLACK;
    		head->left = LeftMost();
    		head->right = RightMost();
    		return true;
    	}
    private:
        Node*& GetRoot()
    	{
        
    		return head->parent;
    	}
    	//获取红黑树中最小节点，即最左侧节点
        Node* LeftMost()
    	{
        
    		Node* cur = GetRoot();
    		if (nullptr == cur)
    			return head;
    
    		while (cur->left)
    			cur = cur->left;
    		return cur;
    	}
    	//获取红黑树中最大节点，即最右侧节点
    	Node* RightMost()
    	{
        
    		Node* cur = GetRoot();
    		if (nullptr == cur)
    			return head;
    		while (cur->right)
    			cur = cur->right;
    		return cur;
    	}
    private:
        PNode _pHead;
    };

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

**情况一: cur为红，p为红，g为黑，u存在且为红**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]

**注意：此处所看到的树，可能是一颗完整的树，也可能是一颗子树。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]  
**情况二: cur为红，p为红（cur为p的左孩子），g为黑，u不存在或者u为黑**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 4]

说明：  
1.如果u节点不存在，则cur一定是新插入的节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同。  
2.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

**情况三: cur为红，p为红（cur为p的右孩子），g为黑，u不存在/u为黑**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 5]

template<class T>
    class RBTree
    {
        
        //...
        
        //新节点插入成功后，红黑树的性质3可能会遭到破坏
    	//因为cur新节点的默认颜色是红色的
    	//如果parent节点的颜色是黑色的，没有违反任何性质
    	//如果parent节点的颜色是红色的，违反了性质三,必须进行调整
    	while (parent != head && RED == parent->color)
    	{
        
    		// parent != head : 该条件可以确定parent一定是树中有效的节点
    		// parent->color == RED: 该条件可以保证parent一定不是根节点
    		Node* grandFather = parent->parent;
    		if (parent == grandFather->left)
    		{
        
    			// 课件中给的情况一二三
    			Node* uncle = grandFather->right;
    			if (uncle && uncle->color == RED)
    			{
        
    				// 情况一
    				parent->color = BLACK;
    				uncle->color = BLACK;
    				grandFather->color = RED;
    
    				// 如果原来grandFather有双亲，需要继续往上更新
    				cur = grandFather;
    				parent = cur->parent;
    			}
    			else
    			{
        
    				// 情况二和情况三
    				if (cur == parent->right)
    				{
        
    					// 情况三
    					RotateLeft(parent);
    					swap(parent, cur);
    				}
    
    				// 情况二
    				parent->color = BLACK;
    				grandFather->color = RED;
    				RotateRight(grandFather);
    			}
    		}
    		else
    		{
        
    			// 课件中给的情况一二三的反情况
    			Node* uncle = grandFather->left;
    			if (uncle && RED == uncle->color)
    			{
        
    				// 情况一反情况
    				parent->color = BLACK;
    				uncle->color = BLACK;
    				grandFather->color = RED;
    
    				// 需要继续往上更新
    				cur = grandFather;
    				parent = cur->parent;
    			}
    			else
    			{
        
    				// 情况二和情况三的反情况
    				if (cur == parent->left)
    				{
        
    					//情况三的反情况
    					RotateRight(parent);
    					swap(parent, cur);
    				}
    
    				// 情况二的反情况
    				parent->color = BLACK;
    				grandFather->color = RED;
    				RotateLeft(grandFather);
    			}
    		}
    	}
    	//...
    	
    }

# 6.红黑树的验证 #

红黑树的检测分为两步：

1.  检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2.  检测其是否满足红黑树的性质

void InOrder()
    	{
        
    		_InOrder(head->parent);
    		cout << endl;
    	}
    
    	bool IsValidRBTree()
    	{
        
    		Node* root = GetRoot();
    		// 1. 空树
    		if (nullptr == root)
    			return true;
    
    		// 2. 非空----按照红黑树的性质来进行检测
    		if (BLACK != root->color)
    		{
        
    			cout << "违反红黑树性质二：根节点不是黑色的!!!" << endl;
    			return false;
    		}
    
    		// 验证性质三和性质四
    		// 优先验证性质四：每条路径中黑色节点个数相同---遍历找到每条路径中黑色节点个数然后对比
    		// 找到一条路径中黑色节点的个数---统计最左侧路径中黑色节点个数
    		size_t blockCount = 0;
    		Node* cur = root;
    		while (cur)
    		{
        
    			if (BLACK == cur->color)
    				blockCount++;
    
    			cur = cur->left;
    		}
    
    		// 检测其他路径中黑色节点的格式与最左侧路径中黑色节点个数是否相同
    		size_t pathCount = 0;
    		return _IsValidRBTree(root, blockCount, pathCount);
    	}
    
    private:
    	bool _IsValidRBTree(Node* root, size_t blockCount, size_t pathCount)
    	{
        
    		if (nullptr == root)
    		{
        
    			return true;
    		}
    
    		if (BLACK == root->color)
    		{
        
    			pathCount++;
    		}
    
    		Node* parent = root->parent;
    		if (parent != head && RED == parent->color && RED == root->color)
    		{
        
    			cout << "违反性质3：有连在一起的红色节点!!!" << endl;
    			return false;
    		}
    
    		// 如果root现在是叶子节点---说明一条路径走到底
    		if (nullptr == root->left && nullptr == root->right)
    		{
        
    			if (pathCount != blockCount)
    			{
        
    				cout << "违反性质4：路径中黑色节点的个数不一样!!!" << endl;
    				return false;
    			}
    		}
    
    		return _IsValidRBTree(root->left, blockCount, pathCount) &&
    			_IsValidRBTree(root->right, blockCount, pathCount);
    	}
    	
        void _InOrder(Node* root)
    	{
        
    		if (root)
    		{
        
    			_InOrder(root->left);
    			cout << root->data << " ";
    			_InOrder(root->right);
    		}
    	}

# 7.红黑树的删除 #

void _Destroy(Node*& root)
    {
        
    	if (root)
    	{
        
    		_Destroy(root->left);
    		_Destroy(root->right);
    		delete root;
    		root = nullptr;
    	}
    }

# 8.红黑树与AVL树的比较 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: /images/20221119/b13b5efddc334045ad7cd3db205f156d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210125161354300.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210125165812622.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210125171558403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210125174408943.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210125180759688.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70