【AVL平衡二叉树】JAVA代码实现

• 实现思路
• 二叉查找树
• • 二叉查找树实现
• 平衡二叉树实现
• • 旋转方法
  • 旋转方法使用
• 完整代码
• • 二叉树类
  • 节点类
  • 测试类

实现思路

AVL平衡二叉树，是在二叉查找树基础上加上了平衡功能，即依照平衡二叉树的规则插入数据之后，依旧要保证任意一个节点的左右子树深度相差不超过1，以此保证最大程度上保证二叉树的查询效率

二叉查找树

二叉查找树的思路非常简单，即数据从根节点插入，若插入值大于该节点则数据作为该节点的左子节点插入（小于则插入右子节点），若左子节点（右子节点）已经存在，则将该值传递至左子节点（右子节点）重复进行比较，直至找到空位插入。
若一个已经被排序的数组进行二叉查找树的插入则非常容易导致形成链式存储，导致二叉树本身的查询优势失效

二叉查找树实现

首先二叉查找树遵循小右大左的插入方式

    public void add(Point p){//通常从根节点插入
        if(p.info<this.getInfo()){//若欲插入节点值小于当前节点值
            if(this.getLeftPoint()!=null){//若当前节点的左子节点已经存在
                this.getLeftPoint().add(p);//将欲插入节点传递至当前节点的左子节点进行再次进行比较
            }else{
                this.setLeftPoint(p);//若当前节点没有左子节点，则该节点以当前节点的左子节点身份完成插入
            }
        }
        if(p.info>this.getInfo()){
            if(this.getRightPoint()!=null){
                this.getRightPoint().add(p);
            }else{
                this.setRightPoint(p);
            }
        }
        //balance();//此方法为平衡二叉树的平衡方法
    }

平衡二叉树实现

平衡二叉树是在二叉查找树的基础上加上了旋转方法，以此来保证二叉树的各个子树之间的深度相差不会大过2

旋转方法

旋转方法分为向左旋转和向右旋转，若当前节点的左子树深度大过右子树深度2及以上，则进行向右旋转，反之亦然

    //向左旋转
    private void leftRotate() {
        /**
         * 当右节点仅有一个左子树时需将左节点和其右子树关系先调整
         * 将左子节点的右子节点设置为左节点，将原来的左子节点设为新左子节点的左子节点
         * 方便旋转
         */
        Point newPoint;
        if(this.getRightPoint().getLeftPoint()!=null && this.getRightPoint().getRightPoint()==null){
            newPoint = this.getRightPoint();
            this.setRightPoint(this.getRightPoint().getLeftPoint());
            this.getRightPoint().setRightPoint(newPoint);
            this.getRightPoint().getRightPoint().setLeftPoint(null);
        }
        newPoint = new Point(this.info);
        if(this.getLeftPoint()!=null){
            newPoint.setLeftPoint(this.getLeftPoint());
        }
        this.setLeftPoint(newPoint);
        this.setInfo(this.getRightPoint().getInfo());
        /**
         * 右节点的左右子节点均存在时，将右节点的左节点设置为左节点的右子树，将右节点的右子树设定为根节点的右子树
         */
        if(this.getRightPoint().getLeftPoint()!=null){
            this.getLeftPoint().setRightPoint(this.getRightPoint().getLeftPoint());
        }
        this.setRightPoint(this.getRightPoint().getRightPoint());

    }
    //向右旋转
    private void rightRotate() {
        /**
         * 当左节点仅有一个右子树点时需将左节点和其右子树关系先调整
         */
        Point newPoint;
        if(this.getLeftPoint().getRightPoint()!=null && this.getLeftPoint().getLeftPoint()==null){
            newPoint = this.getLeftPoint();
            this.setLeftPoint(this.getLeftPoint().getRightPoint());
            this.getLeftPoint().setLeftPoint(newPoint);
            this.getLeftPoint().getLeftPoint().setRightPoint(null);
        }

        newPoint = new Point(this.info);
        if(this.getRightPoint()!=null){
            newPoint.setRightPoint(this.getRightPoint());
        }
        this.setRightPoint(newPoint);
        this.setInfo(this.getLeftPoint().getInfo());
        /**
         * 左节点的左右子节点均存在时，将左节点的右节点设置为右节点的左子树，将左节点的左子树设定为根节点的左子树
         */
        if(this.getLeftPoint().getRightPoint()!=null){
            this.getRightPoint().setLeftPoint(this.getLeftPoint().getRightPoint());
        }
        this.setLeftPoint(this.getLeftPoint().getLeftPoint());
    }

