270-RBTree(红黑树)

逃离我推掉我的手 2022-11-19 01:07 122阅读 0赞

## RBTree(红黑树) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
**红色节点不容许连续，黑色节点容许连续。根一定是黑色的，哨兵节点一定是黑色的。从任意节点出发到达哨兵节点的黑色节点个数要一致。**  
**红黑树近似于平衡。**

## 红黑树的定义 ##

typedef enum {
         RED = 0, BLACK = 1 } ColorType; 
    typedef int KeyType;
    typedef struct rb_node
    {
        
    	rb_node *leftchild;//左孩子 
    	rb_node *parent;//双亲 
    	rb_node *rightchild;//右孩子 
    	ColorType color;//颜色结点，红，黑 
    	KeyType  key;//关键码 
    }rb_node;
    
    
    typedef struct
    {
        
    	struct rb_node* root;//根节点 
    	struct rb_node* NIL; //空节点 
    	int cursize;//个数 
    }RBTree;

## 理解红黑树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
**我们看左图，如果从最上面的黑色节点出发，路径上看黑色数目都是2个，看右图，从最顶点的红色出发，黑色数目都是2个，这两个图是一样的。不会发生变化。**

![在这里插入图片描述][20210413201536600.png_pic_center]  
**当我们插入第一个数据12，颜色必须是红色，但是它作为根节点，它的颜色由红色变为黑色，还有一个黑色节点作为哨兵节点，12的左孩子和右孩子都指向哨兵节点，插入23，颜色都是红色，双亲是黑色，可以（不许红色连续），我们插入34,34也是红色，在右边插入，但是它的双亲是红色，不行，就找双亲的双亲的左边，但是是哨兵节点（黑色），无法通过着色的改变来确定黑色的数目。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
**我们就以23位基准，把12绕到23，进行左旋转。23替代12的位置，23变为黑，12变为红。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
**我们插入45，45是红色，45的双亲是红色，找双亲的双亲的左边也是红色**，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
**我们插入56,56是红色，双亲是红色，双亲的双亲的左边是哨兵，不能调整，只能进行旋转，把34改为红色，左单旋转。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]  
**我们插入50，双亲是红色，在56的左边，在折线上，双亲的双亲的左边是红色**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
**我们插入78，大于56，颜色是红色，双亲是黑色，不需要调整。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
**我们插入89，是红色，双亲是红色，双亲的双亲的左边是红色**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]

## 购买节点 ##

rb_node* Buynode(KeyType kx)//购买结点 
    {
        
    	rb_node* s = (rb_node*)malloc(sizeof(rb_node));
    	if (nullptr == s) exit(1);
    	memset(s, 0, sizeof(rb_node));
    	s->color = RED;
    	s->key = kx;
    	return s;
    }
    
    void Freenode(rb_node* p)//释放结点 
    {
        
    	free(p);
    }

## 左旋转 ##

void RotateLeft(RBTree& tree, rb_node* ptr)//左旋转 
    {
        
    	rb_node* newroot = ptr->rightchild;
    	newroot->parent = ptr->parent;// 1
    	ptr->rightchild = newroot->leftchild;
    	if (newroot->leftchild != nullptr)
    	{
        
    		newroot->leftchild->parent = ptr;// 2
    	}
    	newroot->leftchild = ptr;
    	if (ptr->parent == nullptr)
    	{
        
    		tree.root = newroot;
    	}
    	else
    	{
        
    		if (ptr->parent->leftchild == ptr)
    		{
        
    			ptr->parent->leftchild = newroot;
    		}
    		else
    		{
        
    			ptr->parent->rightchild = newroot;
    		}
    	}
    	ptr->parent = newroot;	 // 3
    }

## 右旋转 ##

void RotateRight(RBTree& tree, rb_node* ptr)//右旋转 
    {
        
    	rb_node* newroot = ptr->leftchild;
    	newroot->parent = ptr->parent;//1
    	ptr->leftchild = newroot->rightchild;
    	if (newroot->rightchild != nullptr)
    	{
        
    		newroot->rightchild->parent = ptr;
    	}
    	newroot->rightchild = ptr;
    	if (ptr->parent == nullptr)
    	{
        
    		tree.root = newroot;
    	}
    	else
    	{
        
    		if (ptr->parent->leftchild == ptr)
    		{
        
    			ptr->parent->leftchild = newroot;
    		}
    		else
    		{
        
    			ptr->parent->rightchild = newroot;
    		}
    	}
    	ptr->parent = newroot;
    }

## 插入和调整 ##

void Adjust_RBTree(RBTree& tree, rb_node *ptr) 
    {
        
    	rb_node* _X = nullptr;
    	while (ptr->parent != nullptr && ptr->parent->color != BLACK)
    	{
        
    		if (ptr->parent->parent->rightchild == ptr->parent)
    		{
        
    			_X = ptr->parent->parent->leftchild;
    			if (_X->color == RED)
    			{
        
    				ptr->parent->color = BLACK;
    				_X->color = BLACK;
    				ptr->parent->parent->color = RED;
    				ptr = ptr->parent->parent;
    			}
    			else
    			{
        
    				if (ptr->parent->leftchild == ptr)
    				{
        
    					ptr = ptr->parent;
    					RotateRight(tree, ptr);
    				}
    				ptr->parent->color = BLACK;
    				ptr->parent->parent->color = RED;
    				RotateLeft(tree, ptr->parent->parent);
    			}
    
    		}
    		else  // left 
    		{
        
    			_X = ptr->parent->parent->rightchild;
    			if (_X->color == RED)
    			{
        
    				ptr->parent->color = BLACK;
    				_X->color = BLACK;
    				ptr->parent->parent->color = RED;
    				ptr = ptr->parent->parent;
    			}
    			else
    			{
        
    				if (ptr->parent->rightchild == ptr)
    				{
        
    					ptr = ptr->parent;
    					RotateLeft(tree, ptr);
    				}
    				ptr->parent->color = BLACK;
    				ptr->parent->parent->color = RED;
    				RotateRight(tree, ptr->parent->parent);
    			}
    		}
    	}
    	tree.root->color = BLACK;
    }
    
    
    
    bool Insert(RBTree& tree, KeyType kx)
    {
        
    	rb_node* p = Buynode(kx);
    	Adjust_RBTree(tree, p);
    	return true;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/c7fd245b4dec485a919763e2e6367aff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/d28b33b0a6f74215932053e7f2413699.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/0ac900b1536542ac89803bf982b2ad4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/dff4bebc395c47a2b8dab5678712560e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/2fb48c9f9b7d4f049137c820b15d0055.png
[20210413201536600.png_pic_center]: /images/20221022/7d03c91449c740b9b77377a436d4a9e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/2d21e1b404aa4f26ab808d21d8096335.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/82f8d505423847c991362c474393725b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221022/4053a573b6e44a4a98186d18c41df26b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221022/3a9c06c54fad4cf88c1b70783238b982.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221022/ba9584caef43436aa09589b38c9f788b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221022/0f33e9b4d2d74141af9eb7d03fc5446a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221022/639b4492b3d34c2dbc00168353b3acbc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221022/862ae10d707b4b06b29eba4bfd11d548.png