AVL树实现练习

debug了好久才写出来的平衡树，代码里有注释可以方便理解
可能有代码冗余或者有误的地方，欢迎指出错误
（好像因为是看了别人的博客，所以混淆了结点高度这个概念，我先解释一下我代码里的Height=当前结点到叶子结点的经过的边+1）
很抱歉影响了你的观看体验！

推荐一个网站（数据结构操作可视化）
(我这里给出的是平衡树界面)
AVL Tree Visualzation
(我debug就是看着可视化的树查错的)

还是讲下一些关键操作吧：
1、左旋(基操)
左旋不会改变中序遍历

2、右旋(基操)
右旋不会改变中序遍历

3、LL(左左)
用下图举例的话，就是插入操作为在结点1的左孩子的左孩子处插入结点3，这样会使得平衡度== 2
就是对结点1进行一个右旋

4、RR(右右，在结点1的右孩子的右孩子处插入结点3，这样会使得平衡度==-2)
就是对结点1进行一个左旋

5、LR（左右，在结点1的左孩子的右孩子处插入结点3，这样会使得平衡度==-2）
就是先对结点2右旋，再对结点1左旋

6、RL(开摆！你们自己对照着LR比划去罢)

7、计算平衡度
首先得到当前结点的左右孩子的高度(高度的更新是在回溯的时候进行的，所以可以保证子结点的高度已经是正确的了)
然后就是return leftHeight-rightHeight了

8、找到左子树的最大值
删除一个左右子结点都存在的结点时，需要用左子树的最大结点或右子树的最小结点来替代当前结点(我的代码里用的是左子树的最大结点)
其实左子树的最大结点就是左子树的最右下角的结点

下面开始放代码(欢迎喷我代码的问题)

import java.util.LinkedList;

/**
 * @author 20级三班刘宇阳
 * @create 2022/2/3
 */

/**
 * 平衡樹
 * @param <K> key的类型 元素必须可比较
 * @param <V> value的类型
 */
public class AVLTree<K extends Comparable<K>,V> {
    //树结点类
    private class Node{
        //键
        private K key;
        //值
        private V value;
        //高度
        private Integer height;
        //左右父
        private Node left,right,parent;

        public Node(K key,V value) {
            this.key=key;
            this.value = value;
            height=1;
        }

        /**
         * 获得平衡度
         * @return 平衡度
         */
        private int getBalanceFactor(){
            int leftHeight=left==null?0:left.getHeight();
            int rightHeight=right==null?0:right.getHeight();
            return leftHeight-rightHeight;
        }

        private int getHeight(){
            return height;
        }

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

        /**
         * 更新该结点的高度
         */
        private void updateHeight(){
            int leftHeight=left==null?0:left.getHeight();
            int rightHeight=right==null?0:right.getHeight();
            height=1+Math.max(leftHeight,rightHeight);
        }

        private K getKey() {
            return key;
        }

        private void setKey(K key) {
            this.key = key;
        }

        private V getValue() {
            return value;
        }

        private void setValue(V value) {
            this.value = value;
        }

        private void setKeyAndValue(K key,V value){
            setKey(key);
            setValue(value);
        }

        private Node getLeft() { return left; }

        private void setLeft(Node left) { this.left = left; }

        private Node getRight() { return right; }

        private void setRight(Node right) { this.right = right; }

        private Node getParent() { return parent; }

        private void setParent(Node parent) { this.parent = parent; }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }
    //结点个数
    private int size;
    //根结点
    private Node root;

    public AVLTree(){
        clear();
    }

    /**
     *    1              2
     *     \            / \
     *      2     =>   1   3
     *       \
     *        3
     * @param node1 需要调整的该子树的根结点
     * @return 新的根结点
     */
    private Node leftRotate(Node node1){
        Node node2=node1.getRight();
        node1.setRight(node2.getLeft());
        node1.setParent(node2);
        if(node1.getRight()!=null){
            node1.getRight().setParent(node1);
        }
        node2.setLeft(node1);
        node1.updateHeight();
        node2.updateHeight();
        return node2;
    }

    /**
     *      1       2
     *     /  =>   / \
     *    2       3   1
     *   /
     *  3
     * @param node1 需要调整的该子树的根结点
     * @return 新的根结点
     */
    private Node rightRotate(Node node1){
        Node node2=node1.getLeft();
        node1.setLeft(node2.getRight());
        node1.setParent(node2);
        if(node1.getLeft()!=null){
            node1.getLeft().setParent(node1);
        }
        node2.setRight(node1);
        node1.updateHeight();
        node2.updateHeight();
        return node2;
    }

