一、红黑树原理

1、红黑树的insert(新的插入的节点默认为红色)

　　（1）如果插入是根节点，直接把节点涂为黑色，把节点设置为根节点

　　（2）如果插入的节点的父节点是黑色，无需任何处理

　　（3）需要修复的情况

　　　　情况1：当前节点的父节点为红色，叔叔节点为红色，解决办法：（将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，重新开始递归调整），根节点涂黑

　　　　情况2：当前节点的父节点为红色，叔叔节点为null或者黑色(或者的情况虽然在当前不存在，但是在情况1的递归条件下是存在的)，当前节点为父节点的右孩子，解决办法：需要先左旋，（左旋后，把父节点当成当前节点，当前节点的父节点涂黑，祖父节点涂红，后右旋），根节点涂黑（父节点为祖父左孩子的情况）

　　　　情况3：当前节点的父节点为红色，叔叔节点为null或者黑色(或者的情况虽然在当前不存在，但是在情况1的递归条件下是存在的)，当前节点为父节点的左孩子，解决办法：父节点涂黑，祖父节点涂红，直接右旋，根节点涂黑（父节点为祖父左孩子的情况）

2、红黑树的删除

　　（1）删除红色的叶子节点，直接删除

　　（2）删除的红色节点有左子树或者右子树的情况，这种情况不存在

　　（3）删除黑色的叶子结点

　　　　情况1：兄弟节点为红色，那父节点就必须为黑色，解决方法：把兄弟节点和父节点颜色对调，然后左旋，就变成了情况2，或者情况3

　　　　情况2：兄弟节点为黑色节点，远侄子节点为红色，解决办法：把兄弟节点与父节点颜色对调，然后左旋，把侄子节点颜色变黑，删除目的节点

　　　　情况3：兄弟节点为黑色节点，近侄子节点为红色，解决办法：把近侄子节点和该侄子的父节点进行右旋，然后他两颜色互换，然后就变成了情况2

　　　　情况4：兄弟节点为黑色，侄子节点也为黑色，这种情况不存在（但，这种情况在情况6的递归情况中是存在的，所以也得考虑）

　　　　情况5：兄弟节点为黑色，无侄子节点，父节点为红色，解决办法：把父节点变成黑色，兄弟节点变成红色，删除目的节点

　　　　情况6：兄弟节点为黑色，无侄子节点，父节点为黑色，解决办法：把兄弟节点变成红色，删除目的节点，接着把当前节点指向父节点，然后按照父节点为黑色叶子节点的情况进行递归调整

　　（4）删除的黑色节点有左子树或者右子树的情况，当然这个时候它的左子树或者右子树节点只能是红色不能是黑色，处理方法简单：即用黑色节点的孩子替换黑色节点，并将替换后的节点染成黑色。

3、红黑树三旋转（insert一旋转，delete二旋转）

其中，insert一旋转，向插入节点子树的对立方向旋转（以祖父为中心）（ 祖父节点和父节点颜色互换）

delete的二旋转，两次都是向删除节点的同一方向旋转（两次都是以父亲为中心）（第一次旋转：父节点和兄弟节点颜色互换）（第二次旋转：父节点和兄弟节点颜色互换，侄子节点涂黑）

二、二叉排序树中需要旋转的场景描述（旋转需要有三个点，当然第三个点也可以是null）

左旋或者右旋的三要素：

1、包含根节点的变更

2、除根节点外，包含三个点的操作

3、

三、红黑树的代码

