数据结构——AVL树

作者: 小波同学 | 来源:发表于2022-02-27 01:00 被阅读0次

一、平衡二叉树

平衡二叉树也称平衡二叉搜索树（Self-balancing binary search tree）是一种结构平衡的二分搜索树。

平衡二叉树由二分搜索树发展而来，在二分搜索树的基础上平衡二叉树需要满足两个条件：

1、它的左右两个子树的高度差的绝对值不超过1。
2、左右两个子树都是一棵平衡二叉树

平衡因子

某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。如果某一结点的平衡因子绝对值大于1则说明此树不是平衡二叉树。为了方便计算每一结点的平衡因子我们可以为每个节点赋予height这一属性，表示此节点的高度。

常见的平衡二叉搜索树有：

AVL树
红黑树
Treap

二、AVL树

AVL树是由 G. M. Adelson- V elsky 和 E. M. Landis于1962年提出。AVL树是最早的平衡二叉树。

AVL树维护自身的平衡涉及到两个概念：

1、节点的高度
2、节点的平衡因子

节点的高度就是从根节点到该节点的边的总和

节点的平衡因子是左子树的高度减去它的右子树的高度

带有平衡因子1、0或 -1的节点被认为是平衡的，因为它的左右子树高度差不超过 1。

面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

三、AVL树代码实现

3.1 基础设计

首先我们可以设计出AVL树节点，并且实现一些简单通用的方法供后续操作。

public class AVLTree<K extends Comparable<K>, V> {

    //AVLTree 树节点类
    private class Node<K extends Comparable<K>, V>{

        public K key;

        public V value;

        public Node<K, V> left;

        public Node<K, V> right;

        //当前节点所处的高度值
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            //初始化新的节点都是叶子节点，高度都为1
            this.height = 1;
        }

        @Override
        public String toString() {
            return key.toString() +" : " + value.toString();
        }
    }

    // 根节点
    private Node<K, V> root;

    // 树容量
    private Integer size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    /**
     * 判断该二叉树是否是一棵平衡二叉树
     * @return
     */
    private boolean isBalanced(){
        return isBalanced(root);
    }

    /**
     * 判断该二叉树是否是一棵平衡二叉树, 递归调用函数
     * @param node
     * @return
     */
    private boolean isBalanced(Node<K,V> node){
        //node == null 代表该树是一颗平衡二叉树，
        //平衡二叉树左右子树高度相差不超过1
        // 因为空树的左右子树高度相差不超过1
        if(node == null){
            return true;
        }

        //获取平衡因子
        int balanceFactor = getBalanceFactor(node);

        //左右子树高度相差超过1，则不是平衡二叉树
        if(Math.abs(balanceFactor) > 1){
            return false;
        }
        //递归调用该节点的左右子树，判断是否是平衡二叉树
        return isBalanced(node.left) && isBalanced(node.right);
    }


    /**
     * 返回node节点的高度值
     * @param node
     * @return
     */
    private int getHeight(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return node.height;
    }

    /**
     * 获取节点node的平衡因子
     * @param node
     * @return
     */
    private int getBalanceFactor(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }
}

3.2 添加节点

往平衡二叉树中添加节点很可能会导致二叉树失去平衡，所以我们需要在每次插入节点后进行平衡的维护操作。插入节点破坏平衡性有如下四种情况：

3.2.1 LL（右旋）

LL的意思是向左子树（L）的左孩子（L）中插入新节点后导致不平衡，这种情况下需要右旋操作，而不是说LL的意思是右旋，后面的也是一样。

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示：

 * 右旋转
 * // 对节点y进行向右旋转操作，返回旋转后新的根节点x
 * //        y                              x
 * //       / \                           /   \
 * //      x   T4     向右旋转 (y)        z     y
 * //     / \       - - - - - - - ->    / \   / \
 * //    z   T3                       T1  T2 T3 T4
 * //   / \
 * // T1   T2

