天天看点
返回

AVL树详解1. 简介2. 插入3. 删除4 java代码例子

AVL树详解

  • 1. 简介
  • 2. 插入
    • 2.1 单向右旋平衡处理LL
    • 2.2 单向左旋平衡处理RR
    • 2.3 双向旋转（先左后右）平衡处理LR
    • 2.4 双向旋转（先右后左）平衡处理RL
  • 3. 删除
  • 4 java代码例子

相关文章链接：

相关文章链接 第2节 数据结构

观前提示：

本文所使用的Eclipse版本为Photon Release (4.8.0)，IDEA版本为ultimate 2019.1，JDK版本为1.8.0_141，Tomcat版本为9.0.12。

1. 简介

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。

特点

  1. 本身首先是一棵二叉搜索树。
  2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

平衡因子： 某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。

2. 插入

这里只介绍插入节点后破坏平衡所做的旋转操作。

2.1 单向右旋平衡处理LL

在左子树（L）的左孩子（L）插入节点失衡，需要进行单向右旋平衡处理LL。

AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子

2.2 单向左旋平衡处理RR

在右子树（R）的右孩子（R）插入节点失衡，需要进行单向左旋平衡处理RR。

AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子

2.3 双向旋转（先左后右）平衡处理LR

在左子树（L）的右孩子（R）插入节点失衡，需要进行双向旋转（先左后右）平衡处理LR。

AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子

2.4 双向旋转（先右后左）平衡处理RL

在右子树（R）的左孩子（L）插入节点失衡，需要进行双向旋转（先右后左）平衡处理RL。

AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子

3. 删除

AVL树删除操作步骤如下

  1. 搜索给定的key，确定其是否在树中。
  2. 如果不在树中，返回null；如果在树中，执行标准的BST删除操作，并返回该删除的结点。
  3. 检查被删除结点的所有祖先结点是否平衡，如果不平衡，则执行重平衡操作。

BST删除操作三种情况

  1. 当该节点为叶子节点，则让该节点的父节点指向其变为NULL，然后释放节点。

  2. 当该节点不是叶子节点，但左子树或者右子树为空，则：

    （1）若左子树为空，则让该节点父节点指向其右节点。

    （2）若右子树为空，则让该节点父节点指向其左节点。

  3. 当该节点不是叶子节点，且左子树和右子树都不为空，则：

    （1）在该节点的左子树中找到最大节点Lmax（该节点必然是一个叶子节点）或者右子树中的最小节点Rmin，取出节点的值value，并删除该节点。

    （2）将value的值赋到要删除的节点。

4 java代码例子

AVL树 AVLTree.java

package TestTree.AVL;

public class AVLTree {

    private Integer root;
    private AVLTree left;
    private AVLTree right;
    private Integer height;

    public AVLTree(Integer root) {
        this.root = root;
    }

    public Integer getRoot() {
        return root;
    }

    public void setRoot(Integer root) {
        this.root = root;
    }

    public AVLTree getLeft() {
        return left;
    }

    public void setLeft(AVLTree left) {
        this.left = left;
    }

    public AVLTree getRight() {
        return right;
    }

    public void setRight(AVLTree right) {
        this.right = right;
    }

    public Integer getHeight() {
        return height;
    }

    /**
     * 获取指定节点深度
     * @param node
     * @return
     */
    public static Integer getHeight(AVLTree node){
        if(node == null){
            return 0;
        }
        return node.height;
    }

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

    /**
     * 指定节点深度赋值
     * @param node
     * @param height
     */
    public static void setHeight(AVLTree node, Integer height) {
        if(node == null){
            return;
        }
        node.height = height;
    }

    /**
     * 获取最小节点
     * @param node
     * @return
     */
    public static AVLTree getMinNode(AVLTree node){
        if(node != null && node.getLeft() == null){
            return node;
        }
        return getMinNode(node.getLeft());
    }
}

树操作工具类 TreeOperateUtil.java

package TestTree.AVL;

