二叉树:红黑树 博客分类： Tree

    红黑树是一种自平衡的二叉树,它的查找,插入,删除操作时间复杂度皆为O(logN),不会出现普通二叉搜索树在最差情况时时间复杂度会变为O(N)的问题.
    红黑树必须遵循红黑规则,规则如下
    1、每个节点不是红就是黑。
    2、根总是黑的
    3、如果节点是红的，它的子节点必须全部是黑的
    4、从根到叶节点或者空子节点的每条路径，必须包含相同数量的黑色节点(黑色高度一致)    

    红黑树的插入操作比二叉搜索树复杂,为了保证黑红规则,要进行必要的变色和旋转.
  
    插入操作:
    查找例程遇到一个有两个红色子节点的黑色节点时,必须要把子节点变成黑色,把父节点变成红色(除非父节点为根节点).这样做是为了连接新的红色节点更容易.但有可违背规则3,当违背规则3时,X为违规节点(子节点违规),P为X的父节点,G为P的父节点则:
    如果X是G的外侧子孙节点:
        1、改变G的颜色
        2、改变P的颜色
        3、以G为顶点旋转,向X上升的方向(即X为左外侧子孙就右旋,为右外侧子孙就左旋)

    如果X是G的内侧子孙节点:
        1、改变G的颜色
        2、改变X的颜色
        3、以P为顶点旋转,向X上升的方向
        4、以G为顶点旋转,向X上升的方向

    在找到要插入的位置并插入节点后,会面临2种情况,即:插入节点的父节点是红色的(违背规则3);插入节点的父节点是黑色的(不违规).在父节点是黑色的情况下就不需要再做什么处理.而如果是红色的又分为两种情况:插入节点是外侧子孙节点;插入节点是内侧子孙节点.两者的处理方式与插入例程中的相同,即:
    如果P为红色,X是G的外侧子孙节点:
        1、改变G的颜色
        2、改变P的颜色
        3、以G为顶点旋转,向X上升的方向

    如果P为红色,X是G的内侧子孙节点:
        1、改变G的颜色
        2、改变X的颜色
        3、以P为顶点旋转,向X上升的方向
        4、以G为顶点旋转,向X上升的方向

    删除操作:
    说实话,本人愚钝,研究插入操作蛋已经碎了一地,好不容易才粘起来,删除操作则更加的复杂,于是还是尽量回避删除操作的好,比如设个作废标记神马的...

    查找操作:
    跟普通的二叉搜索树一样.


tree代码:

public class Tree {
    private Node root;
    
    /**
     * 插入数据
     * @param data 
     */
    public void insert(int data){
        Node node = new Node(data);
        
        if(this.root == null){
            this.setRoot(node);
            return;
        }
        
        Node current = this.root;
        
        while(true){
            //在变色后如果违反规则3,旋转平衡
            if(!this.changeColor(current)){
                this.rotate(current);
            }
            
            if(current.getData() > data){
                if(current.hasLeft()){
                    current = current.getLeft();
                }else{
                    current.setLeft(node);
                    break;
                }
            }else if(current.getData() < data){
                if(current.hasRihgt()){
                    current = current.getRight();
                }else{
                    current.setRight(node);
                    break;
                }
            }else{
                current.setValid(true);
                return;
            }
        }
        
        //插入后如果违反规则3,旋转平衡
        if(node.getParent().isRed()){
            this.rotate(node);
        }
    }
    
    /**
     * 查找数据
     * @param key 
     */
    public void find(int key){
        Node node = this.findNode(key);
        
        if(node != null && node.isValid()){
            System.out.println(node);
        }else{
            System.out.println("No find");
        }
    }
    
    /**
     * 删除节点
     * @param key 
     */
    public void remove(int key){
        Node node = this.findNode(key);
        
        if(node != null){
            node.setValid(false);
        }
    }
    
    /**
     * 树是否为空
     * @return 
     */
    public boolean isEmpty(){
        return this.root == null;
    }
    
    /**
     * 清空树
     */
    public void clear(){
        this.setRoot(null);
    }
    
    /**
     * 查找节点
     * @param i
     * @return 
     */
    private Node findNode(int key){
        Node current = this.root;
        
        while(current != null){
            if(current.getData() > key){
                current = current.getLeft();
            }else if(current.getData() < key){
                current = current.getRight();
            }else{
                return current;
            }
        }
        
        return null;
    }
    
