首页 > 代码库 > 红黑树插入详解

红黑树插入详解

查找二叉树插入节点:

已知查找二叉树的性质为根节点的值大于左子树的值,小于右子树的值,按照此规律,根据要插入的值为其寻找合适的插入位置,最后将其插入即可:

Tree-Insert(T,z)
{
	x = root(T);
	y = NULL;
	while(x != NULL)
	{
		y = x;
		if(key[z] < key[x])
			x = left[x];
		else
			x = right[x];
	}
	p[z] = y;
	if(y == NULL)
		root[T] = z;
	else if(key[z] < key[y])
		left[y] = z;
	else
		right[y] = z;
}

红黑树插入节点:

红黑树插入节点类似于查找二叉树,但需要注意的是当新的节点插入红黑树时,可能会导致无法保持红黑树的性质,因此需对其进行修改。

通过函数RB-INSERT-FIXUP(T,z)使其保持红黑性质。

RB-Insert(T,z)
{
	x = root(T);
	y = nil[T];
	while(x != nil[T])
	{
		y = x;
		if(key[z] < key[x])
			x = left[x];
		else
			x = right[x];
	}
	p[z] = y;
	if(y == nil[T])
		root[T] = z;
	else if(key[z] < key[y])
		left[y] = z;
	else
		right[y] = z;
	left[z] = nil[T];
	right[z] = nil[T];
	color[z] = RED;
	RB-INSERT-FIXUP(T,z);
}

不同于之前查找二叉树的插入,红黑二叉树的插入过程中主要在最后几步与其有异:将插入节点的颜色置红,修补红黑树性质。

接下来分析,当新的节点插入时,打破了红黑树的哪些性质。

红黑树的性质为:

1.      每个节点或是红的,或是黑的。

2.      根节点是黑的

3.      叶节点是黑的

4.      如果一个节点是红的,则其两个儿子都是黑的

5.      对每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点

易知新节点的插入不会影响性质1、3、5

现在的问题为如何保持性质2和4。

当z插入红黑树时,考虑z的父节点,当父节点为黑色时,性质2和4仍能保持,因此现考虑while(color[p[z]] == RED)时,如何保持性质2和4。

插入z后有两种情况:z == left[p[z]]或z == right[p[z]]。这里首先考虑z == left[p[z]]。

已知color[p[z]] == RED ,则由红黑树性质4知,color[p[p[z]]]必为黑色。因为若p[z]的父节点为红色,则p[z]需为黑色,矛盾。而z的叔叔(设为y)颜色即可能是红色,也可能是黑色。若y为红色,为保持性质4,应将p[z]、y均设为黑色,p[p[z]]设为红色。之后让z = p[p[z]],继续循环;若y为黑色,此时z有可能是p[z]的左子树或右子树。当z为右子树时,可执行以下步骤:z = p[z];LEFT-ROTATE(T,z),可将其转变为z为左子树的情况。此时右旋p[z],则p[p[z]]变成了p[z]的右子树,z仍为p的左子树。为保持红黑树性质,将p[z]置黑,p[z]的右子树置红。

最后,color[p[z]] != RED时,为保证性质2,color[root[T]] = BLACK;

 


红黑树插入详解