I want to understand this problem... This is the code I wrote to simulate the standard implementation. The standard implementation is to first confirm that the element exists in the red-black tree and then delete it; mine is to delete it directly, regardless of whether it exists or not. For the time being. There is no test, but it is basically the same as the standard code implementation

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) ; }

The idea of deletion is similar to the idea of deleting the minimum and maximum values. The previous thinking was limited to how to simulate the deletion of 2-3 trees and did not recognize the relationship between them clearly...

I want to ask the poster a question
In the process of moving to the right branch in delete, the moveRedRight method is called
Excuse me why in the moveRedRight method
node = rotateRight(node);
flipColors(node);
After these two steps are executed Why is there no need to perform left rotation? It stands to reason that the color of node.right.right at this time is red, and the color of node.right.left is black. (The node in this row is the node passed in in the delete method) At this time, not Should a left-hand rotation be performed?