旋转方法使用

在平衡二叉树完成插入和删除等可能改变树的深度的操作之后都需要调用平衡方法

完整代码

二叉树类

其中重构了获取根节点的方法，因为在调用旋转之后根节点可能会发生变化

package AVLTree;

import java.util.ArrayList;
import java.util.List;

public class Tree {

    private Point rootPoint;

    public List<Point> getPointsList() {
        return pointsList;
    }

    public void setPointsList(List<Point> pointsList) {
        this.pointsList = pointsList;
    }

    private List<Point> pointsList = new ArrayList<Point>();

    public Point getRootPoint() {
        List<Point> list = new ArrayList<Point>();
        for(Point p : pointsList){
            list.add(p);
        }
        for(Point p:pointsList){
            for(int i = 0;i<list.size();i++){
                if(p.getLeftPoint()!=null){
                    if(p.getLeftPoint().getInfo()==list.get(i).getInfo()){
                        list.remove(i);
                    }
                }
                if(p.getRightPoint()!=null){
                    if(p.getRightPoint().getInfo()==list.get(i).getInfo()){
                        list.remove(i);
                    }
                }
            }
        }
        return list.get(0);
    }

    public void setRootPoint(Point rootPoint) {
        this.rootPoint = rootPoint;
    }



    Tree(int[] arr){
        int midNum = getMidNum(arr);
        this.rootPoint = new Point(midNum);
        this.pointsList.add(this.rootPoint);
        for(int i:arr){
            if(i!=this.rootPoint.getInfo()){
                Point p = new Point(i);
                this.getRootPoint().add(p);
                this.pointsList.add(p);
            }
        }
    }

    /**
     * 采用中序遍历
     * @param p
     */
    void showTre(Point p){
        if (p.getLeftPoint() != null) {
            showTre(p.getLeftPoint());
        }
        System.out.println(p.getInfo());
        if(p.getRightPoint()!=null){
            showTre(p.getRightPoint());
        }
    }

    int getMidNum(int[] arr){
        int x=0;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j< arr.length;j++){
                if(arr[i]<arr[j]){
                    x = arr[i];
                    arr[i] =arr[j];
                    arr[j] = x;
                }
            }
        }
        return arr[arr.length/2];
    }

}

节点类

package AVLTree;

public class Point {
    private int info;
    private int deep=0;
    private Point leftPoint;

    public int getInfo() {
        return info;
    }

    public void setInfo(int info) {
        this.info = info;
    }

    public Point getLeftPoint() {
        return leftPoint;
    }

    public void setLeftPoint(Point leftPoint) {
        this.leftPoint = leftPoint;
    }

    public Point getRightPoint() {
        return rightPoint;
    }

    public void setRightPoint(Point rightPoint) {
        this.rightPoint = rightPoint;
    }

    private Point rightPoint;

    Point(int info){
        this.info = info;
    }


    public int getDeep() {
        return deep;
    }

    public void setDeep(){
        this.deep = getHight();
    }

    public int getLeftHight(){
        if(this.getLeftPoint()==null){
            return 0;
        }
        return this.getLeftPoint().getHight();
    }
    public int getRightHight(){
        if(this.getRightPoint()==null){
            return 0;
        }
        return this.getRightPoint().getHight();
    }

