AVL树

平衡条件

若一个节点的左右孩子，高度差大于1，节点失衡

失衡情况

• LL

  – 失衡节点的左边更高

  – 失衡节点的左孩子的平衡因子>=0,即左孩子这边也是左边更高或等高

  

• LR

  – 失衡节点的bf>1，左边更高

  – 失衡节点的左孩子的bf<0，即左孩子右边更高

  

• RL

  – 失衡节点的bf<-1,右边高

  – 失衡节点右孩子的左边更高

  

• RR

  – 失衡节点的bf<-1，即右边更高

  – 失衡节点的右孩子的右边更高

  

代码实现

/**
 * @author ==> 许帅帅
 * @version ==> 1.0
 * 2023/5/21 14:11
 */
public class AVLTree {

    AVLNode root;

    static class AVLNode {
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1; //高度

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    //更新节点高度(新增、修改、删除、旋转)
    private void updateHeight(AVLNode node) {
        node.height = Integer.max(height(node.left), height(node.right)) + 1;
    }

    //求节点高度差(平衡因子)平衡： 0、1、-1 不平衡：>1 或者 <-1
    private int bf(AVLNode node) {
        return height(node.left) - height(node.right);
    }

    //右旋LL  返回值是新的根节点，参数是要旋转的节点
    private AVLNode rightRotate(AVLNode node) {
        AVLNode temp = node.left;
        node.left = temp.right;
        temp.right = node;
        updateHeight(node);
        updateHeight(temp);
        return temp;
    }

    //左旋 RR
    private AVLNode leftRotate(AVLNode node) {
        AVLNode temp = node.right;
        node.right = temp.left;
        temp.left = node;
        updateHeight(node);
        updateHeight(temp);
        return temp;
    }

    //LR
    private AVLNode leftRightRotate(AVLNode node) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    //RL
    private AVLNode rightLeftRotate(AVLNode node) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    //检查节点是否平衡,重新平衡代码
    private AVLNode balanced(AVLNode node) {
        if (node == null) {
            return null;
        }
        int bf = bf(node);
        //LL
        if (bf > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        }
        //LR
        else if (bf > 1 && bf(node.left) < 0) {
            return leftRightRotate(node);
        }
        // RL
        else if (bf < -1 && bf(node.right) > 0) {
            return rightLeftRotate(node);
        }
        //RR
        else if (bf < -1 && bf(node.right) <= 0) {
            return leftRotate(node);
        }
        return node;
    }

    //查询
    private AVLNode search(AVLNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            return search(node.left, key);
        } else if (key > node.key) {
            return search(node.right, key);
        } else {
            return node;
        }
    }


    public void put(int key, Object value) {
        root = doPut(root, key, value);
    }

    private AVLNode doPut(AVLNode node, int key, Object value) {
        //1.找到空位，创建新节点
        if (root == null) {
            return new AVLNode(key, value);
        }
        //2.key 已经存在，更新操作
        if (key == node.key) {
            node.value = value;
            return node;
        }
        //继续查找
        if (key < node.key) {
            node.left = doPut(node.left, key, value);
        } else {
            node.right = doPut(node.right, key, value);
        }
        //更新树高度
        updateHeight(node);
        //重新进行平衡
        return balanced(node);
    }

    //删除
    public void remove(int key) {
        root = doRemove(root, key);
    }

    private AVLNode doRemove(AVLNode node, int key) {
        //1. node == null
        if (node == null) {
            return null;
        }
        //2. 没有找到key
        if (key < node.key) {
            node.left = doRemove(node.left, key);
        } else if (key > node.key) {
            node.right = doRemove(node.right, key);
        } else {
            //3. 找到key 1.没有孩子 2. 只有一个 3. 有两个
            if (node.left == null && node.right == null) {
                //没有孩子
                return null;
            } else if (node.left == null) {
                node = node.right;
            } else if (node.right == null) {
                node = node.left;
            } else {
                //4. 有两个孩子
                AVLNode temp = node.right;
                //找到后继节点
                while(temp.left != null){
                    temp = temp.left;
                }

                temp.right = doRemove(node.right,temp.key);
                temp.left = node.left;

                node = temp;
            }
        }
        //更新高度
        updateHeight(node);
        //重新进行平衡
        return balanced(node);
    }

}