/**
 * 树操作工具类
 * @author jjy
 * @date 2020-10-19
 */
public class TreeOperateUtil {

    /**
     * 插入节点
     * @param node
     * @param data
     * @return
     */
    public static AVLTree insert(AVLTree node, int data){
        // 根节点没有数据，直接插入
        if(node == null || node.getRoot() == null){
            node = new AVLTree(data);
            node.setHeight(1);
            return node;
        }

        if(node.getRoot() > data){
            node.setLeft(insert(node.getLeft(), data));
        } else {
            node.setRight(insert(node.getRight(), data));
        }

        // 更新深度
        node.setHeight(1 + Math.max(AVLTree.getHeight(node.getLeft()), AVLTree.getHeight(node.getRight())));
        int balanceFactor = getBalanceFactor(node);

        // LL
        if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) > 0 ){
            System.out.println("-------------LL旋转-------------");
            return LLRotate(node);
        }

        // LR
        if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) < 0){
            System.out.println("-------------LR旋转-------------");
            return LRRotate(node);
        }

        // RR
        if(balanceFactor == -2 && getBalanceFactor(node.getRight()) < 0){
            System.out.println("-------------RR旋转-------------");
            return RRRotate(node);
        }

        // RL
        if(balanceFactor == -2 && getBalanceFactor(node.getRight()) > 0){
            System.out.println("-------------RL旋转-------------");
            return RLRotate(node);
        }

        return node;
    }

    /**
     * 删除节点
     * @param node
     * @param data
     * @return
     */
    public static AVLTree remove(AVLTree node, int data){
        if(node == null){
            return null;
        }
        if(node.getRoot() > data){
            node.setLeft(remove(node.getLeft(), data));
        } else if( node.getRoot() < data){
            node.setRight(remove(node.getRight(), data));
        } else {

            if(node.getLeft() == null) {
                // 没有左子树
                node = node.getRight();
            } else if(node.getRight() == null) {
                // 没有右子树
                node = node.getLeft();
            } else {
                // 左右子树均不为空，取右子树最小值（或者左子树最大值），替换当前要删除的节点
                AVLTree minNode = AVLTree.getMinNode(node.getRight());
                node.setRight(remove(node.getRight(), minNode.getRoot()));
                node.setRoot(minNode.getRoot());
            }

        }

        // 只有根节点，删除后为空
        if(node == null){
            return null;
        }

        // 更新深度
        node.setHeight(1 + Math.max(AVLTree.getHeight(node.getLeft()), AVLTree.getHeight(node.getRight())));
        int balanceFactor = getBalanceFactor(node);

        // LL
        if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) > 0 ){
            System.out.println("-------------LL旋转-------------");
            return LLRotate(node);
        }

        // LR
        if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) < 0){
            System.out.println("-------------LR旋转-------------");
            return LRRotate(node);
        }

        // RR
        if(balanceFactor == -2 && getBalanceFactor(node.getRight()) < 0){
            System.out.println("-------------RR旋转-------------");
            return RRRotate(node);
        }

        // RL
        if(balanceFactor == -2 && getBalanceFactor(node.getRight()) > 0){
            System.out.println("-------------RL旋转-------------");
            return RLRotate(node);
        }

        return node;
    }

    /**
     * LL旋转
     * @param node
     * @return
     */
    private static AVLTree LLRotate(AVLTree node){
        AVLTree result = node.getLeft();
        node.setLeft(result.getRight());
        result.setRight(node);

        AVLTree.setHeight(result.getLeft(), getTreeDepth(result.getLeft()));
        AVLTree.setHeight(result.getRight(), getTreeDepth(result.getRight()));
        AVLTree.setHeight(result, getTreeDepth(result));
        return result;
    }

    /**
     * RR旋转
     * @param node
     * @return
     */
    private static AVLTree RRRotate(AVLTree node){
        AVLTree result = node.getRight();
        node.setRight(result.getLeft());
        result.setLeft(node);

        AVLTree.setHeight(result.getLeft(), getTreeDepth(result.getLeft()));
        AVLTree.setHeight(result.getRight(), getTreeDepth(result.getRight()));
        AVLTree.setHeight(result, getTreeDepth(result));
        return result;
    }

    /**
     * LR旋转
     * @param node
     * @return
     */
    private static AVLTree LRRotate(AVLTree node){
        node.setLeft(RRRotate(node.getLeft()));
        return LLRotate(node);
    }

    /**
     * RL旋转
     * @param node
     * @return
     */
    private static AVLTree RLRotate(AVLTree node){
        node.setRight(LLRotate(node.getRight()));
        return RRRotate(node);
    }

    /**
     * 获取平衡因子
     * @param node
     * @return
     */
    private static int getBalanceFactor(AVLTree node){
        return AVLTree.getHeight(node.getLeft()) - AVLTree.getHeight(node.getRight());
    }

    /**
     * 获取树的深度
     * @param node
     * @return
     */
    private static int getTreeDepth(AVLTree node){
        if(node == null || node.getRoot() == null){
            return 0;
        }
        AVLTree left = node.getLeft();
        AVLTree right = node.getRight();
        return Math.max(getTreeDepth(left), getTreeDepth(right)) + 1;
    }
}

