AVL树的建立与删除（JAVA）

          这里有一些不太合理的代码，比如把AVL树专属的平衡因子加入到了树的定义上，这是最开始遗留的问题，暂时没改，等以后敲其他树的算法的时候再改一下吧

package com.bn;

public abstract class Tree{
    //左孩子
    private Tree left;
    //右孩子
    private Tree right;
    //父亲节点
    private Tree father;

    //数据
    private int entry;
    //树的高度
    private int height;
    //树的平衡因子,左子树高度-右子树高度
    private int balance;

    public Tree(int value){
        //节点数值随便现给定一个
        entry=value;
        //此时是叶子节点，高度为1
        height=1;
        //叶子节点必然平衡
        balance=0;
        left=null;
        right=null;
        father=null;
    }

    public void setLeftSon(Tree son){
        this.left=son;
        //我们可以往子树上插入空树，此时就无需设定子树的父亲
        if (son!=null){
            son.father=this;
        }
    }

    //设置右子树
    public void setRightSon(Tree son){
        this.right=son;
        //我们可以往子树上插入空树，此时就无需设定子树的父亲
        if (son!=null){
            son.father=this;
        }
    }

    //将当前树替换为t树
    //不会改变父亲与当前树的关系
    //这里不是深度copy,子树并没有重新构造对象，必须保证替换后t树的不再被引用
    //否则会存在两颗树同时指向一个子树的BUG
    public void replace(Tree t){
       // this.father=t.father; 除了爸爸，其他每一个都复制一下
        this.setLeftSon(t.left);
        this.setRightSon(t.right);
        this.height=t.height;
        this.balance=t.balance;
        this.entry=t.entry;
    }

    //判断其是不是父亲的左孩子
    public boolean isFatherLeftSon(){

        return this==father.left;
    }

    //更新树的高度，只能从该位置开始,如果需要更新全部节点高度，
    //只能争对每一个叶子节点使用一次，建议建树的时候就开始更新
    //返回第一个失衡点的引用,传送的时候需要传送一个空应用
    public Tree updateHeight(Tree firstBreakBalanceTree){
        //先假定一个不可能的数值
        int newHeight=-1;
        //两颗子树都存在
        if(left!=null&&right!=null){
            //当前高度为，两颗子树高度的最大值加1
            newHeight=Math.max(left.height, right.height)+1;
            //调整平衡因子
            balance=left.height-right.height;
        }else if(left==null&&right==null){//此时为叶子节点
            //叶子节点高度为0
            newHeight=1;
            //调整平衡因子
            balance=0;
        }else if(left!=null){//如果左子树不是空树，且右子树是空树
            newHeight=left.height+1;
            //调整平衡因子
            balance=left.height;
        }else if(right!=null){//如果右子树不是空树，且左子树是空树
            newHeight=right.height+1;
            //调整平衡因子
            balance=-right.height;
        }
        //这棵树破坏平衡，并且我们还没有找到破坏平衡的树
        if ((balance<-1||balance>1)&&firstBreakBalanceTree==null){
            //那么这个第一棵破坏平衡的树就是他了
            firstBreakBalanceTree=this;
        }

        //前后两次高度不相等，说明树高度变化
        if(height!=newHeight){
            height=newHeight;
            //如果存在父节点
            if(father!=null){
                //开始递归
                return father.updateHeight(firstBreakBalanceTree);
            }
        }
        //返回第一棵破坏平衡的数
        return firstBreakBalanceTree;
    }



    public void setBalance(int balance) { this.balance = balance; }

    public void setHeight(int height) { this.height = height; }

    public void setEntry(int entry){ this.entry=entry; }

    //获得数据
    public int getEntry() { return entry; }

    //获得高度
    public int getHeight() {
        return height;
    }

    //获得平衡因子
    public int getBalance() {
        return balance;
    }

    //获得父亲节点
    public Tree getFather() {
        return father;
    }

    //获得左子树
    public Tree left() {
        return left;
    }

    //获得右子树
    public Tree right() { return right; }