    public int getHight(){
        if(this.getRightPoint()==null && this.getLeftPoint()==null){
            return 1;
        }else{
            return Math.max(this.getLeftPoint() == null ? 0 : this.getLeftPoint().getHight(), this.getRightPoint() == null ? 0 : this.getRightPoint().getHight())+ 1;
        }
    }

    public void add(Point p){
        if(p.info<this.getInfo()){
            if(this.getLeftPoint()!=null){
                this.getLeftPoint().add(p);
            }else{
                this.setLeftPoint(p);
            }
        }
        if(p.info>this.getInfo()){
            if(this.getRightPoint()!=null){
                this.getRightPoint().add(p);
            }else{
                this.setRightPoint(p);
            }
        }
        //balance();
    }
    //向左旋转
    private void leftRotate() {
        /**
         * 当右节点仅有一个左子树时需将左节点和其右子树关系先调整
         * 将左子节点的右子节点设置为左节点，将原来的左子节点设为新左子节点的左子节点
         * 方便旋转
         */
        Point newPoint;
        if(this.getRightPoint().getLeftPoint()!=null && this.getRightPoint().getRightPoint()==null){
            newPoint = this.getRightPoint();
            this.setRightPoint(this.getRightPoint().getLeftPoint());
            this.getRightPoint().setRightPoint(newPoint);
            this.getRightPoint().getRightPoint().setLeftPoint(null);
        }
        newPoint = new Point(this.info);
        if(this.getLeftPoint()!=null){
            newPoint.setLeftPoint(this.getLeftPoint());
        }
        this.setLeftPoint(newPoint);
        this.setInfo(this.getRightPoint().getInfo());
        /**
         * 右节点的左右子节点均存在时，将右节点的左节点设置为左节点的右子树，将右节点的右子树设定为根节点的右子树
         */
        if(this.getRightPoint().getLeftPoint()!=null){
            this.getLeftPoint().setRightPoint(this.getRightPoint().getLeftPoint());
        }
        this.setRightPoint(this.getRightPoint().getRightPoint());

    }
    //向右旋转
    private void rightRotate() {
        /**
         * 当左节点仅有一个右子树点时需将左节点和其右子树关系先调整
         */
        Point newPoint;
        if(this.getLeftPoint().getRightPoint()!=null && this.getLeftPoint().getLeftPoint()==null){
            newPoint = this.getLeftPoint();
            this.setLeftPoint(this.getLeftPoint().getRightPoint());
            this.getLeftPoint().setLeftPoint(newPoint);
            this.getLeftPoint().getLeftPoint().setRightPoint(null);
        }

        newPoint = new Point(this.info);
        if(this.getRightPoint()!=null){
            newPoint.setRightPoint(this.getRightPoint());
        }
        this.setRightPoint(newPoint);
        this.setInfo(this.getLeftPoint().getInfo());
        /**
         * 左节点的左右子节点均存在时，将左节点的右节点设置为右节点的左子树，将左节点的左子树设定为根节点的左子树
         */
        if(this.getLeftPoint().getRightPoint()!=null){
            this.getRightPoint().setLeftPoint(this.getLeftPoint().getRightPoint());
        }
        this.setLeftPoint(this.getLeftPoint().getLeftPoint());
    }
    void balance(){

        //如果其左子树长度高于右，则进行向右旋转
        if(this.getLeftHight()-this.getRightHight()>1){
            this.rightRotate();
            return;
        }
        //如果其右子树长度高于左，则进行向左旋转
        if(this.getRightHight()-this.getLeftHight()>1){
            this.leftRotate();
            return;
        }
    }

}

测试类

package AVLTree;

public class TestMain {


    public static void main(String[] args){
        int[] arr = {34,5,12,32,67,87};
        Tree tree = new Tree(arr);
        tree.showTre(tree.getRootPoint());
    }

}