红黑树的插入删除完整版以及java版本

本文主要是介绍红黑树的插入删除完整版以及java版本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原理 请看算法导论的红黑树的讲解，我是按照图的编写实现java的版本

package rbtree;

public class RBTree {  
    
    private final Node NIL = new Node(null,null,null,Color.BLACK,-1);  
    private Node root;  
      
    public RBTree() {  
        root = NIL;  
    }  
      
    public RBTree(Node  root) {  
        this.root = root;  
    }  
      
    public void insert(int data){
    rbInsert(new Node(data));
    }
    //插入节点  
    private void rbInsert(Node node) {  
          
        Node previous = NIL;  
        Node temp = root;  
          
        while (temp != NIL) {  
            previous = temp;  
            if (temp.getValue() < node.getValue()) {  
                temp = temp.getRight();  
            } else {  
                temp = temp.getLeft();  
            }  
        }  
        node.setParent(previous);  
          
        if (previous == NIL) {  
            root = node;  
            root.setParent(NIL);  
        } else  if (previous.getValue() > node.getValue()) {  
            previous.setLeft(node);  
        } else {  
            previous.setRight(node);  
        }  
          
        node.setLeft(NIL);  
        node.setRight(NIL);  
        node.setColor(Color.RED);  
        rb_Insert_Fixup(node);  
    }  
      
    //插入节点后的调整  
    private void rb_Insert_Fixup(Node node) {  
      
        while (node.getParent().getColor() == Color.RED) {  
              
            if (node.getParent() == node.getParent().getParent().getLeft()) {  
                  
                Node rightNuncle = node.getParent().getParent().getRight();  
                  
                if (rightNuncle.getColor() == Color.RED) {        
                    rightNuncle.setColor(Color.BLACK);  
                    node.getParent().setColor(Color.BLACK);  
                    node.getParent().getParent().setColor(Color.RED);  
                    node = node.getParent().getParent();  
                                          
                } else if(rightNuncle.getColor() == Color.BLACK){
                if(node == node.getParent().getRight()) {    
                         node = node.getParent();  
                         leftRotate(node);  
                     }
                node.getParent().setColor(Color.BLACK);  
                     node.getParent().getParent().setColor(Color.RED);  
                     rightRotate(node.getParent().getParent());  
                }
            } else {  
                  
                Node leftNuncle = node.getParent().getParent().getLeft();  
                  
                if (leftNuncle.getColor() == Color.RED) {       
                    leftNuncle.setColor(Color.BLACK);  
                    node.getParent().setColor(Color.BLACK);  
                    node.getParent().getParent().setColor(Color.RED);  
                    node = node.getParent().getParent();  
                  
                } else if(leftNuncle.getColor() == Color.BLACK){
                if(node == node.getParent().getLeft()) { 
                    node = node.getParent();  
                    rightRotate(node);  
                   }                                        
                    node.getParent().setColor(Color.BLACK);  
                    node.getParent().getParent().setColor(Color.RED);  
                    leftRotate(node.getParent().getParent());  
                }  
                                  
            }  
        }  
        root.setColor(Color.BLACK);  
    }  
      
    
    //将v子树代替u子树
   private void transplant(Node u,Node v){
  if(u.getParent()==NIL){
  this.root=v;
  }else if(u.getParent().getLeft()==u){
  u.getParent().setLeft(v);
  }else{
  u.getParent().setRight(v);
  }
  if(v!=NIL){
  v.setParent(u.getParent());
  }
   }
      
   private Node Minmum(Node node){
  while(node.getLeft()!=NIL){
  node=node.getLeft();
  }
  return node;
   }
   
   private Node successor(Node node){
  if(node.getRight()!=NIL){
  return this.Minmum(node);
  }
  Node parent=node.getParent();
  while(parent!=NIL&&parent.getRight()==node){
  node=parent;
  parent=parent.getParent();
  }
  return parent;
   }
   
