MutilMap的删除有BUG about gostl HOT 3 CLOSED

迭代删除有问题，删除之后指针变化了

from gostl.

迭代删除有问题，删除之后指针变化了

你的补丁在删除的时候避免使用了后继节点来迭代，但是我觉得可能下面的方法更好：
不要删除后继指针，而是把后继节点和要删除的节点位置交换（Relink），再把要删除的节点剥出来，这样后继节点不会因为删除而失效

func (rb *RbTree) Delete(n *Node) {
	erasedNode := n
	var fixNode, fixNodeParent, pNode *Node

	pNode = erasedNode
	if pNode.left == nil {
		fixNode = pNode.right
	} else if pNode.right == nil {
		fixNode = pNode.right
	} else {
		pNode = successor(n)
		fixNode = pNode.right
	}

	if pNode == erasedNode {
		fixNodeParent = erasedNode.parent
		if fixNode != nil {
			fixNode.parent = fixNodeParent // link up
		}
		if rb.root == erasedNode {
			rb.root = fixNode // link down from root
		} else if fixNodeParent.left == erasedNode {
			fixNodeParent.left = fixNode // link down to left
		} else {
			fixNodeParent.right = fixNode // link down to right
		}
	} else {
		//>> pNode is erasedNode's successor,  swap(pNode, erasedNode)
		erasedNode.left.parent = pNode // link left up
		pNode.left = erasedNode.left   // link successor down
		if pNode == erasedNode.right {
			fixNodeParent = pNode // successor is next to erased
		} else { // successor further down, link in place of erased
			fixNodeParent = pNode.parent // parent is successor's
			if fixNode != nil {
				fixNode.parent = fixNodeParent // link fix up
			}
			fixNodeParent.left = fixNode    // link fix down
			pNode.right = erasedNode.right  // link next down
			erasedNode.right.parent = pNode // right up
		}
		if rb.root == erasedNode {
			rb.root = pNode // link down from root
		} else if erasedNode.parent.left == erasedNode {
			erasedNode.parent.left = pNode // link down to left
		} else {
			erasedNode.parent.right = pNode // link down to right
		}
		pNode.parent = erasedNode.parent                              // link successor up
		pNode.color, erasedNode.color = erasedNode.color, pNode.color // recolor it
	}

	if erasedNode.color == BLACK { // erasing black link, must recolor/rebalance tree
		rb.rbDeleteFixup(fixNode, fixNodeParent)
	}
	rb.size--
}

from gostl.

迭代删除有问题，删除之后指针变化了

你的补丁在删除的时候避免使用了后继节点来迭代，但是我觉得可能下面的方法更好：
不要删除后继指针，而是把后继节点和要删除的节点位置交换（Relink），再把要删除的节点剥出来，这样后继节点不会因为删除而失效

func (rb *RbTree) Delete(n *Node) {
	erasedNode := n
	var fixNode, fixNodeParent, pNode *Node

	pNode = erasedNode
	if pNode.left == nil {
		fixNode = pNode.right
	} else if pNode.right == nil {
		fixNode = pNode.right
	} else {
		pNode = successor(n)
		fixNode = pNode.right
	}

	if pNode == erasedNode {
		fixNodeParent = erasedNode.parent
		if fixNode != nil {
			fixNode.parent = fixNodeParent // link up
		}
		if rb.root == erasedNode {
			rb.root = fixNode // link down from root
		} else if fixNodeParent.left == erasedNode {
			fixNodeParent.left = fixNode // link down to left
		} else {
			fixNodeParent.right = fixNode // link down to right
		}
	} else {
		//>> pNode is erasedNode's successor,  swap(pNode, erasedNode)
		erasedNode.left.parent = pNode // link left up
		pNode.left = erasedNode.left   // link successor down
		if pNode == erasedNode.right {
			fixNodeParent = pNode // successor is next to erased
		} else { // successor further down, link in place of erased
			fixNodeParent = pNode.parent // parent is successor's
			if fixNode != nil {
				fixNode.parent = fixNodeParent // link fix up
			}
			fixNodeParent.left = fixNode    // link fix down
			pNode.right = erasedNode.right  // link next down
			erasedNode.right.parent = pNode // right up
		}
		if rb.root == erasedNode {
			rb.root = pNode // link down from root
		} else if erasedNode.parent.left == erasedNode {
			erasedNode.parent.left = pNode // link down to left
		} else {
			erasedNode.parent.right = pNode // link down to right
		}
		pNode.parent = erasedNode.parent                              // link successor up
		pNode.color, erasedNode.color = erasedNode.color, pNode.color // recolor it
	}

	if erasedNode.color == BLACK { // erasing black link, must recolor/rebalance tree
		rb.rbDeleteFixup(fixNode, fixNodeParent)
	}
	rb.size--
}

嗯，这个好，有时间再改一下

from gostl.