首页 > 代码库 > 红黑树详细介绍二

红黑树详细介绍二

2024-07-03 05:12:42   225人阅读

删除

        RB-TRANSPLANT(T,u,v）函数是将u子树用v来代替，在替换的时候分为了三种情况，如果u就是root结点则直接替换u，如果树里面还包含有其它结点，则将u的左右子树转移到v的左右子树上面。
RB-TRANSPLANT(T,u,v)
if u.p == T.nil
	T.root = v
else if u == u.p.left
	u.p.left = v
else
	u.p.right = v
v.p = u.p

删除代码

RB-DELETE(T,z)
y = z
y-original-color = z.color
if z.left == T.nil        //左子树为空
	x = z.left
	RB-TRANSPLANT(T, z, z.left)        //左孩子结点替换z的位置
else if z.right == T.nil                           //右子树为空
	x = z.right
	RB-TRANSPLANT(T, z, z.right)        //右孩子结点替换z的位置
else y = TREE-MINIMUM(z.right)            //左右孩子都不为空的情况下，找到z的右孩子的最左边的孩子
	y-original-color = y.color
	x = y.right             //记住y的右孩子
	if y.p == z            //z.right的最左孩子是本身时
		x.p = y 
	else 
		RB-TRANSPLANT(T, y, x)        //用x去替换y的位置
		y.right = z.right
		y.right.p = y
	RB-TRANSPLANT(T, z, y)        //用y去替换z的位置
	y.left = z.left
	y.left.p = y
	y.color = z.color
if y-original-color == BLACK        //如果y是红色则不影响
	RB-DELETE-FIXUP(T,x)
     如果y是黑色则可能已经引入了一个或多个红黑性质被破坏的情况，所以会调用RB-DELETE-FIXUP来修复红黑树的性质。如果y是红色，则y被删除或移动时，红黑性质任然保持，原因如下：
  1. 树中的黑高没有变化。
  2. 不存在两个相邻的红结点。因为y在树中占据了z的位置，在考虑到z的颜色，树中y的新位置不可能有两个相邻的红结点。另外，如果y不是z的右孩子，则y的原始右孩子x代替y。 如果y是红色，则x一定是黑色，因此用x代替y不可能使两个红结点相邻。
      3.  如果y是红色，就不可能是根结点，所以根结点任就是黑色。
        如果y是黑色的，则会产生三个问题，可以通过调用RB-DELETE-FIXUP进行补救。
  1. 如果y是原来的根结点，则y的一个红色的孩子称为新的根结点，这就违反了性质2.
  2. 如果x和x.p是红色的，则违反了性质4.
  3. 在树中移动y将导致先前包含y的任何简单路径上黑结点个数减少1.因此，y的任何祖先不满足性质5.
        改正这一问题的办法就是将现在路径上黑节点个数加1，则在这种假设下，性质5成立。当将黑节点y删除或移动时，将其黑色的“下推‘给结点x。现在的问题变为结点x可能既不是红色，又不是很色，从而违反了性质1.现在结点x是双重黑色或者红黑色，这就分别给包含x的简单路径上黑结点数贡献2或1.x的color属性任然是RED(如果x是红黑色的)或者BLACK(如果x是双重黑色的)。换句话说，结点额外的黑色是针对x结点的，而不是反映在它的color属性上的。

删除结点之后的修复

RB-DELETE-FIXUP(T,x)
while x != T.nil and x.color == BLACK
	if x == x.p.left
		w = x.p.right
		if w.color == RED        //x的叔叔结点是红色
			w.color = BLACK                    //case 1
			x.p.color = RED                       //case 1    
			RB-ROTATE-LEFT(T, x.p)       //case 1
			w = x.p.right                          //case 1
		if w.right.color == BLACK and w.left.color == BLACK		//w的两个子结点都是黑色
			w.color = RED       //case 2
			x = x.p                   //case 2
		else if w.right.color == BLACK		//w的左孩子是红色，右孩子是黑色
			w.left.color = BLACK                   //case 3
			w.color = RED                   //case 3
			RB-ROTATE-RIGHT(T, w)                   //case 3
			w = x.p.right                   //case 3
		else		//w的两个孩子都是红色或者是右孩子是红色
			w.right.color = BLACK                   //case 4
			w.color = x.p.color                   //case 4
			x.p.color = BLACK                   //case 4
			RB-ROTATE-LEFT(T, x.p)                   //case 4
			x = T.root                   //case 4
	else
		w = x.p.left
		if w.color == RED
			x.p.color = RED
			w.color = BLACK
			RIGHT-ROTATE(T, x.p)
			w = x.p.left
		if w.right.color == BLACK and w.left.color == BLACK
			w.color = RED
			x = x.p
		else if w.left.color == BLACK
			w.right.color = BLACK
			w.color = RED
			LEFT-ROTATE(T, w)
			w = x.p.left
		else
			w.left.color = BLACK
			w.color = x.p.color
			x.p.color = BLACK
			RIGHT-ROTATE(T, x.p)
			x = T.root
x.color = BLACK



      第1~22行中while循环的目标是将额外的黑色沿树上移，直到：
  1. x指向红黑结点，此时在第23行中，将x着为黑色。
  2. x指向根结点，此时可以简单的”移除“额外的黑色。
  3. 执行适当的旋转和重新着色，退出循环。
      在while循环中，x总是指向一个具有双重黑色的非根结点。在第2行要判断x是其父结点x.p的左孩子还是右孩子。
     情况1： x的兄弟结点w是红色的
     情况1发生的在结点x的兄弟结点w为红色时。因为w必须有黑色子结点，所以可以改变w和x.p的颜色，然后对x.p做一次左旋转而不违反红色树的任何性质。现在，x的新兄弟结点是旋转之前w的某个子结点，其颜色为黑色。这样，就将情况1转换为情况2、3、4处理。
     当结点w为黑色时，直接就属于2、3、4中的一种，这些情况是由w的孩子结点的颜色来区分的。
   情况2：x的兄弟结点w是黑色的，而且w的两个子结点都是黑色的。
   情况3：x的兄弟结点w是黑色的，w的左孩子是红色的，右孩子是黑色的。
   情况4：x的兄弟结点w是黑色的，且右孩子是黑色的。


联系
我们