/**
 * 右旋转
 * // 对节点y进行向右旋转操作，返回旋转后新的根节点x
 * //        y                              x
 * //       / \                           /   \
 * //      x   T4     向右旋转 (y)        z     y
 * //     / \       - - - - - - - ->    / \   / \
 * //    z   T3                       T1  T2 T3 T4
 * //   / \
 * // T1   T2
 * @param y
 * @return
 */
private Node<K, V> rightRotate(Node<K, V> y){
    Node<K, V> x = y.left;
    Node<K, V> T3 = x.right;
    //向右旋转过程
    x.right = y;
    y.left = T3;

    //更新节点的高度height值
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    return x;
}

3.2.2 RR（左旋）

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示：

 * 向左旋转
 * // 对节点y进行向左旋转操作，返回旋转后新的根节点x
 * //    y                             x
 * //  /  \                          /   \
 * // T1   x      向左旋转 (y)       y     z
 * //     / \   - - - - - - - ->   / \   / \
 * //   T2  z                     T1 T2 T3 T4
 * //      / \
 * //     T3 T4

/**
 * 向左旋转
 * // 对节点y进行向左旋转操作，返回旋转后新的根节点x
 * //    y                             x
 * //  /  \                          /   \
 * // T1   x      向左旋转 (y)       y     z
 * //     / \   - - - - - - - ->   / \   / \
 * //   T2  z                     T1 T2 T3 T4
 * //      / \
 * //     T3 T4
 * @param y
 * @return
 */
private Node<K, V> leftRotate(Node<K, V> y){
    Node<K, V> x = y.right;
    Node<K, V> T2 = x.left;
    //向左旋转过程
    x.left = y;
    y.right = T2;

    //更新节点的高度height值
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    return x;
}

3.2.3 LR

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示：

3.2.4 RL

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示：

添加节点代码

/**
 * 向AVL树添加新的元素(key,value)
 * @param key
 * @param value
 */
public void add(K key, V value){
    //向根节点添加元素e
    root = add(root, key, value);
}

/**
 * 向以node为根的AVL树中插入元素(key,value)，递归算法
 * @param node
 * @param key
 * @param value
 * @return 返回插入新元素的AVL树的根
 */
private Node<K, V> add(Node<K, V> node, K key, V value){
    if(node == null){
        size ++;
        return new Node<>(key, value);
    }

    //递归调用，元素添加到node.left
    if(key.compareTo(node.key) < 0){
        node.left = add(node.left, key, value);
    }else if(key.compareTo(node.key) > 0){
        //递归调用，元素添加到node.right
        node.right = add(node.right, key, value);
    }else {
        node.value = value;
    }

    //更新节点的高度height
    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);

    //平衡维护
    //LL
    // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在左子树的左子树的左侧
    if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
        //右旋转
        return rightRotate(node);
    }

    //RR
    // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在右子树的右子树的右侧
    if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
        //左旋转
        return leftRotate(node);
    }

    //LR
    // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在左子树的左子树的右侧
    if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
        //先对node.left进行左旋转
        node.left = leftRotate(node.left);
        //然后对node进行右旋转
        return rightRotate(node);
    }

    //RL
    // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在右子树的右子树的左侧
    if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
        //先对node.right进行右旋转
        node.right = rightRotate(node.right);
        //然后对node进行左旋转
        return leftRotate(node);
    }

    //返回当前根节点
    return node;
}

3.3 删除节点

在删除AVL树节点前需要知道二分搜索树的节点删除操作，和二分搜索树删除节点不同的是我们删除AVL树的节点后需要进行平衡的维护操作。

/**
 * 返回以node为根的二分搜索树的最小值所在的节点
 * @param node
 * @return
 */
private Node<K, V> minimum(Node<K, V> node){
    if(node.left == null){
        return node;
    }
    return minimum(node.left);
}

/**
 * 从二分搜索树中删除元素键为key的节点, 并返回value, 不存在返回null
 * @param key
 * @return
 */
public V remove(K key){
   Node<K, V> node = getNode(root, key);
    if(node == null){
        //不存在直接返回null
        return null;
    }
    //存在
    root = remove(root, key);
    return node.value;
}