    /**
     * 作为put的递归工具方法
     * @param root 当前的根结点
     * @param key
     * @param value
     * @return
     */
    private Node addNode(Node root,K key,V value){
        if(root==null){
            //直接返回结点，让父节点更新子结点，同时不走下面的reBalance
            return new Node(key,value);
        }
        int cmpRes=key.compareTo(root.getKey());
        //小于，看左子树
        if(cmpRes<0){
            //这里需要更新左子结点
            Node leftChild=addNode(root.getLeft(),key,value);
            root.setLeft(leftChild);
            leftChild.setParent(root);
        }else if(cmpRes>0){//大于，看右子树
            //这里需要更新右子结点
            Node rightChild=addNode(root.getRight(),key,value);
            root.setRight(rightChild);
            rightChild.setParent(root);
        }else{
            //key值相等就认为是更新
            root.setValue(value);
        }
        return reBalance(root);
    }

    private Node reBalance(Node root){
        int bf=root.getBalanceFactor();
        //左子树高
        if(bf>1){
            Node leftChild=root.getLeft();
            int childBF=leftChild.getBalanceFactor();
            /**LL型
             *        1              2
             *       /              / \
             *      2              3   1
             *     /        =>
             *    3
             **/
            if(childBF>0){
                //右旋
                root=rightRotate(root);
            }
            /** LR型
             *
             *       1          1        3
             *      /          /        / \
             *     2    =>    3   =>   2   1
             *      \        /
             *       3      2
             */
            else{
                //先左旋再右旋
                //注意左旋是以2为根结点
                root.setLeft(leftRotate(root.getLeft()));
                root=rightRotate(root);
            }
        }else if(bf<-1){//右子树高
            Node rightChild=root.getRight();
            int childBF=rightChild.getBalanceFactor();
            /**RL型
             *
             *    1         1             3
             *     \         \           / \
             *      2  =>     3   =>    1   2
             *     /           \
             *    3             2
             */
            if(childBF>0){
                //注意右旋是以2为根结点
                root.setRight(rightRotate(root.getRight()));
                root=leftRotate(root);
            }
            /**RR型
             *     1              2
             *      \            / \
             *       2    =>    1   3
             *        \
             *         3
             */
            else{
                //左旋
                root=leftRotate(root);
            }
        }
        //这里可以在回溯时更新路径上的所有结点的高度(已平衡的结点会直接来这里更新高度)
        root.updateHeight();
        return root;
    }

    /**
     * 根据key值寻找结点
     * @param root 当前根节点
     * @param key 当前键
     * @return 目标结点
     */
    private Node findNode(Node root,K key){
        if(root==null){
            return null;
        }
        int cmpRes=key.compareTo(root.getKey());
        if(cmpRes<0){
            return findNode(root.getLeft(),key);
        }else if(cmpRes>0){
            return findNode(root.getRight(),key);
        }else{
            return root;
        }
    }

    /**
     * 查找要被删除结点的左子树的最大节点
     * @param root 当前根节点
     * @param deletedNode 要被删除的结点
     * @return
     */
    private Node replaceNode(Node root,Node deletedNode){
        if(root.getRight()==null){
            deletedNode.setKeyAndValue(root.getKey(),root.getValue());
            return null;
        }
        root.setRight(replaceNode(root.getRight(),deletedNode));
        root.updateHeight();
        return reBalance(root);
    }

