我想明白這個問題了...這個是我模擬標準實現寫的代碼, 標準實現是先確定紅黑樹中存在該元素,然後刪除; 我的則是直接刪除,不管存不存在. 暫時還沒有測試, 不過和標準程式碼實現基本一致

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）這時候不應該進行左旋嗎？