对于红黑来说,其是从 AVL 树演变而来,因此首先应该满足 AVL(平衡二叉树)的性质。然后在满足以下性质:
(1)节点非红即黑
(2)根节点必须是黑
(3)叶子结点为空且必须为黑
(4)任意一个节点到叶节点的路径中黑节点子树相同
例如:
满足上述性质就是一棵红黑树了,但是对于红黑树的删除与插入必须也要满足以上的条件,下面就来说一下红黑树的插入与删除
情形 1:当为空树时候,此时只有一个节点 N(不满足性质 1), 只要把 N 改为黑色就可以了。
情形 2:当不为空时候,但是父节点为黑色,这时候只要直接插入节点就不会破坏红黑树。
情形 3:当 N 为红,P 为红,祖父节点一定存在且为黑,叔父节点也为红。
这时候就需要把 G 改为红,叔节点改为黑,父节点改为黑,但是这时候还没结束,由于祖父节点为红,可能祖父节点 G 的父节点为红这就又又违反了性质,但依然按照原先的方式进行向上检索。知道满足为止。例如:
情形 4: N 为红,P 为红,U 为黑,G 为黑(或者 P 为 G 的右孩子,N 为 P 的左孩子;反正就是同向的)这时候只要将 G 变为黑,以 P 为轴顺时针旋转就可以 ,例如:
情形 5: N 为红,P 为红,U 为黑,P 为 G 的左孩子,N 为 P 的右孩子(或者 P 为 G 的右孩子,N 为 P 的左孩子;反正两方向相反)。这时候需要以 N 为轴旋转至 P 原来的是位置。这时候就出现了情形 4 的情形,只要按照情形 4 做相应的变换就 OK.
情形 1 :S 为红色(那么父节点 P 一定是黑,子节点一定是黑),N 是 P 的左孩子(或者 N 是 P 的右孩子)。
情形 2: P、S 及 S 的孩子们都为黑。
情形 3: P 为红(S 一定为黑),S 的孩子们都为黑。
情形 4: P 任意色,S 为黑,N 是 P 的左孩子,S 的右孩子 SR 为红,S 的左孩子任意(或者是 N 是 P 的右孩子,S 的左孩子为红,S 的右孩子任意)。
操作:SR(SL)改为黑,P 改为黑,S 改为 P 的颜色,P、S 变换–这里相对应于 AVL 中的右右中的旋转(或者是 AVL 中的左左旋转),结束。
解析:P、S 旋转有变色,等于给 N 这边加了一个黑节点,P 位置(是位置而不是 P)的颜色不变,S 这边少了一个黑节点;SR 有红变黑,S 这边又增加了一个黑节点;这样一来又恢复了平衡,结束。
** 情形 5:**P 任意色,S 为黑,N 是 P 的左孩子,S 的左孩子 SL 为红,S 的右孩子 SR 为黑(或者 N 是 P 的有孩子,S 的右孩子为红,S 的左孩子为黑)。
操作:SL(或 SR)改为黑,S 改为红,SL(SR)、S 变换;此时就回到了情形 4,SL(SR)变成了黑 S,S 变成了红 SR(SL),做情形 4 的操作即可,这两次变换,其实就是对应 AVL 的右左的两次旋转(或者是 AVL 的左右的两次旋转)。
(1)红黑树多用在内部排序,即全放在内存中的,微软 STL 的 map 和 set 的内部实现就是红黑树。
(2)红黑树在函数式编程中也特别有用,
来源: http://blog.csdn.net/qq_36675830/article/details/78463262