    /**
     * 删除结点
     * @param root 当前根节点
     * @param key 目标键
     * @return 当前子树的新根节点(可能会更新也可能不会),用来给父节点更新子树
     */
    private Node deleteNode(Node root,K key){
        if(root==null){
            return null;
        }
        int cmpRes=key.compareTo(root.getKey());
        if(cmpRes<0){
            //找左子树
            Node leftChild=deleteNode(root.getLeft(), key);
            root.setLeft(leftChild);
            if(leftChild!=null){
                //
                leftChild.setParent(root);
            }
        }else if(cmpRes>0) {
            //找右子树
            Node rightChild=deleteNode(root.getRight(), key);
            root.setRight(rightChild);
            if(rightChild!=null){
                rightChild.setParent(root);
            }
        }else{
            //找到要删除的结点了
            if(root.getLeft()==null&&root.getRight()==null){//叶子结点
                if(root.getParent()==null){
                    setRoot(null);
                }
                return null;
            }else if(root.getLeft()==null){//左子树为空，右子树不为空
                root.getRight().setParent(root.getParent());
                if(root.getParent()==null){
                    setRoot(root.getRight());
                }
                return root.getRight();
            } else if(root.getRight()==null){//右子树为空，左子树不为空
                root.getLeft().setParent(root.getParent());
                if(root.getParent()==null){
                    setRoot(root.getLeft());
                }
                return root.getLeft();
            }
            else{//有两个儿子结点
                Node leftChild=root.getLeft();
                if(leftChild.getRight()==null){
                    //要被删除的结点用左儿子结点替换，同时他的右儿子要作为他左儿子的右儿子
                    leftChild.right=root.getRight();
                    root=leftChild;
                }else{
                    //用左子树的最大节点覆盖被删除的结点（可视为删除），并更新左孩子
                    Node newLeft=replaceNode(leftChild,root);
                    root.setLeft(newLeft);
                    if(newLeft!=null){
                        newLeft.setParent(root);
                    }
                }
            }
        }
        root.updateHeight();
        return reBalance(root);
    }

    /**
     * 放入元素
     * @param key 键
     * @param value 值
     */
    public void put(K key,V value){
        if(root==null){ setRoot(new Node(key,value)); }
        else{
            setRoot(addNode(root,key,value));
            //因为这些操作不涉及根结点的处理，所以需要单独写一个根结点的父节点置空
            getRoot().setParent(null);
        }
        size++;
    }

    /**
     * 获取键对应的值
     * @param key
     * @return 对应结点的值
     */
    public V get(K key){
        if(key==null){
            throw new NullPointerException("key cannot be null");
        }
        Node node=findNode(root,key);
        if(node==null){
            return null;
        }
        return node.getValue();
    }

    /**
     * 根据键删除对应结点
     * @param key 键
     */
    public void remove(K key){
        if(key==null){
            throw new NullPointerException("key cannot be null");
        }
        setRoot(deleteNode(root,key));
        if(getRoot()!=null){
            getRoot().setParent(null);
        }
        size--;
    }

    /**
     * 重置树(可用于初始化)
     */
    public void clear(){
        size=0;
        root=null;
    }

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

    public int size() { return size; }

    private void setSize(int size) { this.size = size; }

    private Node getRoot() { return root; }

    private void setRoot(Node root) { this.root = root; }

    private StringBuilder preOrderTraverse(Node root,StringBuilder sb){
        if(root==null){
            //null结点为#
            sb.append("# ");
            return sb;
        }
        sb.append(root.getKey()).append(" ");
        sb=preOrderTraverse(root.getLeft(),sb);
        sb=preOrderTraverse(root.getRight(),sb);
        return sb;
    }

    @Override
    public String toString(){
        StringBuilder sb=new StringBuilder();
        sb.append("preOrderTraverseSequenceOfKey is [");
        sb=preOrderTraverse(root,sb);
        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }
}

class AVLTreeDemo{
    public static void main(String[] args) {
        AVLTree<Integer,Integer> tree=new AVLTree<>();
        LinkedList<Integer> list=new LinkedList<>();
        for(int i=1;i<=10;i++){
            list.add(i);
        }
        list.add(0);
//        System.out.println(list);
        System.out.println("----------put测试----------");
        System.out.println("输出的是前序遍历的key序列：");
        for(Integer it:list){
            tree.put(it,it);
            System.out.println(tree);
        }
        tree.remove(2);
        System.out.println(tree);
//        System.out.println("------------get测试--------------");
//        System.out.println(tree.get(2));
//        System.out.println("------------delete测试--------------");
//        tree.remove(2);
//        System.out.println(tree);
//        tree.remove(1);
//        System.out.println(tree);
//        tree.remove(-1);
//        System.out.println(tree);
//        tree.remove(0);
//        System.out.println(tree);
//        tree.put(11,11);
//        System.out.println(tree);
//        tree.remove(8);
//        System.out.println(tree);
//        tree.remove(9);
//        tree.remove(11);
//        System.out.println(tree);
//        tree.remove(3);
//        System.out.println(tree);
//        tree.remove(6);
//        tree.remove(4);
//        System.out.println(tree);
    }
}