/**
 * 删除以node为根的二分搜索树中键为key的节点，递归递归方式
 * 返回删除节点后新的二分搜索树的根
 * @param node
 * @param key
 * @return
 */
private Node<K, V> remove(Node<K, V> node, K key){
    //节点为空，直接返回
    if(node == null){
        return null;
    }

    //声明要返回去的node
    Node<K, V> retNode;

    if(key.compareTo(node.key) < 0){
        //待删除元素key小于当前节点的键，向左递归寻找
        node.left = remove(node.left, key);
        retNode = node;
    }else if(key.compareTo(node.key) > 0){
        //待删除元素key大于当前节点的键，向右递归寻找
        node.right = remove(node.right, key);
        retNode = node;
    }else {
        //待删除节点左子树为空
        if(node.left == null){
            Node<K, V> rightNode = node.right;
            node.right = null;
            size --;
            retNode = rightNode;
        }

        //待删除节点右子树为空
        else if(node.right == null){
            Node<K, V> rightNode = node.left;
            node.left = null;
            size --;
            retNode = rightNode;
        }else {
            //待删除节点左、右子树不为空
            //找到比待删除节点大的最小节点，即待删除节点右子树最小节点
            //用这个节点顶替待删除节点的位置

            //找到比待删除节点大的最小节点，即待删除节点右子树最小节点
            Node<K, V> successor = minimum(node.right);
            //删除比待删除节点大的最小节点，并将返回值给succeer的右孩子
            //successor.right = removeMin(node.right);
            successor.right = remove(node.right, successor.key);

            //node.left赋值给successor.left
            successor.left = node.left;
            //node节点和二分搜索树脱离关系
            node.left = node.right = null;
            retNode = successor;
        }
    }

    if(retNode == null){
        //如果删除了该节点，返回的二叉树节点的根节点为空的话
        return null;
    }

    //更新节点的高度height
    retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;

    //计算平衡因子
    int balanceFactor = getBalanceFactor(retNode);

    //平衡维护
    //LL
    // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在左子树的左子树的左侧
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
        //右旋转
        return rightRotate(retNode);
    }

    //RR
    // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在右子树的右子树的右侧
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
        //左旋转
        return leftRotate(retNode);
    }

    //LR
    // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在左子树的左子树的右侧
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
        //先对node.left进行左旋转
        retNode.left = leftRotate(retNode.left);
        //然后对node进行右旋转
        return rightRotate(retNode);
    }

    //RL
    // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
    // 且新添加的节点是在右子树的右子树的左侧
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
        //先对node.right进行右旋转
        retNode.right = rightRotate(retNode.right);
        //然后对node进行左旋转
        return leftRotate(retNode);
    }

    //如果删除节点后，没有打破平衡，直接返回当前根节点
    return retNode;
}

3.4 完整代码

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

/**
 * @Author: huangyibo
 * @Date: 2022/2/26 20:24
 * @Description: AVL Tree
 */

public class AVLTree<K extends Comparable<K>, V> {

    //AVLTree 树节点类
    private class Node<K extends Comparable<K>, V>{

        public K key;

        public V value;

        public Node<K, V> left;

        public Node<K, V> right;

        //当前节点所处的高度值
        public int height;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            //初始化新的节点都是叶子节点，高度都为1
            this.height = 1;
        }

