平衡树和AVL树

平衡树和AVL树

AVL树的实现

public class AVLTree<K extends Comparable<K>,V>{
    private class Node{
        public K key;
        public V value;
        public Node right;
        public Node left;
        public int height;

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

    private Node root;
    private int size;

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

    public int size(){
        return size;
    }

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

    public boolean isBST(){
        ArrayList<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 node,ArrayList<K> keys){
        if(node == null){
            return;
        }

        inOrder(node.left,keys);
        keys.add(node.key);
        inOrder(node.right,keys);
    }

    public boolean isBalanced(){
        return isBalanced(root);
    }

    private boolean isBalanced(Node node){
        if(node == null){
            return true;
        }

        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor)>1){
            return false;
        }
        return isBalanced(node.left) && isBalanced(node.right);
    }

    // 获得节点node高度
    private int getHeight(Node node){
        if(node == null){
            return 0;
        }
        return node.height;
    }

    private int getBalanceFactor(Node node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left)-getHeight(node.right);
    }

    public void add(K key,V value){
        root = add(root,key,value);
    }

    private void add(Node node,K key,V value){
        if(node == null){
            size++;
            return new Node(key,value);
        }

        if(key.compareTo(node.key)<0){
            node.left = add(node.left,key,value);
        }else if(key.compareTo(node.key)>0){
            node.right = add(node.right,key,value);
        }else{
            node.value = value;
        }
        // 更新height
        node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
        // 计算平衡因子
        int balanceFactor = getBalanceFactor(node);
        // 维护平衡
        // LL
        if(balanceFactor>1&&getBalanceFactor(node.left)>=0){
            return rightRotate(node);
        }
        // RR
        if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){
            reutrn leftRotate(node);
        }
        // LR
        if(balanceFactor>1&&getBalanceFactor(node.left)<0){
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // RL
        if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    private Node rightRotate(Node y){
        Node x = y.left;
        Node 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;
    }

    private Node leftRotate(Node y){
        Node x = y.right;
        Node 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;
    }

    public V remove(K key){
        Node node = getNode(root,key);
        if(node != null){
            root = remove(root,key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node,K key){
       if(node == null){
            return null;
       } 
       Node retNode;
       if(key.compareTo(node.key)<0){
            node.left = remove(node.left,key);
            retNode = node;
       }else if(key.compareTo(node.key)>0){
            node.right = remove(node.right,key);
            retNode = node;
       }else{
            
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                retNode = rightNode;
            }else if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                retNode = leftNode;
            }else{
                Node successor = mininum(node.right);
                successor.right = remove(node.right,successor.key);
                successor.left = node.left;

                node.lef = node.right = null;
                retNode = successor;
            }
       }

       if(retNode == null){
            return null;
       }

        // 更新height
        retNode.height = 1+Math.max(getHeight(retNode.left),getHeight(retNode.right));
        // 计算平衡因子
        int balanceFactor = getBalanceFactor(retNode);
        // 维护平衡
        // LL
        if(balanceFactor>1&&getBalanceFactor(retNode.left)>=0){
            return rightRotate(retNode);
        }
        // RR
        if(balanceFactor<-1&&getBalanceFactor(retNode.right)<=0){
            reutrn leftRotate(retNode);
        }
        // LR
        if(balanceFactor>1&&getBalanceFactor(retNode.left)<0){
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        // RL
        if(balanceFactor<-1&&getBalanceFactor(retNode.right)>0){
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return retNode;
    }
}