替代 Y 结点为 X 结点的位置,先将 Y 结点的父母结点设置为 X 结点的父结点,并设置 X 的父结点的子结点（根据 X 是 X 父结点的子结点位置来设置为左或者右结点）,如果 X 的父结点为空,则设置 Y 的父结点也为空。
原先的结点布局为 X 的子结点为 a 和 Y ,Y 的子结点为 b 和 c。旋转后结点布局应该为 X 的子结点为 a 和 b ,y 的子结点为 X 和 c。 其结点设置过程为设置 X 的 左结点为 a,右结点为 b,并将 a 和 b 的父结点设置 X 。 同理如下可以设置 Y 的结点也这样。
右旋转
原理同左旋转过程。
旋转过程可行性分析
假如树本身就是一棵平衡二叉树,只是进行旋转操作,在左旋转过程中,变换的操作为将 Y 的左结点设置为 X 的右结点,将 X 设置为 Y 的左结点。 根据二叉平衡树的定义,其根结点大于所有的左结点,小于所有的右结点。那么 b 结点肯定比 X 大,但是比 Y 小。所以 b 可以作为 X 的右结点。因为 Y 结点比 X 大所以,X 肯定可以作为 Y 的左结点。 并且 b 结点也是比 Y小的。所以 Y 的左子树上所有结点的值。肯定比 Y 小,证明完毕。其右旋转过程同理。
// y 替换 x func(t *Tree)leftRotate(x *Node) { // Default node inserted will be a red node y := x.right // 设置 y 的左结点到 x 下 x.right = y.left if y.left != nil { y.left.parent = x } // 设置 y 的父结点为 x 父结点 y.parent = x.parent
// x 是根结点 // this is root if x.parent == nil { t.root = y } else { // 将 x 的父结点指向 y if x == x.parent.left { x.parent.left = y } else { x.parent.right = y } } // 设置 y 的 左结点为 x y.left = x // 设置 x 的 父结点为 y x.parent = y }
func(t *Tree)rightRotate(x *Node) { y := x.left x.left = y.right if y.right != nil { y.right.parent = x } y.parent = x.parent
// this is root if x.parent == nil { t.root = y } else { if x == x.parent.right { x.parent.right = y } else { x.parent.left = y } } y.right = x x.parent = y
我画出违反红黑树的四种情况如上图所示。其中图一需要右旋转过程,图二需要左旋转过程修复。图三需要先进行左旋转然后进行右旋转过程。图四需要先进行右旋转然后进行左旋转过程修复。修复后的情况为 Y 为红色结点,X 和 Z 都是黑色结点,满足红黑树的来满足第四条性质。
其中在违反红黑树的四种情况下。其中 X 插入的颜色为红色,在这种情况下如果 X 的 父结点是红色,那么违反了性质 4 ： 每个红色结点到两个结点一定都是黑色。在其前提下,又要分为两种情况判断其 X 的 Uncle 结点的颜色。
假如 Uncle 结点是红色,那么性质 5 并没有被违反,因此只需要重新设置结点的颜色即可,将 P 结点设置为黑色,将 G 结点设置为红色,将 U 结点设置为黑色。在这样的情况下满足性质 4 和性质 5。并且不需要关心 X 结点是 P 结点的左结点还是右结点,P 是 G 结点的左结点还是右结点。图中所列出的只是其中一种情况。因为将 G 结点设置为红色了,所以需要递推检查 G 的结点是否满足性质 4 和 性质 5。
假如 Uncle 结点是黑色结点,X 是红色结点,因此性质 5 也被破坏了。其修复过程为,假如 X 是 P 的右结点,需要进行左旋转操作为第二步操作。在这种情况下将 G 结点设置为红色,将 P 结点设置为黑色,然后进行右旋转过程。此时 P 结点被设置为根结点, P 结点为黑色,因此 P 结点满足性质 4 ,不用在继续往上递推修复。同时整个树满足性质 4 和 性质 5 （因为每个叶子（NIL）为黑色）。同时上面情况的对称情况同理。
实现
假如不考虑红黑树的修复,代码如下:
根据 value 找到合适的插入位置
将插入结点的父结点设置为 y
根据 y 结点为空将该结点设置为根结点。
如果 y 结点不为空,就判断 y 结点 value 值 和 x 的 value 值的大小,来找到插入的位置。
func(t *Tree)insert(item *Node) { var y *Node x := t.root
for x != nil { y = x if item.key < x.key { // insert value into the left node x = x.left } elseif item.key > x.key { // insert value into the left node x = x.right } else { // value exists return } }
t.size++ item.parent = y item.color = RED
if y == nil { item.color = BLACK t.root = item return } elseif item.key < y.key { y.left = item } else { y.right = item } // Checking RBT conditions and repairing the node t.insertRepairNode(item)
func(t *Tree)insertRepairNode(x *Node) { // N's parent (P) is not black var y *Node for x != t.root && x.parent.color == RED { if x.parent == x.grandparent().left { y = x.grandparent().right if y != nil && y.color == RED { x.parent.color = BLACK y.color = BLACK x.grandparent().color = RED x = x.grandparent() } else { if x == x.parent.right { x = x.parent t.leftRotate(x) } x.parent.color = BLACK x.grandparent().color = RED t.rightRotate(x.grandparent()) } } else { y = x.grandparent().left if y != nil && y.color == RED { x.parent.color = BLACK y.color = BLACK x.grandparent().color = RED x = x.grandparent() } else { if x == x.parent.left { x = x.parent t.rightRotate(x) } x.parent.color = BLACK x.grandparent().color = RED t.leftRotate(x.grandparent()) } } } // N is the root node, i.e., first node of red–black tree t.root.color = BLACK
func(t *Tree)Delete(key int64) { z := t.Search(key) if z == nil { return } t.delete(z) }
func(t *Tree)Search(key int64) *Node { x := t.root
if x == nil { returnnil }
for x != nil { switch { case key == x.key: return x case key < x.key: x = x.left case key > x.key: x = x.right } }
returnnil }
func(t *Tree)delete(z *Node) { var x, y *Node y = z
if z.left == nil { x = z.right t.replace(z, z.right) } elseif z.right == nil { x = z.left t.replace(z, z.left) } else { y = z.successor() z.key = y.key z.value = y.value if y.left != nil { x = y.left } elseif y.right != nil { x = y.right } if x != nil { x.parent = y.parent } if y.parent == nil { t.root = x } else { if y == y.parent.left { y.parent.left = x } else { y.parent.right = x } } }
if y.color == BLACK { t.deleteRepairNode(x) } t.size--
y.parent = nil y.left = nil y.right = nil }
func(t *Tree)replace(a, b *Node) { if a.parent == nil { t.root = b } elseif a == a.parent.left { a.parent.left = b } else { a.parent.right = b } if b != nil { b.parent = a.parent } }
func(n *Node)successor() *Node { if n.right != nil { return n.right.minimum() } y := n.parent for y != nil && n == y.right { n = y y = y.parent } return y }
func(t *Tree)deleteRepairNode(x *Node) { if x == nil { return } var w *Node for x != t.root && x.color == BLACK { if x == x.parent.left { w = x.sibling() // case2 if w.color == RED { w.color = BLACK x.parent.color = RED t.leftRotate(x.parent) w = x.parent.right } // case3 4 这里是因为违反了性质五 if w.left.color == BLACK && w.right.color == BLACK { w.color = RED x = x.parent } else { // case5 if w.right.color == BLACK { w.left.color = BLACK w.color = RED t.rightRotate(w) w = x.parent.right } // case6 w.color = x.parent.color x.parent.color = BLACK w.right.color = BLACK t.leftRotate(x.parent) // 退出循环 x = t.root } // 对称情况 } else { w = x.sibling() if w.color == RED { w.color = BLACK x.parent.color = RED t.rightRotate(x.parent) w = x.parent.left } if w.left.color == BLACK && w.right.color == BLACK { w.color = RED x = x.parent } else { if w.left.color == BLACK { w.right.color = BLACK w.color = RED t.leftRotate(w) w = x.parent.left } w.color = x.parent.color x.parent.color = BLACK w.left.color = BLACK t.rightRotate(x.parent) x = t.root }
} } // case1 x.color = BLACK }
func(n *Node)sibling() *Node { p := n.father() // No parent means no sibling if p == nil { returnnil } if n == p.left { return p.right } return p.left }
代码中我已经标明了case1 ~ case6,还有其对称情况。上面已经说过了,这里就不再说了。
五、总结
红黑树插入过程较为复杂,但是只要清楚破坏性质 4 的四种情况,应该就很容理解。对于删除过程后面会继续补充完整。其删除过程看起来很复杂,其实只不过是穷举了五种情况n.parent(),n.sibling(),n.sibling().left,n.sibling().right为红色结点和全部都为黑色结点,顺序为S A P SL SR在这五种情况下的修复过程而已,仔细一想其实还好,没有很复杂。