package main;import java.util.LinkedList;import java.util.Queue;public class RBTree
     
      > {    private static final boolean RED = false;    private static final boolean BLACK = true;    private RBNode
      
        root = null;    public class RBNode
       
        {        private T key;        private boolean color;        private RBNode
        
          parent;        private RBNode
         
           left;        private RBNode
          
            right; public RBNode(T key) { this.key = key; this.color = RED; this.parent = null; this.left = null; this.right = null; } } public static void main(String[] args) { RBTree
           
             rbree = new RBTree<>(); rbree.insert(1); rbree.insert(9); rbree.insert(5); rbree.insert(8); rbree.insert(2); rbree.insert(4); rbree.insert(7); rbree.insert(6); rbree.insert(3); rbree.insert(10); rbree.insert(11); rbree.insert(12); rbree.delete(5); rbree.delete(4); rbree.delete(10); rbree.delete(9); rbree.show(); } //红黑树的展示 public void show() { int h = height(this.root); Queue
            
             
              > queue = new LinkedList<>(); queue.add(this.root); RBNode
              
                tempNode = null; for(int i=1;i<=h;++i) { for(int j=0;j
               
                 rootNode) { if(rootNode==null) { return 0; }else { return height(rootNode.left)>height(rootNode.right)?(height(rootNode.left)+1):(height(rootNode.right)+1); } } //节点的插入 public void insert(T key) { RBNode
                
                  newNode = new RBNode<>(key); RBNode
                 
                   tempNode = this.root; RBNode
                  
                    preNode = this.root; while(tempNode!=null) { preNode = tempNode; if(tempNode.key.compareTo(key)==0) { return; }else if(tempNode.key.compareTo(key)<0){ tempNode = tempNode.right; }else { tempNode = tempNode.left; } } if(preNode==null) { this.root = newNode; }else if(preNode.key.compareTo(key)<0) { preNode.right = newNode; newNode.parent = preNode; }else{ preNode.left = newNode; newNode.parent = preNode; } //节点插入后需要进行颜色和位置的调整 fixupInsert(newNode); } //节点插入的调整 public void fixupInsert(RBNode
                   
                     newNode) { if(newNode.parent==null||newNode.parent.color == BLACK) { //父节点没有或者父节点为黑色时不做任何处理 }else { //父节点 RBNode
                    
                      parentNode = newNode.parent; //祖父节点 RBNode
                     
                       grandParentNode = parentNode.parent; //叔叔节点 RBNode
                      
                        uncleNode = null; if(grandParentNode.left==parentNode) { uncleNode = grandParentNode.right; }else { uncleNode = grandParentNode.left; } //叔叔节点为黑色(这里的条件在递归中作用很大) if(uncleNode==null||uncleNode.color) { if(grandParentNode.left==parentNode&&parentNode.left==newNode) { parentNode.color = BLACK; grandParentNode.color = RED; rightRotate(grandParentNode); }else if(grandParentNode.left==parentNode&&parentNode.right==newNode){ leftRotate(parentNode); newNode.color = BLACK; grandParentNode.color = RED; rightRotate(grandParentNode); }else if(grandParentNode.right==parentNode&&parentNode.left==newNode){ rightRotate(parentNode); newNode.color = BLACK; grandParentNode.color = RED; leftRotate(grandParentNode); }else { parentNode.color = BLACK; grandParentNode.color = RED; leftRotate(grandParentNode); } }else { //叔叔节点位红色 parentNode.color = BLACK; uncleNode.color = BLACK; grandParentNode.color = RED; fixupInsert(grandParentNode); } } this.root.color = BLACK;//根节点设为黑色 } public void delete(T key) { RBNode
                       
                         tempNode = this.root; RBNode
                        
                          tempLeftNode = null; //寻找删除的节点 while(tempNode!=null) { if(tempNode.key.compareTo(key)==0) { if(tempNode.left!=null&&tempNode.right!=null) { tempLeftNode = tempNode.left; while(tempLeftNode.right!=null) { tempLeftNode = tempLeftNode.right; } tempNode.key = tempLeftNode.key; tempNode = tempLeftNode; } break; }else if(tempNode.key.compareTo(key)<0) { tempNode = tempNode.right; }else { tempNode = tempNode.left; } } //需要删除的节点为tempNode if(tempNode!=null) { if(tempNode.left!=null) { //删除节点有红色的左孩子节点 tempNode.left.color = BLACK; if(tempNode.parent==null) { this.root = tempNode.left; tempNode.left.parent = null; }else { if(tempNode.parent.left==tempNode) { tempNode.parent.left = tempNode.left; tempNode.left.parent = tempNode.parent; }else { tempNode.parent.right = tempNode.left; tempNode.left.parent = tempNode.parent; } } }else if(tempNode.right!=null) { //删除节点有红色的右孩子节点 tempNode.right.color = BLACK; if(tempNode.parent==null) { this.root = tempNode.right; tempNode.right.parent = null; }else { if(tempNode.parent.left==tempNode) { tempNode.parent.left = tempNode.right; tempNode.right.parent = tempNode.parent; }else { tempNode.parent.right = tempNode.right; tempNode.right.parent = tempNode.parent; } } }else if(!tempNode.color){ //删除红色叶子结点 if(tempNode.parent==null) { this.root = null; }else { if(tempNode.parent.left==tempNode) { tempNode.parent.left = null; }else { tempNode.parent.right = null; } } }else { //删除黑色叶子结点 fixupDelete(tempNode);//先调整，后删除 if(tempNode.parent==null) { this.root = null; }else { if(tempNode.parent.left==tempNode) { tempNode.parent.left = null; }else { tempNode.parent.right = null; } } } } } public void fixupDelete(RBNode
                         
                           tempNode) { RBNode
                          
                            parentNode = null; if(tempNode.parent==null) { return; }else { parentNode = tempNode.parent; } RBNode
                           
                             uncleNode = null; if(parentNode.left==tempNode) { uncleNode = parentNode.right; }else { uncleNode = parentNode.left; } //删除节点的兄弟节点为红色的情况 if(parentNode.color==BLACK&&uncleNode.color==RED) { parentNode.color = RED; uncleNode.color = BLACK; if(parentNode.left==uncleNode) { rightRotate(parentNode); }else { leftRotate(parentNode); } if(parentNode.left==tempNode) { uncleNode = parentNode.right; }else { uncleNode = parentNode.left; } } //删除节点的兄弟节点为黑色的情况 if(parentNode.right==uncleNode) { if(uncleNode.right!=null&&!uncleNode.right.color) { //远侄子节点为红色 uncleNode.color = parentNode.color; parentNode.color = BLACK; uncleNode.right.color = BLACK; leftRotate(parentNode); }else if(uncleNode.left!=null&&!uncleNode.left.color){ //近侄子节点为红色 uncleNode.left.color = parentNode.color; parentNode.color = BLACK; rightRotate(uncleNode); leftRotate(parentNode); }else if(parentNode.color) { //父节点为黑色，两个侄子节点为null或者在低轨情况下可能都为黑色 uncleNode.color = RED; fixupDelete(parentNode); }else { //父节点为红色，两个侄子节点为null或者在低轨情况下可能都为黑色 uncleNode.color = RED; parentNode.color = BLACK; } }else { if(uncleNode.left!=null&&!uncleNode.left.color) { //远侄子节点为红色 uncleNode.color = parentNode.color; parentNode.color = BLACK; uncleNode.left.color = BLACK; rightRotate(parentNode); }else if(uncleNode.right!=null&&!uncleNode.right.color) { //近侄子节点为红色 uncleNode.right.color = parentNode.color; parentNode.color= BLACK; leftRotate(uncleNode); rightRotate(parentNode); }else if(parentNode.color) { //父节点为黑色，两个侄子节点为null或者在低轨情况下可能都为黑色 uncleNode.color = RED; fixupDelete(parentNode); }else { //父节点为红色，两个侄子节点为null或者在低轨情况下可能都为黑色 uncleNode.color = RED; parentNode.color = BLACK; } } this.root.color = BLACK; } //以参数节点为中心进行左旋 public void leftRotate(RBNode
                            
                              rotateNode) { RBNode
                             
                               rightNode = rotateNode.right; //对承接节点的处理 if(rotateNode.parent==null) { rightNode.parent = null; this.root = rightNode; }else { rightNode.parent = rotateNode.parent; if(rotateNode.parent.left==rotateNode) { rotateNode.parent.left = rightNode; }else { rotateNode.parent.right = rightNode; } } //对支节点的处理 rotateNode.right = rightNode.left; if(rightNode.left!=null) { rightNode.left.parent = rotateNode; } //对当下节点的处理 rightNode.left = rotateNode; rotateNode.parent = rightNode; } //以参数节点为中心进行右旋 public void rightRotate(RBNode
                              
                                rotateNode) { RBNode
                               
                                 leftNode = rotateNode.left; //对承接节点的处理 if(rotateNode.parent==null) { leftNode.parent = null; this.root = leftNode; }else { leftNode.parent = rotateNode.parent; if(rotateNode.parent.left==rotateNode) { rotateNode.parent.left = leftNode; }else { rotateNode.parent.right = leftNode; } } //对支节点的处理 rotateNode.left = leftNode.right; if(leftNode.right!=null) { leftNode.right.parent = rotateNode; } //对当下节点的处理 leftNode.right = rotateNode; rotateNode.parent = leftNode; }}
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

参考文献

红黑树的理解：