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

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

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

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

实现思路

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

二叉查找树

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

二叉查找树实现

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

    public void add(Point p){//通常从根节点插入
        if(p.infothis.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 getPointsList() {
        return pointsList;
    }

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

    private List pointsList = new ArrayList();

    public Point getRootPoint() {
        List list = new ArrayList();
        for(Point p : pointsList){
            list.add(p);
        }
        for(Point p:pointsList){
            for(int i = 0;ipackage 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.infothis.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());
    }

}