测试类 TestAVL.java

package TestTree.AVL;

import java.util.Arrays;
import java.util.List;

public class TestAVL {
    public static void main(String[] args) {
        System.out.println("-------------插入操作-------------");
        testInsert();
        System.out.println("-------------第一组删除操作-------------");
        testDelete();
        System.out.println("-------------第二组删除操作-------------");
        testDelete2();
    }

    /**
     * 测试插入节点
     */
    private static void testInsert(){
        AVLTree t1 = getTestData();
        System.out.println("-------------插入前-------------");
        TraversalUtil.init();
        List<Integer> preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        List<Integer> inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        List<Integer> postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        System.out.println("-------------1.插入70-------------");
        t1 = TreeOperateUtil.insert(t1, 70);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestData();
        System.out.println("-------------2.插入130-------------");
        t1 = TreeOperateUtil.insert(t1, 130);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestData();
        System.out.println("-------------3.插入85-------------");
        t1 = TreeOperateUtil.insert(t1, 85);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestData();
        System.out.println("-------------4.插入115-------------");
        t1 = TreeOperateUtil.insert(t1, 115);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));
    }

    /**
     * 测试数据
     *         100
     *       /    \
     *     90      110
     *   /          \
     * 80           120
     * @return
     */
    private static AVLTree getTestData(){
        AVLTree t1 = new AVLTree(100);
        AVLTree t2 = new AVLTree(90);
        AVLTree t3 = new AVLTree(110);
        AVLTree t4 = new AVLTree(80);
        AVLTree t5 = new AVLTree(120);
        t3.setHeight(1);
        t4.setHeight(1);
        t5.setHeight(1);
        t2.setLeft(t4);
        t2.setHeight(2);
        t3.setRight(t5);
        t2.setHeight(2);
        t1.setLeft(t2);
        t1.setRight(t3);
        t1.setHeight(3);
        return t1;
    }

    /**
     * 测试删除节点
     */
    private static void testDelete(){
        AVLTree t1 = getTestDeleteData1();
        System.out.println("-------------删除前-------------");
        TraversalUtil.init();
        List<Integer> preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        List<Integer> inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        List<Integer> postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        System.out.println("-------------1.删除80-------------");
        t1 = TreeOperateUtil.remove(t1, 80);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestDeleteData1();
        System.out.println("-------------2.删除120-------------");
        t1 = TreeOperateUtil.remove(t1, 120);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestDeleteData1();
        System.out.println("-------------3.删除95-------------");
        t1 = TreeOperateUtil.remove(t1, 95);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestDeleteData1();
        System.out.println("-------------4.删除105-------------");
        t1 = TreeOperateUtil.remove(t1, 105);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestDeleteData1();
        System.out.println("-------------5.删除100-------------");
        t1 = TreeOperateUtil.remove(t1, 100);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));
    }

    /**
     * 测试数据
     *               100
     *             /     \
     *          90       110
     *        /   \     /   \
     *      80     95  105  120
     *     /                  \
     *   70                   130
     * @return
     */
    private static AVLTree getTestDeleteData1(){
        AVLTree t1 = new AVLTree(100);
        AVLTree t2 = new AVLTree(90);
        AVLTree t3 = new AVLTree(110);
        AVLTree t4 = new AVLTree(80);
        AVLTree t5 = new AVLTree(95);
        AVLTree t6 = new AVLTree(105);
        AVLTree t7 = new AVLTree(120);
        AVLTree t8 = new AVLTree(70);
        AVLTree t9 = new AVLTree(130);

        t5.setHeight(1);
        t6.setHeight(1);
        t8.setHeight(1);
        t9.setHeight(1);
        t4.setLeft(t8);
        t4.setHeight(2);
        t7.setRight(t9);
        t7.setHeight(2);
        t2.setLeft(t4);
        t2.setRight(t5);
        t2.setHeight(3);
        t3.setLeft(t6);
        t3.setRight(t7);
        t3.setHeight(3);
        t1.setLeft(t2);
        t1.setRight(t3);
        t1.setHeight(4);

        return t1;
    }

    /**
     * 测试删除节点
     */
    private static void testDelete2(){
        AVLTree t1 = getTestDeleteData2();
        System.out.println("-------------删除前-------------");
        TraversalUtil.init();
        List<Integer> preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        List<Integer> inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        List<Integer> postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        System.out.println("-------------1.删除95-------------");
        t1 = TreeOperateUtil.remove(t1, 95);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));

        t1 = getTestDeleteData2();
        System.out.println("-------------2.删除105-------------");
        t1 = TreeOperateUtil.remove(t1, 105);
        TraversalUtil.init();
        preList = TraversalUtil.preOrder(t1);
        System.out.println("先序排列结果为：");
        System.out.println(Arrays.toString(preList.toArray()));

        TraversalUtil.init();
        inList = TraversalUtil.inOrder(t1);
        System.out.println("中序排列结果为：");
        System.out.println(Arrays.toString(inList.toArray()));

        TraversalUtil.init();
        postList = TraversalUtil.postOrder(t1);
        System.out.println("后序排列结果为：");
        System.out.println(Arrays.toString(postList.toArray()));
    }

    /**
     * 测试数据
     *               100
     *             /     \
     *          90       110
     *        /   \     /   \
     *      80     95  105  120
     *       \             /
     *       85          115
     * @return
     */
    private static AVLTree getTestDeleteData2(){
        AVLTree t1 = new AVLTree(100);
        AVLTree t2 = new AVLTree(90);
        AVLTree t3 = new AVLTree(110);
        AVLTree t4 = new AVLTree(80);
        AVLTree t5 = new AVLTree(95);
        AVLTree t6 = new AVLTree(105);
        AVLTree t7 = new AVLTree(120);
        AVLTree t8 = new AVLTree(85);
        AVLTree t9 = new AVLTree(115);

        t5.setHeight(1);
        t6.setHeight(1);
        t8.setHeight(1);
        t9.setHeight(1);
        t4.setRight(t8);
        t4.setHeight(2);
        t7.setLeft(t9);
        t7.setHeight(2);
        t2.setLeft(t4);
        t2.setRight(t5);
        t2.setHeight(3);
        t3.setLeft(t6);
        t3.setRight(t7);
        t3.setHeight(3);
        t1.setLeft(t2);
        t1.setRight(t3);
        t1.setHeight(4);

        return t1;
    }
}

测试结果为

AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子
AVL树详解1. 简介2. 插入3. 删除4 java代码例子
数据结构 avl树
上一篇: php array(object)格式转成纯数组
下一篇: 如何使用MFC编写自定义UI界面【附高仿QQ 2014登陆界面范例程序】1. 概述2. 编写自定义UI界面3. 小结

继续阅读