   public void deleteNode(int data){
  Node node = search(data);
  if(node==null)return;
  Node x=NIL;
  Node y=node;
  Color original_color=y.getColor();
  if(node.getLeft()==NIL){
  x=node.getRight();
  this.transplant(node, node.getRight());
  }else if(node.getRight()==NIL){
  x=node.getLeft();
  this.transplant(node, node.getLeft());
  }else{
  y=this.successor(node);
  System.out.println(y);
  original_color=y.getColor();
  x=y.getRight();
  if(y.getParent()==node){
  x.setParent(y);
  }else{
  this.transplant(y, y.getRight());
  y.setRight(node.getRight());
  y.getRight().setParent(y);
  }
  this.transplant(node, y);
  y.setLeft(node.getLeft());
  y.getLeft().setParent(y);
  y.setColor(node.getColor());
  if(original_color==Color.BLACK){
  delete_fixup(x);
  }
  }
   }
   
   
      private void delete_fixup(Node x) {
     while(x!=NIL&&x.getColor()==Color.BLACK){
     if(x==x.getParent().getLeft()){
     Node w=x.getParent().getRight();
     if(w.getColor()==Color.RED){
     w.setColor(Color.BLACK);
     x.getParent().setColor(Color.RED);
     this.leftRotate(x.getParent());
     w=x.getParent().getRight();
     }else if(w.getColor()==Color.BLACK){
    if(w.getLeft().getColor()==Color.BLACK&&w.getRight().getColor()==Color.BLACK){
    w.setColor(Color.RED);
    x=x.getParent();
    }else if(w.getRight().getColor()==Color.BLACK){
    w.getLeft().setColor(Color.BLACK);
    w.setColor(Color.RED);
    this.rightRotate(w);
    w=x.getParent().getRight();
    }
    w.setColor(x.getParent().getColor());
    x.getParent().setColor(Color.BLACK);
    w.getRight().setColor(Color.BLACK);
    this.leftRotate(x.getParent());
    x=NIL;
     }
     }else{
    Node leftw=x.getParent().getLeft();
    if(leftw.getColor()==Color.RED){
    x.getParent().setColor(Color.RED);
    leftw.setColor(Color.BLACK);
    this.rightRotate(x.getParent());
    leftw=x.getParent().getLeft();
    }else if(leftw.getColor()==Color.BLACK){
    if(leftw.getLeft().getColor()==Color.BLACK&&leftw.getRight().getColor()==Color.BLACK){
    leftw.setColor(Color.RED);
    x=x.getParent();
    }else if(leftw.getLeft().getColor()==Color.BLACK){
    leftw.getRight().setColor(Color.BLACK);
    leftw.setColor(Color.RED);
    this.leftRotate(leftw);
    leftw=x.getParent().getLeft();
    }
    leftw.setColor(x.getParent().getColor());
    x.getParent().setColor(Color.BLACK);
    leftw.getLeft().setColor(Color.BLACK);
    this.rightRotate(x.getParent());
    x=NIL;
    }
     }
     }
     x.setColor(Color.BLACK);
      }
      
      
    //查找节点  
    public Node search(int data) {  
        Node temp = root;  
          
        while (temp != NIL) {  
            if (temp.getValue() == data) {  
                return temp;  
            } else  if (data < temp.getValue()) {  
                temp = temp.getLeft();  
            } else {  
                temp = temp.getRight();  
            }  
        }  
        return null;  
    }  
      
      
      
      
    //左转函数  
    private void leftRotate(Node node) {  
          
        Node rightNode = node.getRight();  
          
        node.setRight(rightNode.getLeft());  
        if (rightNode.getLeft() != NIL) {  
            rightNode.getLeft().setParent(node);  
        }  
        rightNode.setParent(node.getParent());  
          
        if (node.getParent() == NIL) {  
            root=rightNode;  
        } else if (node == node.getParent().getLeft()) {  
            node.getParent().setLeft(rightNode);  
        } else {  
            node.getParent().setRight(rightNode);  
        }  
          
        rightNode.setLeft(node);
        rightNode.getLeft().setParent(rightNode);
    }  
      
    //右转函数  
    private void rightRotate(Node node) {  
          
        Node leftNode = node.getLeft();  
        node.setLeft(leftNode.getRight());  
          
        if (leftNode.getRight() != NIL) {  
            leftNode.getRight().setParent(node);  
        }  
          
        leftNode.setParent(node.getParent());  
          
        if (node.getParent() == NIL) {  
            root = leftNode;  
        } else if (node == node.getParent().getLeft()) {  
            node.getParent().setLeft(leftNode);  
        } else {  
            node.getParent().setRight(leftNode);  
        }  
          
        leftNode.setRight(node);  
        leftNode.getRight().setParent(leftNode);
    }  
      
    //中序遍历红黑树  
    public void printTree() {  
        inOrderTraverse(root);  
    }  
      
    private void inOrderTraverse(Node node) {  
          
        if (node != NIL) {  
            inOrderTraverse(node.getLeft());  
            System.out.println(" 节点："+node.getValue() + "的颜色为：" + node.getColor());  
            inOrderTraverse(node.getRight());  
        }  
          
    }  
      
      
    public Node getNIL() {  
        return NIL;  
    }  
  
}  
  
  
  
class Node {  
    private Node left;  
    private Node right;  
    private Node parent;  
    private Color color;  
    private int value;  
    public Node(Node left, Node right, Node parent, Color color, int value) {  
        super();  
        this.left = left;  
        this.right = right;  
        this.parent = parent;  
        this.color = color;  
        this.value = value;  
    }  
      
    public Node() {  
    }  
      
    public Node(int value) {  
        this(null,null,null,null,value);  
    }  
  
    public Node getLeft() {  
        return left;  
    }  
  
    public void setLeft(Node left) {  
        this.left = left;  
    }  
  
    public Node getRight() {  
        return right;  
    }  
  
    public void setRight(Node right) {  
        this.right = right;  
    }  
  
    public Node getParent() {  
        return parent;  
    }  
  
    public void setParent(Node parent) {  
        this.parent = parent;  
    }  
  
    public Color getColor() {  
        return color;  
    }  
  
    public void setColor(Color color) {  
        this.color = color;  
    }  
  
    public int getValue() {  
        return value;  
    }  
  
    public void setValue(int value) {  
        this.value = value;  
    }  
      
}  
  
enum Color {  
    RED,BLACK  
}  

这篇关于红黑树的插入删除完整版以及java版本的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---