        @Override
        public String toString() {
            return key.toString() +" : " + value.toString();
        }
    }

    // 根节点
    private Node<K, V> root;

    // 树容量
    private Integer size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    /**
     * 判断该二叉树是否是一棵二分搜索树
     * @return
     */
    private boolean isBST(){
        List<K> keys = new ArrayList<>();
        inOrder(root, keys);
        for (int i = 1; i < keys.size(); i++) {
            if(keys.get(i - 1).compareTo(keys.get(i)) > 0){
                return false;
            }
        }
        return true;
    }

    //中序遍历
    private void inOrder(Node<K,V> node, List<K> keys) {
        if(node == null){
            return;
        }
        inOrder(node.left, keys);
        keys.add(node.key);
        inOrder(node.right, keys);
    }

    /**
     * 判断该二叉树是否是一棵平衡二叉树
     * @return
     */
    private boolean isBalanced(){
        return isBalanced(root);
    }

    /**
     * 判断该二叉树是否是一棵平衡二叉树, 递归调用函数
     * @param node
     * @return
     */
    private boolean isBalanced(Node<K,V> node){
        //node == null 代表该树是一颗平衡二叉树，
        //平衡二叉树左右子树高度相差不超过1
        // 因为空树的左右子树高度相差不超过1
        if(node == null){
            return true;
        }

        //获取平衡因子
        int balanceFactor = getBalanceFactor(node);

        //左右子树高度相差超过1，则不是平衡二叉树
        if(Math.abs(balanceFactor) > 1){
            return false;
        }
        //递归调用该节点的左右子树，判断是否是平衡二叉树
        return isBalanced(node.left) && isBalanced(node.right);
    }


    /**
     * 返回node节点的高度值
     * @param node
     * @return
     */
    private int getHeight(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return node.height;
    }

    /**
     * 获取节点node的平衡因子
     * @param node
     * @return
     */
    private int getBalanceFactor(Node<K, V> node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 右旋转
     * // 对节点y进行向右旋转操作，返回旋转后新的根节点x
     * //        y                              x
     * //       / \                           /   \
     * //      x   T4     向右旋转 (y)        z     y
     * //     / \       - - - - - - - ->    / \   / \
     * //    z   T3                       T1  T2 T3 T4
     * //   / \
     * // T1   T2
     * @param y
     * @return
     */
    private Node<K, V> rightRotate(Node<K, V> y){
        Node<K, V> x = y.left;
        Node<K, V> T3 = x.right;
        //向右旋转过程
        x.right = y;
        y.left = T3;

        //更新节点的高度height值
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }


    /**
     * 向左旋转
     * // 对节点y进行向左旋转操作，返回旋转后新的根节点x
     * //    y                             x
     * //  /  \                          /   \
     * // T1   x      向左旋转 (y)       y     z
     * //     / \   - - - - - - - ->   / \   / \
     * //   T2  z                     T1 T2 T3 T4
     * //      / \
     * //     T3 T4
     * @param y
     * @return
     */
    private Node<K, V> leftRotate(Node<K, V> y){
        Node<K, V> x = y.right;
        Node<K, V> T2 = x.left;
        //向左旋转过程
        x.left = y;
        y.right = T2;

        //更新节点的高度height值
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }


    /**
     * 向AVL树添加新的元素(key,value)
     * @param key
     * @param value
     */
    public void add(K key, V value){
        //向根节点添加元素e
        root = add(root, key, value);
    }

    /**
     * 向以node为根的AVL树中插入元素(key,value)，递归算法
     * @param node
     * @param key
     * @param value
     * @return 返回插入新元素的AVL树的根
     */
    private Node<K, V> add(Node<K, V> node, K key, V value){
        if(node == null){
            size ++;
            return new Node<>(key, value);
        }

        //递归调用，元素添加到node.left
        if(key.compareTo(node.key) < 0){
            node.left = add(node.left, key, value);
        }else if(key.compareTo(node.key) > 0){
            //递归调用，元素添加到node.right
            node.right = add(node.right, key, value);
        }else {
            node.value = value;
        }

        //更新节点的高度height
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

        //计算平衡因子
        int balanceFactor = getBalanceFactor(node);

        //平衡维护
        //LL
        // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在左子树的左子树的左侧
        if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
            //右旋转
            return rightRotate(node);
        }

        //RR
        // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在右子树的右子树的右侧
        if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
            //左旋转
            return leftRotate(node);
        }

        //LR
        // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在左子树的左子树的右侧
        if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
            //先对node.left进行左旋转
            node.left = leftRotate(node.left);
            //然后对node进行右旋转
            return rightRotate(node);
        }

        //RL
        // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在右子树的右子树的左侧
        if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
            //先对node.right进行右旋转
            node.right = rightRotate(node.right);
            //然后对node进行左旋转
            return leftRotate(node);
        }

        //返回当前根节点
        return node;
    }



    /**
     * 根据key从当前以当前node为根节点中寻找value, 不存在返回null
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> getNode(Node<K, V> node, K key){
        //递归终止条件
        if(node == null){
            return null;
        }

        //待寻找key比当前节点key小，递归调用node.left
        if(key.compareTo(node.key) < 0){
            return getNode(node.left, key);
        }else if(key.compareTo(node.key) > 0){
            //待寻找key比当前节点key大，递归调用node.right
            return getNode(node.right, key);
        }else {
            //待寻找key和当前节点key相等，直接返回
            return node;
        }
    }


    public boolean contains(K key) {
        return getNode(root, key) != null;
    }


    public void set(K key, V value) {
        Node<K, V> node = getNode(root, key);
        if(node == null){
            //不存在直接抛异常
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        //key已存在，则更新
        node.value = value;
    }

    public V get(K key) {
        Node<K, V> node = getNode(root, key);
        return node == null ? null : node.value;
    }

    /**
     * 返回以node为根的二分搜索树的最小值所在的节点
     * @param node
     * @return
     */
    private Node<K, V> minimum(Node<K, V> node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    /**
     * 从二分搜索树中删除元素键为key的节点, 并返回value, 不存在返回null
     * @param key
     * @return
     */
    public V remove(K key){
       Node<K, V> node = getNode(root, key);
        if(node == null){
            //不存在直接返回null
            return null;
        }
        //存在
        root = remove(root, key);
        return node.value;
    }

    /**
     * 删除以node为根的二分搜索树中键为key的节点，递归递归方式
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> remove(Node<K, V> node, K key){
        //节点为空，直接返回
        if(node == null){
            return null;
        }

        //声明要返回去的node
        Node<K, V> retNode;

        if(key.compareTo(node.key) < 0){
            //待删除元素key小于当前节点的键，向左递归寻找
            node.left = remove(node.left, key);
            retNode = node;
        }else if(key.compareTo(node.key) > 0){
            //待删除元素key大于当前节点的键，向右递归寻找
            node.right = remove(node.right, key);
            retNode = node;
        }else {
            //待删除节点左子树为空
            if(node.left == null){
                Node<K, V> rightNode = node.right;
                node.right = null;
                size --;
                retNode = rightNode;
            }

            //待删除节点右子树为空
            else if(node.right == null){
                Node<K, V> rightNode = node.left;
                node.left = null;
                size --;
                retNode = rightNode;
            }else {
                //待删除节点左、右子树不为空
                //找到比待删除节点大的最小节点，即待删除节点右子树最小节点
                //用这个节点顶替待删除节点的位置

                //找到比待删除节点大的最小节点，即待删除节点右子树最小节点
                Node<K, V> successor = minimum(node.right);
                //删除比待删除节点大的最小节点，并将返回值给succeer的右孩子
                //successor.right = removeMin(node.right);
                successor.right = remove(node.right, successor.key);

                //node.left赋值给successor.left
                successor.left = node.left;
                //node节点和二分搜索树脱离关系
                node.left = node.right = null;
                retNode = successor;
            }
        }

        if(retNode == null){
            //如果删除了该节点，返回的二叉树节点的根节点为空的话
            return null;
        }

        //更新节点的高度height
        retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;

        //计算平衡因子
        int balanceFactor = getBalanceFactor(retNode);

        //平衡维护
        //LL
        // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在左子树的左子树的左侧
        if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
            //右旋转
            return rightRotate(retNode);
        }

        //RR
        // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在右子树的右子树的右侧
        if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
            //左旋转
            return leftRotate(retNode);
        }

        //LR
        // 左子树比右子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在左子树的左子树的右侧
        if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
            //先对node.left进行左旋转
            retNode.left = leftRotate(retNode.left);
            //然后对node进行右旋转
            return rightRotate(retNode);
        }

        //RL
        // 右子树比左子树高度超过了1，说明当前节点的平衡被打破
        // 且新添加的节点是在右子树的右子树的左侧
        if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
            //先对node.right进行右旋转
            retNode.right = rightRotate(retNode.right);
            //然后对node进行左旋转
            return leftRotate(retNode);
        }

        //如果删除节点后，没有打破平衡，直接返回当前根节点
        return retNode;
    }
}

四、AVL树实现映射(Map)

Map接口

public interface Map<K, V> {

    /**
     * 添加元素
     * @param key
     * @param value
     */
    void add(K key, V value);

    /**
     * 删除元素，返回元素对应的value
     * @param key
     * @return
     */
    V remove(K key);

    /**
     * 是否包含key
     * @param key
     * @return
     */
    boolean contains(K key);

    /**
     * 修改元素key对应的value
     * @param key
     * @param value
     */
    void set(K key, V value);

    /**
     * 获取key对应的value
     * @param key
     * @return
     */
    V get(K key);

    /**
     * 映射的元素个数
     * @return
     */
    int getSize();

    /**
     * 映射是否为空
     * @return
     */
    boolean isEmpty();
}

