C++学习笔记——红黑树

发布时间:2023-11-26 13:30

在前面的基础上,来到最后一棵树,红黑树。

目录

概念

性质

结点的定义

树的结构与定义

红黑树的插入


概念

红黑树又可以叫双色树,只要有能够进行区分的两种颜色就行,通常是红色和黑色。它也是一种二叉搜索树,只是在每个结点上增加了颜色。通过颜色,来让这棵树达到平衡。

C++学习笔记——红黑树_第1张图片

性质

以红黑两种颜色为例,可以看上面的图,来看下面的性质。

  1. 根节点都是黑色
  2. 如果一个结点是红色的,则它的两个孩子都是黑色的,也即是说路径上不能是有红色结点相连
  3. 对于每个结点到其叶子结点的路径上,黑结点的个数均是相同的

结点的定义

// 节点的颜色
enum Color { 
    RED, 
    BLACK
};
// 红黑树节点的定义
template
struct RBTreeNode
{
    typedef RBTreeNode Node;
    typedef RBTreeNode* pNode;
​
    pNode pLeft_ = nullptr; // 节点的左孩子
    pNode pRight_ = nullptr; // 节点的右孩子
    pNode pParent_ = nullptr; // 节点的双亲(红黑树需要旋转,为了实现简单给出该字段)
    pair kv_; // 这里采用pair,为后续关联式容器内容做铺垫。节点的值域,自定义类型调用自己的默认构造
    Color color_ = RED; // 节点的颜色,初始化成红色,因为插入黑色就破坏了红黑树的性质
                        //每条路径上的黑色结点数量是相同的
};

树的结构与定义

在红黑树的结构中,增加了一个header的头节点(后面会用到),因为跟节点必须为黑色,为了与根节点进 行区分,将头结点给成黑色,并且让头结点的 pParent_ 域指向红黑树的根节点,pLeft_指向红黑树中最左边的结点,即就是最小的节点,pRight指向红黑树中最右边的结点,即就是最大的节点。

C++学习笔记——红黑树_第2张图片

template
class BRTree
{
public:
    typedef RBTreeNode Node;
    typedef RBTreeNode* pNode;
​
    BRTree()
    {
        header_ = new Node;
        header_->pLeft_ = header_;
        header_->pRight_ = header_;
        header_->pParent_ = nullptr;
    }
    private:
    pNode header_;
};

红黑树的插入

对于红黑树的插入,已经不再是AVL树一样调整平衡因子了,而是改颜色,当然在改的过程还是要旋转。至于这个颜色怎么改,就要看“隔壁老王”了。

由于如果插入时,其结点的父结点是黑色,则不需要做任何改变;如果其父结点是红色,则违反了红色结点不能相连的性质,故需要调整。在插入时有以下协议 :

当前结点为cur,父结点为p,爷爷结点为g,叔叔结点为u,

C++学习笔记——红黑树_第3张图片

在调整的时候就分一下下面两种情况。(调整那则p结点是红色的)

1、叔叔存在且是红色

C++学习笔记——红黑树_第4张图片

2、叔叔存在是黑色或者叔叔不存在

C++学习笔记——红黑树_第5张图片

对于第一种情况:只需要修改颜色,将p,u改为黑,g改为红,然后把g当成cur,继续向上调整,直到红色不连续

C++学习笔记——红黑树_第6张图片

对于第二种情况则需要先旋转,旋转的方式和AVL树相同的。旋转之后,p变黑,g变红。

  • 1)p为左c为左,以g为轴右旋

C++学习笔记——红黑树_第7张图片

  • 2)p为右c为右,以g为轴左旋

C++学习笔记——红黑树_第8张图片

  • 3)p为左c为右,左右旋

C++学习笔记——红黑树_第9张图片

  • 4)p为右c为左,有左旋

C++学习笔记——红黑树_第10张图片

对于(3)(4)两种情况,其实只要经过第一次旋转,就会回到第(1)(2)种情况的。

注意:双旋的时候,第一次旋转是不修改颜色的,第二次修改颜色改的是cur和g的,因为cur到g的位置上