    /**
     * 右旋转
     * @param top 顶点
     */
    private void rotateRight(Node top){
        if(top.hasLeft()){
            Node parent = top.getParent();
            Node left = top.getLeft();
            
            if(left.hasRihgt()){
                top.setLeft(left.getRight());
            }else{
                top.setLeft(null);
            }
            
            if(!top.isRoot()){
                if(top.isLeft()){
                    parent.setLeft(left);
                }else{
                    parent.setRight(left);
                }
            }else{
                this.setRoot(left);
            }
            
            left.setRight(top);
        }
    }
    
    /**
     * 左旋转
     * @param top 顶点 
     */
    private void rotateLeft(Node top){
        if(top.hasRihgt()){
            Node parent = top.getParent();
            Node right = top.getRight();
            
            if(right.hasLeft()){
                top.setRight(right.getLeft());
            }else{
                top.setRight(null);
            }
            
            if(!top.isRoot()){
                if(top.isLeft()){
                    parent.setLeft(right);
                }else{
                    parent.setRight(right);
                }
            }else{
                this.setRoot(right);
            }
            
            right.setLeft(top);
        }
    }
    
    /**
     * 如果一个节点的为黑色,并且它的两个子节点均为红色,将父节点变味红色,子节点变为黑色
     * @param node 父节点
     * @return 是否违反规则3,false为违反
     */
    private boolean changeColor(Node node){
        if(node.isBlack() && node.hasLeft() && node.hasRihgt() 
                && node.getLeft().isRed() && node.getRight().isRed()){
            
            node.getLeft().changeColor();
            node.getRight().changeColor();
            
            if(!node.isRoot()){
                node.changeColor();
                
                if(node.getParent().isRed()){
                    return false;
                }
            }
        }
        
        return true;
    }
    
    /**
     * 在违反规则3时做旋转操作平衡
     * @param node 违规节点
     */
    private void rotate(Node node){
        Node p = node.getParent();
        Node g = p.getParent();
        
        //当节点是外侧子孙节点的时候
        if(this.isRR(node) || this.isLL(node)){
            p.changeColor();
            g.changeColor();
            
            if(node.isRight()){
                this.rotateLeft(g);
            }else{
                this.rotateRight(g);
            }
        //当节点是内侧子孙节点的时候
        }else{
            g.changeColor();
            node.changeColor();
            
            if(node.isRight()){
                this.rotateLeft(p);
                this.rotateRight(g);
            }else{
                this.rotateRight(p);
                this.rotateLeft(g);
            }
        }
    }
    
    /**
     * 判断节点是否是父节点的右节点,并且父节点是否是祖父节点的右节点
     * @return 
     */
    private boolean isRR(Node node){
        return node.isRight() && node.getParent().isRight();
    }
    
    /**
     * 判断节点是否是父节点的左节点,并且父节点是否是祖父节点的左节点
     * @return 
     */
    private boolean isLL(Node node){
        return node.isLeft() && node.getParent().isLeft();
    }
    
    /**
     * 设置根节点
     * @param node 
     */
    private void setRoot(Node node){
        this.root = node;
        
        if(this.isEmpty()){
            return;
        }
        
        this.root.setParent(null);
        
        if(this.root.isRed()){
            this.root.changeColor();
        }
    }
}

node代码:

public class Node {
    
    private boolean color;//true是红,false是黑
    private Node parent;
    private Node left;
    private Node right;
    private int data;
    private boolean valid;

    public Node(int data) {
        this.data = data;
        this.color = true;
        this.valid = true;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;

        if (left != null) {
            left.setParent(this);
        }
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;

        if (right != null) {
            right.setParent(this);
        }
    }

    public void setValid(boolean flag){
        this.valid = flag;
    }
    
    public boolean isValid(){
        return this.valid;
    }
    
    public boolean hasLeft() {
        return this.left != null;
    }

    public boolean hasRihgt() {
        return this.right != null;
    }

    public boolean isRed() {
        return this.color;
    }

    public boolean isBlack() {
        return !this.color;
    }

    public boolean isRoot() {
        return this.parent == null;
    }
    
    public boolean isLeft(){
        if(this.isRoot()){
            return false;
        }
        
        return this.parent.getLeft() == this;
    }
    
    public boolean isRight(){
        if(this.isRoot()){
            return false;
        }
        
        return this.parent.getRight() == this;
    }

    public void changeColor() {
        this.color = !this.color;
    }
}