我想明白这个问题了...这个是我模拟标准实现写的代码, 标准实现是先确定红黑树中存在该元素,然后删除; 我的则是直接删除,不管存不存在. 暂时还没有测试, 不过和标准代码实现基本一致

public void delete(int num) { if(root == null) return ; if(!isRed(root.left) && !isRed(root.right)) root.color = RED ; root = delete(root , num) ; if(root != null) root.color = BLACK ; } private Node delete(int key , Node node){ if(node == null) return null ; int cmp = node.key - key ; if(cmp > 0) //说明在他的左子树上 { //说明是一个2-节点, 需要从右子树上借一个给他 if(node.left != null && !isRed(node.left) && !isRed(node.left.left)) node = moveRedLeft(node) ; node.left = delete(node.left , key) ; } else //说明key在右子树上 { if(isRed(node.left))//说明该节点本身就是3-节点, 直接分一个给右子树即可 node = rotateRight(node) ; if(cmp == 0 && node.right == null) return null ; //如果右节点是一个2-节点, 那么就从左子树上借一个给他 if(node.right != null && !isRed(node.right) && !isRed(node.right.left)) node = moveRedRight(node) ; //cmp失效, 重新计算 cmp = node.key-key ; if(cmp == 0) { //和普通二叉树的删除相同, 将右子树的最小节点放在这个节点的位置 Node x = min(node.right) ; node.key = x.key ; node.value = x.value ; //将原来的最小节点删除 node.right = deleteMin(node.right) ; } else { node.right = delete(node.right , key) ; } } //维持红黑树的性质 return balance(node) ; }

删除的思路和删除最小值最大值的思路类似, 之前的思维局限于如何模拟2-3树的删除而导致没有认清楚他们之间的关系...

想问楼主一个问题
在delete中当要向右分支移动的过程中调用了moveRedRight的方法
请问 为什么moveRedRight方法中
node = rotateRight(node);
flipColors(node) ;
这两步执行之后为什么不需要进行左旋转呢
按理说此时的node.right.right的color是红色，node.right.left的color是黑色，（这一行的node是delete方法中传入的node）这时候不应该进行左旋吗？