树——平衡二叉树插入和查找的JAVA实现(2):增加删除方法

浏览数：33 / 时间：2015年06月08日
package com.tomsnail.data.tree;
/**
 * AVL二叉平衡树
 * @author tomsnail
 * @date 2015年3月30日 下午4:35:50
 */
public class AVLTree {
    
    /**
     * 根节点
     * @author tomsnail
     * @date 2015年3月30日 下午4:36:54
     */
    private AVLNode rootNode;
    
    private String bulidType = "";
    
    /**
     * 增加一个节点
     * @author tomsnail
     * @date 2015年3月30日 下午4:36:08
     */
    public void add(int value){
        AVLNode subNode = null;
        if(rootNode==null){
            subNode  = new AVLNode(value);
            rootNode = subNode;
        }else{            
            subNode = addNode(rootNode,value);
        }
        reBuild(subNode);

    }
    
    private AVLNode addNode(AVLNode node,int value){
        AVLNode subNode = null;
        if(node.getValue()>value){
            if(node.getLeftNode()==null){
                subNode = new AVLNode(value);
                node.setLeftNode(subNode);
            }else{
                subNode = addNode(node.getLeftNode(), value);
            }
        }
        if(node.getValue()<value){
            if(node.getRightNode()==null){
                subNode = new AVLNode(value);
                node.setRightNode(subNode);
            }else{
                subNode = addNode(node.getRightNode(),value);
            }
        }
        return subNode;
    }
    /**
     * 重平衡树
     * @author tomsnail
     * @date 2015年3月30日 下午5:42:00
     */
    private void reBuild(AVLNode node){
        if(node!=null){
            AVLNode tempRootNode = findTempRootNode(node);
            if(tempRootNode!=null){
                if(bulidType.equals("ll")){
                    Lrotate(node,tempRootNode);
                }else if(bulidType.equals("rr")){
                    Rrotate(node,tempRootNode);
                }else if(bulidType.equals("lr")){
                    Rrotate(node,tempRootNode.getLeftNode());
                    Lrotate(node,tempRootNode);
                }else if(bulidType.equals("rl")){
                    Lrotate(node,tempRootNode.getRightNode());
                    Rrotate(node,tempRootNode);
                }
                reBuild(tempRootNode);
            }
        }
    }
    /**
     * 右旋
     * @author tomsnail
     * @date 2015年3月30日 下午9:23:28
     */
    private void Rrotate(AVLNode node,AVLNode tempRootNode){
        AVLNode rotateNode = tempRootNode.getRightNode();//旋转节点
        AVLNode rootNode = tempRootNode.getRootNode();//主根节点
        String type = "";
        if(rootNode!=null){
            if(rootNode.getLeftNode()==tempRootNode){
                type="l";
            }else{
                type="r";
            }
        }
        AVLNode adjustNode = rotateNode.getLeftNode();//调整节点
        rotateNode.setLeftNode(tempRootNode);
        tempRootNode.setRightNode(null);
        if(adjustNode!=null){
            tempRootNode.setRightNode(adjustNode);
        }
        if(rootNode==null){
            rotateNode.setRootNode(null);
            this.rootNode = rotateNode;
        }
        if(type.equals("r")){
            rootNode.setRightNode(rotateNode);
        }else if(type.equals("l")){
            rootNode.setLeftNode(rotateNode);
        }
    }
    /**
     * 左旋
     * @author tomsnail
     * @date 2015年3月30日 下午9:23:28
     */
    private void Lrotate(AVLNode node,AVLNode tempRootNode){
        AVLNode rotateNode = tempRootNode.getLeftNode();//旋转节点
        AVLNode rootNode = tempRootNode.getRootNode();//主根节点
        String type = "";
        if(rootNode!=null){//子树类型
            if(rootNode.getLeftNode()==tempRootNode){
                type="l";
            }else{
                type="r";
            }
        }
        AVLNode adjustNode = rotateNode.getRightNode();//调整节点
        rotateNode.setRightNode(tempRootNode);
        tempRootNode.setLeftNode(null);
        if(adjustNode!=null){
            tempRootNode.setLeftNode(adjustNode);
        }
        if(rootNode==null){
            rotateNode.setRootNode(null);
            this.rootNode = rotateNode;
        }
        if(type.equals("r")){
            rootNode.setRightNode(rotateNode);
        }else if(type.equals("l")){
            rootNode.setLeftNode(rotateNode);
        }
    }
    
