// Delete to delete the node with the key from the tree
Delete to delete the node with the key from the tree
// Delete to delete the node with the key from the tree
func (rb *RBTree) Delete(key int) error {
	node := rb.searchNode(key)
	if node == rb.nil() {
		return fmt.Errorf("key %v does not exist", key)
	}
	y := node
	yOriginalColor := node.color 
	x := rb.nil()                
	if node.leftChild == rb.nil() && node.rightChild == rb.nil() { 
		if yOriginalColor == rbBlack {
			x = rb.doubleBlackNil 
		}
		rb.transplant(node, x)
	} else if node.leftChild == rb.nil() { 
		x = node.rightChild
		rb.transplant(node, node.rightChild)
	} else if node.rightChild == rb.nil() { 
		x = node.leftChild
		rb.transplant(node, node.leftChild)
	} else { 
		y = rb.minimumNode(node.rightChild)
		yOriginalColor = y.color
		x = y.rightChild
		if yOriginalColor == rbBlack && x == rb.nil() {
			x = rb.doubleBlackNil 
			y.rightChild = x
			x.parent = y
		}
		if y != node.rightChild { 
			rb.transplant(y, y.rightChild)
			y.rightChild = node.rightChild
			y.rightChild.parent = y
		}
		rb.transplant(node, y)
		y.leftChild = node.leftChild
		y.leftChild.parent = y
		y.color = node.color
	}
	if yOriginalColor == rbBlack { 
		rb.deleteFixup(x)        
		rb.clearDoubleBlackNil() 
	}
	rb.count--
	return nil
}
func ( rb * RBTree ) Delete ( key int ) error { node := rb . searchNode ( key ) if node == rb . nil ( ) { return fmt . Errorf ( " " , key ) } y := node yOriginalColor := node . color x := rb . nil ( ) if node . leftChild == rb . nil ( ) && node . rightChild == rb . nil ( ) { if yOriginalColor == rbBlack { x = rb . doubleBlackNil } rb . transplant ( node , x ) } else if node . leftChild == rb . nil ( ) { x = node . rightChild rb . transplant ( node , node . rightChild ) } else if node . rightChild == rb . nil ( ) { x = node . leftChild rb . transplant ( node , node . leftChild ) } else { y = rb . minimumNode ( node . rightChild ) yOriginalColor = y . color x = y . rightChild if yOriginalColor == rbBlack && x == rb . nil ( ) { x = rb . doubleBlackNil y . rightChild = x x . parent = y } if y != node . rightChild { rb . transplant ( y , y . rightChild ) y . rightChild = node . rightChild y . rightChild . parent = y } rb . transplant ( node , y ) y . leftChild = node . leftChild y . leftChild . parent = y y . color = node . color } if yOriginalColor == rbBlack { rb . deleteFixup ( x ) rb . clearDoubleBlackNil ( ) } rb . count -- return nil }
Delete to delete the node with the key from the tree
Delete to delete the node with the key from the tree
// 参考 "红黑树-Delete-我的推导" 笔记中的 x 和 yOrignalColor 的解释 // the node's color which will affect red-black properties if delete // the node which may have double-black, so that we need to maintain red-black properties start from here // Below process is very similar with `Delete()` of binary search tree. // Refer to "Introduction to Algorithms - Third Edition" ch12.3 // and "Introduction to Algorithms - Third Edition" ch13.4 for more details if necessary. // A better introduction: https://segmentfault.com/a/1190000012115424 //no child // remember parent of x // only have a rightChild // only have a leftChild // have both leftChild and rightChild // find successor of current node // The successor of node MUST be in right-sub-tree of current node, // and it will not have a leftChild. // remember parent of x // same condition of binary search tree `Delete()` // y in node's subTree but not the rightChild of node // if yOriginalColor is RED, will not affect red-black tree properties // the most complex part of red-black tree deletion // if yOriginalColor == rbRed, this doubleBlackNil will be changed