【数据结构-Java】平衡二叉树（AVL树）-java黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

码神

558

文章

281086

访问

+关注

分类

暂无分类

日期归档

2024-11(1)

【数据结构-Java】平衡二叉树（AVL树）

发布于2021-05-29 19:27 阅读(1072) 评论(0) 点赞(11) 收藏(4)

本博客主要参考周志明老师的《深入理解Java虚拟机》第三版
欢迎指出文章的不足之处；更多内容请点进爱敲代码的小游子查看

文章目录

1、基本介绍

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树，可以保证查询效率较高。
具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过****1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
看看下面哪些 AVL 树, 为什么?

2、应用案例-单旋转(左旋转)

1) 数列

{4,3,6,5,7,8}

2) 思路分析

创建新的节点，以当前根节点的值
把新的节点的左子树设置为当前节点的左子树
把新节点的右子树设置为当前节点的右子树的左子树
让当前节点的值等于当前节点的右子节点的值
让当前节点左子树指向newNode，右子树指向当前节点的右子树的右子树

3）代码

/**
     * 左旋转
     */
    private void leftRotate() {
        //1、创建新的节点，以当前根节点的值
        Node newNode = new Node(this.val);
        //2、把新的节点的左子树设置为当前节点的左子树
        newNode.left = this.left;
        //3、把新节点的右子树设置为当前节点的右子树的左子树
        newNode.right = this.right.left;
        //4、让当前节点的值等于当前节点的右子节点的值
        this.val = this.right.val;
        //5、让当前节点左子树指向newNode，右子树指向当前节点的右子树的右子树
        this.left = newNode;
        this.right = this.right.right;
    }

 /**
     * 添加节点中使用左旋转
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) throw new RuntimeException("节点为空");
        //传入节点的值和当前子树根节点的值比较，比当前值大就往右边比较
        if (node.val >= this.val) {
            if (this.right == null) {//如果右边为空，则直接挂在右子节点就可以
                this.right = node;
            } else { //递归往右子树添加
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
        //当添加完一个节点后，如果右子树的高度比左子树的高度高于1=>发生左旋转
        if (rightHeight() - leftHeight() > 1) {
           leftRotate();
        }
    }

高度测试

3、应用案例-单旋转(右旋转)

1）需求

数列 {10,12,8,9,7,6}

2）思路分析

创建一个新节点newNode，值相当于当前根节点

3）图解

/**
     * 右旋转
     */
    private void rightRotate() {
        //1、创建新的节点，设置为档期那根节点的值
        Node newNode = new Node(this.val);
        //2、把新结点的左子树设置为当前节点左子树的的右子树
        newNode.left = this.left.right;
        //3、把当新节点的右子树设置为当前节点的右子树
        newNode.right = this.right;
        //4、把当前节点的值设置为右子节点的值
        this.val = this.right.val;
        //5、把当前节点的左子树设值为左子树的左子树
        this.left = this.left.left;
        //6、把当前节点的右子树设置为新节点
        this.right = newNode;
    }

/**
     * 添加节点
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) throw new RuntimeException("节点为空");
        //传入节点的值和当前子树根节点的值比较，比当前值大就往右边比较
        if (node.val >= this.val) {
            if (this.right == null) {//如果右边为空，则直接挂在右子节点就可以
                this.right = node;
            } else { //递归往右子树添加
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
        //当添加完一个节点后，如果右子树的高度比左子树的高度高于1=>发生左旋转
        if (rightHeight() - leftHeight() > 1) {
            leftRotate();
        }
        //每次添加完一个节点后，如果（左子树高度-右子树高度>1）进行右旋转操作
        if(leftHeight() - rightHeight()>1){
            rightRotate();
        }
    }

高度测试

4、应用案例-双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转

不能完成平衡二叉树的转换。比如数列

int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树.

int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树

1) 问题分析

2) 解决思路分析

当符号右旋转的条件时
如果它的左子树的右子树高度大于它的左子树的高度
先对当前这个结点的左节点进行左旋转
在对当前结点进行右旋转的操作即可

3）代码

    /**
     * 添加节点
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) throw new RuntimeException("节点为空");
        //传入节点的值和当前子树根节点的值比较，比当前值大就往右边比较
        if (node.val >= this.val) {
            if (this.right == null) {//如果右边为空，则直接挂在右子节点就可以
                this.right = node;
            } else { //递归往右子树添加
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
        //当添加完一个节点后，如果右子树的高度比左子树的高度高于1=>发生左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的高度
            if(right!=null&&right.leftHeight()>right.rightHeight()){
                //先对右子节点右旋转
                right.rightRotate();
                //再对当前节点左旋转
                leftRotate();
            }else {
                leftRotate();
            }
            return;//每次加进元素时都会进行判断，不需要继续进行操作
        }
        //每次添加完一个节点后，如果（左子树高度-右子树高度>1）进行右旋转操作
        if (leftHeight() - rightHeight() > 1) {
            //如果左子树的右子树高度大于它左子树的高度
            if (left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前节点左节点进行左旋转
                left.leftRotate();
                //然后对当前节点进行右旋转
                rightRotate();
            } else {
                rightRotate();
            }
        }
    }

4）测试

5、AVL完整代码

package com.yky.algorithmFourth.dataStructure.tree.avl;

import java.util.StringJoiner;

/**
 * @Author: yky
 * @CreateTime: 2021-01-27
 * @Description: 二叉平衡树(AVL)
 */