    /**
     * 查找最小不平衡的根节点
     * @author tomsnail
     * @date 2015年3月30日 下午5:40:55
     */
    private AVLNode findTempRootNode(AVLNode node){
        AVLNode noB = getNoBalance(node);
        if(noB==null){
            return null;
        }
        if(isTypeLL(noB)){
            bulidType = "ll";
        }else if(isTypeRR(noB)){
            bulidType = "rr";
        }else if(isTypeLR(noB)){
            bulidType = "lr";
        }else if(isTypeRL(noB)){
            bulidType = "rl";
        }
        return noB;
    }
    //左左类型
    private boolean isTypeLL(AVLNode noB){
        try {
            if(noB.getRightNode()==null&&noB.getLeftNode().getRightNode()==null&&!noB.getLeftNode().getLeftNode().hasSubNode()){
                return true;
            }
            if(noB.getRightNode()!=null&&noB.getLeftNode().getRightNode()!=null&&noB.getLeftNode().getLeftNode().hasSubNode()){
                return true;
            }
        } catch (Exception e) {
        }
        return false;
    }
    //右右类型
    private boolean isTypeRR(AVLNode noB){
        try {
            if(noB.getLeftNode()==null&&noB.getRightNode().getLeftNode()==null&&!noB.getRightNode().getRightNode().hasSubNode()){
                return true;
            }
            if(noB.getLeftNode()!=null&&noB.getRightNode().getLeftNode()!=null&&noB.getRightNode().getRightNode().hasSubNode()){
                return true;
            }
        } catch (Exception e) {
        }
        return false;
    }
    //左右类型
    private boolean isTypeLR(AVLNode noB){
        try {
            if(noB.getRightNode()==null&&noB.getLeftNode().getLeftNode()==null&&!noB.getLeftNode().getRightNode().hasSubNode()){
                return true;
            }
            if(noB.getRightNode()!=null&&noB.getLeftNode().getLeftNode()!=null&&noB.getLeftNode().getRightNode().hasSubNode()){
                return true;
            }
        } catch (Exception e) {
        }
        return false;
    }
    //右左类型
    private boolean isTypeRL(AVLNode noB){
        try {
            if(noB.getLeftNode()==null&&noB.getRightNode().getRightNode()==null&&!noB.getRightNode().getLeftNode().hasSubNode()){
                return true;
            }
            if(noB.getLeftNode()!=null&&noB.getRightNode().getRightNode()!=null&&noB.getRightNode().getLeftNode().hasSubNode()){
                return true;
            }
        } catch (Exception e) {
        }
        return false;
    }
    
    //获取不平衡的根节点
    private AVLNode getNoBalance(AVLNode node){
        if(node.getRootNode()==null){
            return null;
        }else{
            if(!isBalance(node.getRootNode())){
                return node.getRootNode();
            }else{
                return getNoBalance(node.getRootNode());
            }
        }
    }
    
