数据结构——AVL树

标签：node right return AVL key 数据结构 节点 left

一、平衡二叉树

平衡二叉树 也称平衡二叉搜索树（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

标签：node,right,return,AVL,key,数据结构,节点,left
From： https://blog.51cto.com/u_14014612/6031760