AVLTreeMap实现

/**
 * @Author: huangyibo
 * @Date: 2022/2/27 0:47
 * @Description: AVLTreeMap 底层基于AVLTree
 */

public class AVLTreeMap<K extends Comparable<K>, V> implements Map<K, V> {

    private AVLTree<K,V> avlTree;

    public AVLTreeMap(){
        avlTree = new AVLTree<>();
    }

    @Override
    public void add(K key, V value) {
        avlTree.add(key,value);
    }

    @Override
    public V remove(K key) {
        return avlTree.remove(key);
    }

    @Override
    public boolean contains(K key) {
        return avlTree.contains(key);
    }

    @Override
    public void set(K key, V value) {
        avlTree.set(key, value);
    }

    @Override
    public V get(K key) {
        return avlTree.get(key);
    }

    @Override
    public int getSize() {
        return avlTree.getSize();
    }

    @Override
    public boolean isEmpty() {
        return avlTree.isEmpty();
    }
}

五、AVL树实现集合(Set)

集合(Set)接口

public interface Set<E> {

    /**
     * 添加元素
     * @param e
     */
    void add(E e);

    /**
     * 删除元素
     * @param e
     */
    void remove(E e);

    /**
     * 集合是否包含元素
     * @param e
     * @return
     */
    boolean contains(E e);

