java实现平衡二叉树(AVL树)

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在问题。

左边 BST存在的问题分析:

• 1)左子树全部为空，从形式上看，更像一个单链表.

• 2)插入速度没有 影响

• 3)查询速度明显降低(因为需要依次比较),不能发挥BST树的优势，因为每次还需要比较左子树，其查询速度比单链表还慢

• 4)解决方案 - 平衡二 叉树(AVL)

基本介绍

平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树，可以保证查询效率较高。

具有以下特点: 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、 伸展树等。

举例说明, 看看下面哪些AVL树,为什么?

平衡二叉搜索树的左右子树，高度差不能大于1，所以前两个满足。

获取数的高度方法

//创建Node节点
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //返回左子树的高度
    public int leftHeight(){
        if(left == null){
            return 0;
        }
        return left.height();
    }

    //返回右边=子树的高度
    public int rightHeight(){
        if(right == null){
            return 0;
        }
        return right.height();
    }

    //返回当前节点的高度，以该节点为根节点的树的高度
    public int height(){
        //返回当前节点的高度
        return Math.max(
                left == null ? 0 : left.height(),
                right == null ? 0 : right.height()) + 1;
    }
}

单旋转(左旋转)

当二叉排序树加入新的节点时，如果右子树高度 - 左子树高度 > 1 时，需要进行左旋转。

//左旋转的方法 
//调用该方法的是，当前节（理解为根节点）点左子树高度比右子树高度小，进行左旋转
//1、首先创建一个新的节点newNode 并赋给当前节点值
//2、让 newNode.left 指向 根节点的左子树
//3、在让newNode.right 指向 根节点右子树（上移）的左子树
//4、再让根节点value 改为右子树的value
//5、再让根节点（上移右节点）的right 指向 右子树的右子树
//6、让根节点（上移右节点）的left指向newNode节点
private void leftRotate(){
    //创建新的节点，以当前根节点的值 （把当前根节点拷贝作为左子树）
    Node newNode = new Node(value);
    //把新的节点的左子树设置成当前节点的左子树（拷贝的新节点指向根节点的左子树）
    newNode.left = left;
    //把新的节点的，右子树设置成，当前节点右子树的左子树（将根节点右子树的左子树給拷贝节点）
    newNode.right = right.left;
    //把当前节点的值替换成右子节点的值（当前节点值改为右子树的）
    value = right.value;
    //把当前节点的右子树设置成当前节点右子树的右子树（右子树上移作为根节点）
    right = right.right;
    //把当前节点的左子树（左子节点）设置成新的节点（连接下移的新节点【拷贝根节点】）
    left = newNode;
}

单旋转(右旋转)

当二叉排序树加入新的节点时，如果左子树高度 - 右子树高度> 1 时，需要进行右旋转。

//右旋转的方法 
//左旋转2-6方法左右反过来
//该方法在add方法中，每次添加判断当前节点的左右子树高度
private void rightRotate(){
    //创建新的节点，以当前根节点的值 （把当前根节点拷贝作为右子树）
    Node newNode = new Node(value);
    //把新的节点的右子树设置成当前节点的右子树（拷贝的新节点指向根节点的右子树）
    newNode.right = right;
    //把新的节点的，左子树设置成，当前节点左子树的右子树（将根节点左子树的右子树給拷贝节点）
    newNode.left = left.right;
    //把当前节点的值替换成左子节点的值（当前节点值改为左子树的）
    value = left.value;
    //把当前节点的左子树设置成当前节点左子树的左子树（左子树上移作为根节点）
    left = left.left;
    //把当前节点的右子树（右子节点）设置成新的节点（连接下移的新节点【拷贝根节点】）
    right = newNode;
}

双旋转

//添加节点的方法
//递归的形式添加节点，需满足二叉排序树的要求
public void add(Node node){
    if(node == null){
        return;
    }

    //判断传入的节点的值，和当前子树的根节点的值关系
    if(node.value < this.value){
        //如果当前节点，左子树为空null
        if(this.left == null){
            this.left = node;
        } else {
            //递归向左子树添加节点
            this.left.add(node);
        }
    } else { //添加节点的值，大于等于当前节点值
        //如果当前节点，右子树为空null
        if(this.right == null){
            this.right = node;
        } else {
            //递归向右子树添加节点
            this.right.add(node);
        }
    }

    //当添加完一个节点后，如果(右子树的高度-左子树的高度) > 1,左旋转
    if(rightHeight() - leftHeight() > 1){
        //如果当前节点的 右子树 的左子树高度 大于它的 右子树高度
        if(right != null && right.leftHeight() > right.rightHeight()){
            //当前节点的（右子树）进行右旋转
            right.rightRotate();
        }
        leftRotate(); // 左旋转..
        return; //必须要加
    }

    //当添加完一个节点后，如果：(左子树的高度-右子树的高度) > 1，右旋转
    if(leftHeight() - rightHeight() > 1){
        //如果当前节点的[左子树]的[[右子树]]高度大于它的[[左子树]]的高度
        if(left != null && left.rightHeight() > left.leftHeight()){
            //先对当前节点的（左子树）->（左旋转）
            left.leftRotate();
        }
        rightRotate(); //右旋转
    }
}

测试案例

public static void main(String[] args) {
    //int[] arr = {4,3,6,5,7,8}; //左旋数组
    //int[] arr = {10,12,8,9,7,6}; //右旋数组
    int[] arr = {10,11,7,6,8,9}; //双旋数组

    //创建一个AVLTree对象
    AVLTree avlTree = new AVLTree();
    //添加节点
    for (int i = 0; i < arr.length; i++) {
        avlTree.add(new Node(arr[i]));
    }

    //遍历
    System.out.println("中序遍历");
    avlTree.infixOrder();

    System.out.println("在没有平衡处理前~~");
    System.out.println("树的高度="+avlTree.getRoot().height());
    System.out.println("树的左子树高度="+avlTree.getRoot().leftHeight());
    System.out.println("树的右子树高度="+avlTree.getRoot().rightHeight());
    System.out.println("当前的根节点="+avlTree.getRoot());
}

测试结果

链接：完整代码
提取码：1234