bool Insert(const pair& kv)
{
	if (header_->pParent_ == nullptr)
	{//空树的情况下,互相认爹
		pNode root = new Node;
		root->pParent_ = header_;
		header_->pParent_ = root;

		root->kv_ = kv;
		root->color_ = BLACK;
		header_->pLeft_ = root;
		header_->pRight_ = root;

		return true;
	}


	pNode cur = header_->pParent_;
	pNode parent = header_;

	while (cur)
	{
		if (kv.first > cur->kv_.first)
		{
			parent = cur;
			cur = cur->pRight_;
		}
		else if (kv.first < cur->kv_.first)
		{
			parent = cur;
			cur = cur->pLeft_;
		}
		else
		{
			return false;
		}
	}
		pNode newnode = new Node;
	newnode->kv_ = kv;
		if (parent->kv_.first > kv.first)
	{
		parent->pLeft_ = newnode;
	}
	else
	{
		parent->pRight_ = newnode;
	}
	newnode->pParent_ = parent;
	cur = newnode;
	……

  上面的是和二叉搜索树一开始插入是相同的,现在则要开始变色了。

//1、叔叔存在且为红————修改颜色,将p,u改为黑,g改为红,然后把g当成cur,继续向上调整,直到遇见黑的。
//2、	叔叔存在且为黑或者不存在,以祖父结点为轴旋转,
		//同平衡树——
			//1)p为左c为左,右旋
			//2)p为右c为右,左旋
			//3)p为左c为右,左右旋
			//4)p为右c为左,有左旋
		while (cur != header_ ->pParent_ && cur->pParent_->color_ == RED)//直到遇见黑的或者是根节点
	{
		//cur:插入时的结点
		//parent:cur的父亲结点
		//gparent:cur的祖父结点
		//uncle:cur的叔叔结点
		pNode parent = cur->pParent_;
		pNode gparent = parent->pParent_;
		if (gparent->pLeft_ == parent)//父亲在做,则叔叔在右
		{	
			pNode uncle = gparent->pRight_;	
			if (uncle && uncle->color_ == RED)
	//叔叔存在且为红————修改颜色,将p, u改为黑,g改为红,然后把g当成cur,继续向上调整,直到遇见黑的。
			{
				parent->color_ = uncle->color_ = BLACK;
				gparent->color_ = RED;
				cur = gparent;
			}
			else
			{
				//叔叔为空或者是黑色,都需要旋转
				//1)p为左c为左,右旋、如果p为左c为右,左右旋
				if (parent->pRight_ == cur)
				{
					RotateL(parent);
					swap(cur, parent);
				}
				RotateR(gparent);
				parent->color_ = BLACK;
				gparent->color_ = RED;
				break;
			}
		}
		else     //反之父亲在右叔叔在左
		{
			pNode uncle = gparent->pLeft_;
			if (uncle && uncle->color_ == RED)
		//叔叔存在且为红————修改颜色,将p, u改为黑,g改为红,然后把g当成cur,继续向上调整,直到遇见黑的。
			{
				parent->color_ = uncle->color_ = BLACK;
				gparent->color_ = RED;
				cur = gparent;
			}
			else
			{
			//叔叔为空或者是黑色,都需要旋转
			//p为右c为右,左旋
			//4)p为右c为左,右左旋
				if (parent->pLeft_ == cur)
				{
					RotateR(parent);
					swap(cur, parent);
				}
				RotateL(gparent);
				parent->color_ = BLACK;
				gparent->color_ = RED;
				break;
			}
		}
	}

	header_->pParent_->color_ = BLACK;//不管是不是根,根都是黑色
	header_->pLeft_ = leftMost();//插入完左边更新
	header_->pRight_ = rightMost();//右边更新
	return true;
}

左旋和右旋的实现上上一篇博文,怎了不让篇幅太冗余,所以没有写。这里附上leftMost,和rightMost

pNode leftMost()
{
	pNode cur = header_->pParent_;
	while (cur && cur->pLeft_)
	{
		cur = cur->pLeft_;
	}
	return cur;
}

pNode rightMost()
{
	pNode cur = header_->pParent_;
	while (cur && cur->pRight_)
	{
		cur = cur->pRight_;
	}
	return cur;
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号