    //递归插入树，内部调用
    public abstract void insert_rec(Tree newTree);
    //插入一个数据到树中，开放给别人使用
    public abstract void insert(int value);
    //递归删除一颗树
    public abstract void delete_rec();
    //删除一颗树，其数值等于value的数值
    public abstract void delete(int value);
    //查找一颗树，其数值等于value的数值
    public abstract Tree search(int value);
    //打印一棵树
    public abstract void printTree();

    public void Preorder(){
        if(left!=null){
            left.Preorder();
        }

        System.out.print(this.entry+" ");

        if (right!=null){
            right.Preorder();
        }
    }

    //树的字符串表现形式
    @Override
    public String toString() {
        //如果是空树就打印____符
        if (entry==-10){
            return "{entry=null}t";
        }else{
            return "{entry="+entry+",height="+height+",balance="+balance+"}t";
        }
    }
}

        想要表述的都写在注释里面啦，第一次尝试敲AVL，如有错误的地方欢迎指出，有不懂的地方也可以私信我

package com.bn;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class AVL extends Tree
{
	final static int TYPE_RR=0;
	final static int TYPE_LL=1;
	final static int TYPE_RL=2;
	final static int TYPE_LR=3;
	final static int TYPE_R0=5;
	final static int TYPE_L0=6;
	final static int TYPE_ERROR=4;


	public static void main(String[] args){
		int[] array={4,8,16,5,3,15,14,9,6,13,7,11,12,10,1,2,19,18,17};
		AVL avl=null;
		for(int i:array){
			if (avl==null){
				avl=new AVL(i);
			}else{
				avl.insert(i);
				System.out.println("======插入"+i+"后======");
				avl.printTree();
				System.out.println();
			}
		}
		avl.Preorder();

		for(int i:array){


			System.out.println("n======删除"+i+"后======");
			avl.delete(i);

			avl.printTree();
		}

	}


	//生成一颗树
	public AVL(int entry){
		super(entry);
	}

	//返回自己平衡的类型
	public int breakBalanceType(){
		int balance=this.getBalance();
		Tree left=this.left();
		Tree right=this.right();
		//左子树高度高了2
		if(balance==2){
			//左子树的左子树高，为LL形状
			if(left.getBalance()==1){
				return TYPE_LL;
			}else if(left.getBalance()==-1){//如果是左子树的右子树高，则为LR形状
				return TYPE_LR;
			}else if (left.getBalance()==0){//删除子树的时候会出现这种情况，具体情形见调整部分
				return TYPE_L0;
			}
		}else if(balance==-2){//右子树高了2
			//右子树的右子树高，为RR形状
			if(right.getBalance()==-1){
				return TYPE_RR;
			}else if(right.getBalance()==1){//如果是右子树的左子树高,则为RL形状
				return TYPE_RL;
			}else if (right.getBalance()==0){//删除子树的时候会出现这种情况，具体情形见调整部分
				return TYPE_R0;
			}
		}

		//不是这几种情况的都是错误的
		//如果自己是平衡树，也不该调用这个方法，所以返回ERROR
		return TYPE_ERROR;
	}

	//调整RR型
	public void adjustLL(){
		//A,B,C,D,E为中序遍历序列对应编号、x
		//A,B,两棵树需要大改动，故重新建立节点
		AVL A=new AVL(this.getEntry());
		AVL B=new AVL(this.left().getEntry());
		//C,D,E三棵子树只需调整位置，无需改动
		AVL C=(AVL) this.left().left();
		AVL D=(AVL) this.left().right();
		AVL E=(AVL) this.right();

		B.setLeftSon(C);
		B.setRightSon(A);
		A.setLeftSon(D);
		A.setRightSon(E);



		
		//假设调整情况如上图,由于A是我们新new的根节点，高度为1而不是2
		//调整后高度任然为1，此时就会认为A的高度没有发生改变
		//自然不会去递归的调整B的高度，但是实际上A的高度是发生改变的
		//故我们需要将A的高度设定为一个不可能的数值，调整A节点后必然回去调整B节点
		A.setHeight(-1);

		//调整A的高度后会递归的调整B的高度
		A.updateHeight(null);

		//用新树替换this
		//这里只是将新树中除father的成员拷贝到this中
		this.replace(B);

	}

	//调整LL型
	public void adjustRR(){
		//A,C,两棵树需要大改动，故重新建立节点
		AVL A=new AVL(this.getEntry());
		AVL C=new AVL(this.right().getEntry());
		//C,D,E三棵子树只需调整位置，无需改动
		AVL D=(AVL) this.right().left();
		AVL E=(AVL) this.right().right();
		AVL B=(AVL) this.left();

		C.setLeftSon(A);
		C.setRightSon(E);
		A.setLeftSon(B);
		A.setRightSon(D);



		//情况同上
		A.setHeight(-1);

		//调整A的高度后会递归的调整C的高度
		A.updateHeight(null);

		//用新树替换this
		//这里只是将新树中除father的成员拷贝到this中
		this.replace(C);
	}

	//调整LR型
	public void adjustLR(){
		//A,B,D节点变动较大，就不采用原本节点
		Tree A=new AVL(this.getEntry());
		Tree B=new AVL(this.left().getEntry());
		Tree D=new AVL(this.left().right().getEntry());
		//剩余树只是改变了父亲节点，无需改动，故不重新建树
		Tree C=this.left().left();
		Tree E=this.left().right().left();
		Tree F=this.left().right().right();
		Tree G=this.right();

		D.setLeftSon(B);
		D.setRightSon(A);
		B.setLeftSon(C);
		B.setRightSon(E);
		A.setLeftSon(F);
		A.setRightSon(G);

		//情况同上
		A.setHeight(-1);
		B.setHeight(-1);

		//只需调整A，C节点，D节点自动就调整好了
		A.updateHeight(null);
		B.updateHeight(null);

		//用新树替换this
		//这里只是将新树中除father的成员拷贝到this中
		this.replace(D);
	}

	//调整RL型
	public void adjustRL(){
		//A,C,D节点变动较大，就不采用原本节点
		Tree A=new AVL(this.getEntry());
		Tree C=new AVL(this.right().getEntry());
		Tree D=new AVL(this.right().left().getEntry());
		//剩余树只是改变了父亲节点，无需改动，故不重新建树
		Tree B=this.left();
		Tree E=this.right().left().left();
		Tree F=this.right().left().right();
		Tree G=this.right().right();


		D.setLeftSon(A);
		D.setRightSon(C);
		A.setLeftSon(B);
		A.setRightSon(E);
		C.setLeftSon(F);
		C.setRightSon(G);

		//情况同上
		A.setHeight(-1);
		C.setHeight(-1);

		//只需调整A，C节点，D节点自动就调整好了
		A.updateHeight(null);
		C.updateHeight(null);

		//用新树替换this
		//这里只是将新树中除father的成员拷贝到this中
		this.replace(D);
	}


	//调整R0型 删除后A平衡因子变为-2，C为0
	public void adjustR0() {
		//A,C节点变动较大，就不采用原本节点
		Tree A=new AVL(this.getEntry());
		Tree C=new AVL(this.right().getEntry());
		//剩余树只是改变了父亲节点，无需改动，故不重新建树
		Tree B=this.left();
		Tree D=this.right().left();
		Tree E=this.right().right();

		C.setRightSon(E);
		C.setLeftSon(A);
		A.setRightSon(D);
		A.setLeftSon(B);

		//情况同上
		A.setHeight(-1);

		//只需调整A，C节点，D节点自动就调整好了
		A.updateHeight(null);

		//用新树替换this
		//这里只是将新树中除father的成员拷贝到this中
		this.replace(C);
	}

	//调整L0型 删除后A平衡因子变为2，B为0
	public void adjustL0() {
		//A,B节点变动较大，就不采用原本节点
		Tree A=new AVL(this.getEntry());
		Tree B=new AVL(this.left().getEntry());
		//剩余树只是改变了父亲节点，无需改动，故不重新建树
		Tree C=this.right();
		Tree D=this.left().left();
		Tree E=this.left().right();

		B.setRightSon(A);
		B.setLeftSon(D);
		A.setRightSon(C);
		A.setLeftSon(E);

		//情况同上
		A.setHeight(-1);

		//只需调整A，C节点，D节点自动就调整好了
		A.updateHeight(null);

		//用新树替换this
		//这里只是将新树中除father的成员拷贝到this中
		this.replace(B);
	}

	//如果当前树不平衡，会将当前树调整至平衡树
	//调整后的树依旧保持原来的父子树关系
	public void adjustTree(){
		//判断本树不平衡类型
		int type=this.breakBalanceType();
		//根据非平衡类型进行调整
		switch (type){
			case TYPE_RR://RR型
				adjustRR();
				break;
			case TYPE_LL://LL型
				adjustLL();
				break;
			case TYPE_RL://RL型
				adjustRL();
				break;
			case TYPE_LR://LR型
				adjustLR();
				break;
			case TYPE_R0://R0型,删除后可能出现的类型
				adjustR0();
				break;
			case TYPE_L0://L0型，删除后可能出现的类型
				adjustL0();
				break;
			case TYPE_ERROR://如果树已经平衡，或者出现了逻辑错误，我的思路下是不会出现这种情况的
				System.out.println(this+" 出现错误");
				break;
		}

	}

	//check的同时会更新树的高度
	//检查当前树是否平衡，不平衡则调整，之后递归的检查父节点是否平衡
	public void check(){
		//调整树高和平衡因子，并且检查返回第一个破坏平衡的树
		AVL bbt=(AVL) this.updateHeight(null);
		//如果存在不平衡的树，则需要对其进行调整
		if (bbt!=null){
			//调整bbt为平衡树，其父亲不一定是平衡树
			bbt.adjustTree();
			//先找到父亲节点
			AVL father=(AVL)bbt.getFather();
			//父亲不是根节点
			if (father!=null){
				//检查父亲节点是否平衡
				father.check();
			}
		}
	}


	@Override
	public void insert(int value) {
		this.insert_rec(new AVL(value));
	}

	@Override
	//newTree里面必须放的是AVL的引用，所以建议插入数据使用insert方法而不是这个
	public void insert_rec(Tree newTree){
		//小于应该去左子树
		if(newTree.getEntry()this.getEntry()){//大于则去右子树
			//如果正好没有右子树
			if(this.right()==null){
				//将新节点插入右子树
				this.setRightSon(newTree);
				//当前树的高度和平衡因子都有可能发生改变
				//调整高度和平衡因子，并且检查是否出现失衡
				//如果失衡则调整
				this.check();
			}else{//如果已经存在右子树
				//则将节点插入到右子树
				this.right().insert_rec(newTree);
			}
		}
	}

	public Tree search(int value){
		//小于应该去左子树
		if(valuethis.getEntry()){//大于则去右子树
			//如果存在右子树
			if(this.right()!=null){
				//去右子树搜索
				return this.right().search(value);
			}else{//如果右子树为空，代表元素不在书中
				System.out.println("==="+value+"不在本树中===");
				return null;
			}
		}else{//正好等于，当前树就是我们要找的树
			return this;
		}
	}

	@Override
	public void delete_rec() {

		AVL father=(AVL)this.getFather();
		Tree t=this.left();
		AVL left=(AVL)this.left();
		AVL right=(AVL)this.right();
		//此时分为四种情况
		if(left==null&&right==null){//第一种情况，要删除的点正好是叶子节点

			//判断当前树是否为父亲的左子树
			if(this.isFatherLeftSon()){
				//删除该节点,方法结束后，delTree会变为野指针，自动会被GC回收
				father.setLeftSon(null);
			}else {
				father.setRightSon(null);
			}
			
			//父亲有可能不平衡
			//此时调整父亲节点直到平衡
			if(father!=null){//如果delTree不是根节点的话
				father.check();
			}
		}else if(left!=null&&right!=null){//左子树和右子树都存在

		
			//找到左子树的最右边的节点E，用这个节点的值替换A的值，并且删除E节点,找右子树的最左节点也可
			AVL E=left;
			while (E.right()!=null){
				E=(AVL) E.right();
			}
			//将E中的数值赋给A
			this.setEntry(E.getEntry());
			//删除E节点
			E.delete_rec();

			//删除节点后，父亲节点的高度可能发生变化，需要检查父亲节点是否平衡
			if(father!=null){//如果delTree不是根节点的话
				father.check();
			}

		}else if(left!=null){//只存在左子树，右子树不存在
			//直接用左子树替代当前树即可
			this.replace(this.left());


			

			//删除节点后，父亲节点的高度可能发生变化，需要检查父亲节点是否平衡
			if(father!=null){//如果delTree不是根节点的话
				father.check();
			}
		}else if(right!=null){//只存在右子树，与只存在左子树类似
			this.replace(this.right());
			//删除节点后，父亲节点的高度可能发生变化，需要检查父亲节点是否平衡
			if(father!=null){//如果delTree不是根节点的话
				father.check();
			}
		}

	}

	//
	@Override
	public void delete(int value) {
		//先查找值在不在树中
		Tree delTree=this.search(value);
		//如果数值不在树中，我们自然也无法删除这个值
		if(delTree==null){
			System.out.println("===删除失败===");
			return;
		}else if(this.getFather()==null&&this.getHeight()==1){
			//节点高度为1并且无父亲节点，也就是单个节点的树，自然不能删除
			System.out.println("n该树只剩值为"+value+"这一个节点，无法删除");
			return;

		}
		//将这颗树删除
		delTree.delete_rec();
	}


	//打印一棵树看看
	@Override
	public void printTree(){
		//当前访问节点指针
		Tree p;
		//当前访问了几个节点
		int visitedCount=0;
		//当前访问的节点在第几层
		int curLevel=0;
		//高度为k的平衡树，至多2^k-1个节点,但是我这里又多画了一层空树，空树之多为2*n+1，n是节点数
		int maxNodeCount=2*((int)Math.pow(2,getHeight())-1)+1;
		//保证队列足够长
		Queue queue=new ArrayBlockingQueue<>(maxNodeCount);
		//根节点入队
		queue.add(this);
		//当队列中还有着元素时
		while (!queue.isEmpty()){
			//第一个元素出队
			p=queue.remove();
			//当前访问的元素自增
			visitedCount++;
			//节点所在层数
			int newLevel=(int) Math.floor(Math.log(visitedCount)/Math.log(2))+1;
			//换层即换行
			if(newLevel!=curLevel){
				System.out.println();
				System.out.println("Level "+newLevel+":");
				curLevel=newLevel;
			}
			//打印树的信息
			System.out.print(p);

			//记录当前指针的1左右子树
			Tree left=p.left();
			Tree right=p.right();

			//多打印一层空树,-10判断当前树是否为空树
			if (left==null&&p.getEntry()!=-10){
				//创建一棵值为-10的树
				left=new AVL(-10);
				//调整树高度
				left.updateHeight(null);
			}
			if (right==null&&p.getEntry()!=-10){
				//创建一棵值为-10的树
				right=new AVL(-10);
				//调整树高度
				right.updateHeight(null);
			}

			if(left!=null){
				queue.add(left);
			}
			if(right!=null){
				queue.add(right);
			}
		}

	}

	
	
}

       运行代码后会 依次插入4,8,16,5,3,15,14,9,6,13,7,11,12,10,1,2,19,18,17这些节点构造树，并且再依次删除。每次插入删除都会打印一下树的形状，采取层次遍历的方式打印树，打印的时候如过一个节点存在空子树，会把空子树在下一层也打印一遍，不过空子树的空子树不会打印，第四层的两颗null树分别是第三层值为5的节点的两颗空子树，差不多就是这个规律吧。等以后有时间我把具体过程写上。

Level 1:
{entry=8,height=3,balance=1}    
Level 2:
{entry=4,height=2,balance=-1}    {entry=16,height=1,balance=0}    
Level 3:
{entry=null}    {entry=5,height=1,balance=0}    {entry=null}    {entry=null}    
Level 4:
{entry=null}    {entry=null}