    /**
     * 删除一个节点
     * @author tomsnail
     * @date 2015年3月30日 下午4:36:20
     */
    public void delete(int value){
        AVLNode wantDeleteNode = find(value);
        if(wantDeleteNode==null){
            return;
        }else{
            if(wantDeleteNode.getLeftNode()==null&&wantDeleteNode.getRightNode()==null){//删除节点没有左右子树
                AVLNode rootNode = wantDeleteNode.getRootNode();
                if(rootNode!=null){
                    if(rootNode.getLeftNode()==wantDeleteNode){
                        rootNode.setLeftNode(null);
                    }else{
                        rootNode.setRightNode(null);
                    }
                    reBuild(rootNode);
                }
            }else if(wantDeleteNode.getRightNode()==null){//删除节点只有左子树
                AVLNode rootNode = wantDeleteNode.getRootNode();
                if(rootNode!=null){
                    if(rootNode.getLeftNode()==wantDeleteNode){
                        rootNode.setLeftNode(wantDeleteNode.getLeftNode());
                    }else{
                        rootNode.setRightNode(wantDeleteNode.getLeftNode());
                    }
                    wantDeleteNode.setLeftNode(null);
                    reBuild(rootNode);
                }
            }else if(wantDeleteNode.getLeftNode()==null){//删除节点只有右子树
                AVLNode rootNode = wantDeleteNode.getRootNode();
                if(rootNode!=null){
                    if(rootNode.getRightNode()==wantDeleteNode){
                        rootNode.setLeftNode(wantDeleteNode.getRightNode());
                    }else{
                        rootNode.setRightNode(wantDeleteNode.getRightNode());
                    }
                    wantDeleteNode.setRightNode(null);
                    reBuild(rootNode);
                }
            }else {//删除节点有左右子树
                AVLNode maxNode = getLeftMaxValueNode(wantDeleteNode.getLeftNode());//找到节点左子树最大值的节点
                AVLNode rootMaxNode = maxNode.getRootNode();//获得该节点的父节点
                if(maxNode.getLeftNode()!=null){//如果最大值节点有左子树，则将最大值节点的父节点的右子树设为它
                    rootMaxNode.setRightNode(maxNode.getLeftNode());
                    maxNode.setLeftNode(null);
                }else{//否则置空
                    rootMaxNode.setRightNode(null);
                }
                wantDeleteNode.setValue(maxNode.getValue());//把要删除节点的值用最大值节点的值替换
                maxNode=null;//引用置空
                reBuild(rootMaxNode);
            }
        }
    }
    //得到左子树最大值节点
    private AVLNode getLeftMaxValueNode(AVLNode node){
        if(node!=null&&node.getRightNode()!=null){
            return getLeftMaxValueNode(node.getRightNode());
        }else{
            return node;
        }
    }
    
    /**
     * 查找一个节点
     * @author tomsnail
     * @date 2015年3月30日 下午4:36:35
     */
    public AVLNode find(int value){
        return findWith2(rootNode,value);
    }
    private AVLNode findWith2(AVLNode node,int value){
        if(node==null){
            return null;
        }
        System.out.println(node.getValue());
        if(node.getValue()>value){
            return findWith2(node.getLeftNode(),value);
        }else if(node.getValue()<value){
            return findWith2(node.getRightNode(),value);
        }else{
            return node;
        }
    }
    
    /**
     * 中序遍历
     * @author tomsnail
     * @date 2015年3月31日 下午6:23:05
     */
    public void midScan(AVLNode node){
        if(node==null){
            return;
        }
        midScan(node.getLeftNode());
        System.out.println(node.getValue());
        midScan(node.getRightNode());
    }
    
    public AVLNode getRootNode() {
        return rootNode;
    }

    public static void main(String[] args) {
        int[] is = new int[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80};//10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80
        AVLTree tree = new AVLTree();
        for(int i=0;i<is.length;i++){
            tree.add(is[i]);
        }
        System.out.println(tree.getRootNode().getValue());
        System.out.println("----------------------------");
        tree.midScan(tree.getRootNode());
        tree.delete(4);
        System.out.println(isBalance(tree.getRootNode()));
        System.out.println();
        //tree.find(40);
    }
    
    
    public static int depth(AVLNode node){
        if(node==null){
            return 0;
        }else{        
            int ld = depth(node.getLeftNode());        
            int rd = depth(node.getRightNode());        
            return 1 + (ld >rd ? ld : rd);    
        }
    }
    
    public static boolean isBalance(AVLNode node){    
        if (node==null)         
            return true;    
        int dis = depth(node.getLeftNode()) - depth(node.getRightNode());    
        if (dis>1 || dis<-1 )        
            return false;    
        else        
            return isBalance(node.getLeftNode()) && isBalance(node.getRightNode());
    }
}
class AVLNode{
    private int value;
    private AVLNode leftNode;
    private AVLNode rightNode;
    private AVLNode rootNode;
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public AVLNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(AVLNode leftNode) {
        this.leftNode = leftNode;
        if(leftNode!=null){
            leftNode.setRootNode(this);
        }
    }
    public AVLNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(AVLNode rightNode) {
        this.rightNode = rightNode;
        if(rightNode!=null){
            rightNode.setRootNode(this);
        }
    }
    
    public AVLNode getRootNode() {
        return rootNode;
    }
    public void setRootNode(AVLNode rootNode) {
        this.rootNode = rootNode;
    }
    
    public boolean hasSubNode(){
        if(this.leftNode!=null||this.rightNode!=null){
            return true;
        }else{
            return false;
        }
    }
    
    public AVLNode(){
    }
    public AVLNode(int value){
        this.value = value;
    }
}