    /**
     * 集合的元素个数
     * @return
     */
    int getSize();

    /**
     * 集合是否为空
     * @return
     */
    boolean isEmpty();
}

AVLTreeSet实现

/**
 * @Author: huangyibo
 * @Date: 2022/2/27 0:52
 * @Description: AVLTreeSet 底层基于AVLTree
 */

public class AVLTreeSet<E extends Comparable<E>> implements Set<E> {

    private AVLTree<E, Object> avlTree;

    public AVLTreeSet(){
        avlTree = new AVLTree<>();
    }

    @Override
    public void add(E e) {
        avlTree.add(e, null);
    }

    @Override
    public void remove(E e) {
        avlTree.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return avlTree.contains(e);
    }

    @Override
    public int getSize() {
        return avlTree.getSize();
    }

    @Override
    public boolean isEmpty() {
        return avlTree.isEmpty();
    }
}

参考：
https://chiclaim.blog.csdn.net/article/details/80740418

https://catwing.blog.csdn.net/article/details/89110319

数据结构——AVL树

一、平衡二叉树

平衡因子

二、AVL树

三、AVL树代码实现

3.1 基础设计

3.2 添加节点

3.2.1 LL（右旋）

3.2.2 RR（左旋）

3.2.3 LR

3.2.4 RL

添加节点代码

3.3 删除节点

3.4 完整代码

四、AVL树实现映射(Map)

五、AVL树实现集合(Set)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

其他