public class AVLTreeDemo {

    public static void main(String[] args) {
        //int[] arr = {4, 3, 6, 5, 7, 8};
        //int []arr = {10,12,8,9,7,6};
        int[] arr = {2, 1, 6, 5, 7, 3};
        AVLTree avl = new AVLTree();
        for (int i = 0; i < arr.length; i++) {
            avl.add(new Node(arr[i]));
        }
        //avl.infixOrder();
        //高度测试
        System.out.println(avl.getRoot().height());
        System.out.println(avl.getRoot().left.height());
        System.out.println(avl.getRoot().right.height());

    }
}

class AVLTree {
    private Node root;

    /**
     * 添加节点
     */
    public void add(Node node) {
        if (root == null) root = node;//说明为空树
        else root.add(node);
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root == null) {
            System.out.println("空树");
            return;
        }
        root.infixNode();
    }

    public Node getRoot() {
        return root;
    }
}


/**
 * 节点类
 */
class Node {
    int val;//值
    Node left;//左
    Node right;//右

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

    /**
     * 左旋转
     */
    private void leftRotate() {
        //1、创建新的节点，以当前根节点的值
        Node newNode = new Node(this.val);
        //2、把新的节点的左子树设置为当前节点的左子树
        newNode.left = this.left;
        //3、把新节点的右子树设置为当前节点的右子树的左子树
        newNode.right = this.right.left;
        //4、让当前节点的值等于当前节点的右子节点的值
        this.val = this.right.val;
        //5、让当前节点左子树指向newNode，右子树指向当前节点的右子树的右子树
        this.left = newNode;
        this.right = this.right.right;
    }

    /**
     * 右旋转
     */
    private void rightRotate() {
        //1、创建新的节点，设置为档期那根节点的值
        Node newNode = new Node(this.val);
        //2、把新结点的左子树设置为当前节点左子树的的右子树
        newNode.left = this.left.right;
        //3、把当新节点的右子树设置为当前节点的右子树
        newNode.right = this.right;
        //4、把当前节点的值设置为右子节点的值
        this.val = this.right.val;
        //5、把当前节点的左子树设值为左子树的左子树
        this.left = this.left.left;
        //6、把当前节点的右子树设置为新节点
        this.right = newNode;
    }

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

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

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

    /**
     * 添加节点
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) throw new RuntimeException("节点为空");
        //传入节点的值和当前子树根节点的值比较，比当前值大就往右边比较
        if (node.val >= this.val) {
            if (this.right == null) {//如果右边为空，则直接挂在右子节点就可以
                this.right = node;
            } else { //递归往右子树添加
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
        //当添加完一个节点后，如果右子树的高度比左子树的高度高于1=>发生左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的高度
            if(right!=null&&right.leftHeight()>right.rightHeight()){
                //先对右子节点右旋转
                right.rightRotate();
                //再对当前节点左旋转
                leftRotate();
            }else {
                leftRotate();
            }
            return;//每次加进元素时都会进行判断，不需要继续进行操作
        }
        //每次添加完一个节点后，如果（左子树高度-右子树高度>1）进行右旋转操作
        if (leftHeight() - rightHeight() > 1) {
            //如果左子树的右子树高度大于它左子树的高度
            if (left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前节点左节点进行左旋转
                left.leftRotate();
                //然后对当前节点进行右旋转
                rightRotate();
            } else {
                rightRotate();
            }
        }
    }

    /**
     * 中序遍历
     */
    public void infixNode() {
        if (this.left != null) this.left.infixNode();
        System.out.println(this);
        if (this.right != null) this.right.infixNode();
    }

    @Override
    public String toString() {
        return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                .add("val=" + val)
                .toString();
    }
}