java实现数据结构12（AVLTree详解代码之自定义AVLTree）

末蓝、 2023-06-25 01:59 60阅读 0赞

## AVLTree ##

import java.util.ArrayList;
    
    /** * @description: AVLTree是具有调节二分搜索树平衡的树，使得二分搜索树保持左右深度差的绝对值不超过1 * @author: liangrui * @create: 2019-12-23 21:34 **/
    public class AVLTree<K extends Comparable<K>,V> { 
    
        private class Node{ 
            public K key;
            public V value;
            public Node left,right;
            public int height;
    
            public Node(K key,V value){ 
                this.key=key;
                this.value=value;
                left=null;
                right=null;
                height=1;
            }
        }
    
        private Node root;
        private int size;
    
        public AVLTree(){ 
            root=null;
            size=0;
        }
    
        public int getSize(){ 
            return size;
        }
    
        public boolean isEmpty(){ 
            return size==0;
        }
    
        /** * 判断该二叉树是否是一颗二分搜索树 * @return */
        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;
    
        }
    
        /** * 前序排序 * @param node * @param keys */
        private void inOrder(Node node,ArrayList<K> keys){ 
            if (node==null){ 
                return;
            }
    
            inOrder(node.left,keys);
            keys.add(node.key);
            inOrder(node.right,keys);
        }
    
    
        /** * 判断该二叉树是否是一棵平衡二叉树 * @return */
        public boolean isBalanced(){ 
            return isBalanced(root);
        }
    
        /** * 判断Node为根的二叉树是否是一棵平衡二叉树，递归算法 * @param node * @return */
        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的平衡因子 * @param node * @return */
        private int getBalanceFactor(Node node){ 
            if (node==null){ 
                return 0;
            }
            return getHeight(node.left)-getHeight(node.right);
        }
    
        /** * 获得节点node的高度 * @param node * @return */
        private int getHeight(Node node){ 
            if(node==null){ 
                return 0;
            }
            return node.height;
        }
    
        // 对节点y进行向右旋转操作，返回旋转后新的根节点x
        // y x
        // / \ / \
        // x T4 向右旋转 (y) z y
        // / \ - - - - - - - -> / \ / \
        // z T3 T1 T2 T3 T4
        // / \
        // T1 T2
        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;
        }
    
        // 对节点y进行向左旋转操作，返回旋转后新的根节点x
        // y x
        // / \ / \
        // T1 x 向左旋转 (y) y z
        // / \ - - - - - - - -> / \ / \
        // T2 z T1 T2 T3 T4
        // / \
        // T3 T4
        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;
        }
    
        /** * 向二分搜索树中添加新的元素(key,value) * @param key * @param value */
        public void add(K key,V value){ 
            root=add(root,key,value);
        }
    
        /** * 向以node为根的二分搜索树插入元素(key,value),递归算法 * @param node * @param key * @param value * @return 返回插入新节点后二分搜索树的根 */
        private Node 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=Math.max(getHeight(node.left),getHeight(node.right))+1;
    
            //计算平衡因子
            int balanceFactor=getBalanceFactor(node);
    
            //平衡维护
            if (balanceFactor>1&&getBalanceFactor(node.left)>=0){ 
                return rightRotate(node);
            }
    
            if (balanceFactor<-1&&getBalanceFactor(node.right)<=-1){ 
                return leftRotate(node);
            }
    
            if (balanceFactor>1&&getBalanceFactor(node.left)<0){ 
                node.left=leftRotate(node.left);
                return rightRotate(node);
            }
    
            if (balanceFactor<-1&&getBalanceFactor(node.right)>0){ 
                node.right=rightRotate(node.right);
                return leftRotate(node);
            }
    
            return node;
        }
    
        /** * 返回以node为根节点的二分搜索树中，key所在的节点 * @param node * @param key * @return */
        private Node getNode(Node node,K key){ 
            if (node==null){ 
                return null;
            }
    
            if (key.equals(node.key)){ 
                return node;
            }else if (key.compareTo(node.key)<0){ 
                return getNode(node.left,key);
            }else { 
                return getNode(node.right,key);
            }
        }
    
        public boolean contains(K key){ 
            return getNode(root,key)!=null;
        }
    
        public V get(K key){ 
            Node node=getNode(root,key);
            return node==null?null:node.value;
        }
    
        public void set(K key,V newValue){ 
            Node node=getNode(root,key);
            if (node==null){ 
                throw new IllegalArgumentException(key+"doesn't exist.");
            }
            node.value=newValue;
        }
    
        /** * @param node * @return 返回以node为根的二分搜索树的最小值所在的节点 */
        private Node getMinNode(Node node){ 
            if (node.left==null){ 
                return node;
            }
            return getMinNode(node.left);
        }
    
        /** * 从二分搜索树中删除键为key的节点 * @param key * @return */
        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=null;
            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);
            }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 reNode=getMinNode(node.right);
                    reNode.right=remove(node.right,reNode.key);
                    reNode.left=node.left;
                    node.left=node.right=null;
                    retNode=reNode;
                }
            }
    
            if (retNode==null){ 
                return null;
            }
    
            // 更新height
            retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
    
            // 计算平衡因子
            int balanceFactor = getBalanceFactor(retNode);
    
            // 平衡维护
            if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
                return rightRotate(retNode);
    
            if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
                return leftRotate(retNode);
    
            if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) { 
                retNode.left = leftRotate(retNode.left);
                return rightRotate(retNode);
            }
    
            if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { 
                retNode.right = rightRotate(retNode.right);
                return leftRotate(retNode);
            }
    
            return retNode;
        }
    
    }

## 基于AVLTree创建自定义AVLSet ##

#### 1.自定义Set接口 ####

/** * @description: 自定义Set接口 * @author: liangrui * @create: 2019-12-24 10:37 **/
    public interface Set<E> { 
        void add(E e);
        boolean contains(E e);
        void remove(E e);
        int getSize();
        boolean isEmpty();
    }

#### 2.AVLSet ####

/** * @description: 基于AVLTree创建自定义AVLSet * @author: liangrui * @create: 2019-12-24 10:45 **/
    public class AVLSet<E extends Comparable<E>> implements Set<E> { 
    
        private AVLTree<E,Object> avlTree;
    
        public AVLSet(){ 
            avlTree=new AVLTree<>();
        }
    
    
        @Override
        public void add(E e) { 
            avlTree.add(e,null);
        }
    
        @Override
        public boolean contains(E e) { 
            return avlTree.contains(e);
        }
    
        @Override
        public void remove(E e) { 
            avlTree.remove(e);
        }
    
        @Override
        public int getSize() { 
            return avlTree.getSize();
        }
    
        @Override
        public boolean isEmpty() { 
            return avlTree.isEmpty();
        }
    }

## 基于AVLTree创建自定义AVLMap ##

#### 1.自定义Map接口 ####

/** * @description: 自定义map接口 * @author: liangrui * @create: 2019-12-24 10:35 **/
    public interface Map<K,V> { 
        void add(K key, V value);
        boolean contains(K key);
        V get(K key);
        void set(K key, V newValue);
        V remove(K key);
        int getSize();
        boolean isEmpty();
    }

#### 2.AVLMap ####

/** * @description: 基于AVLTree自定义Map * @author: liangrui * @create: 2019-12-24 10:38 **/
    public class AVLMap<K extends Comparable<K>,V> implements Map<K,V> { 
    
        private AVLTree<K,V> avlTree;
    
        public AVLMap(){ 
            avlTree=new AVLTree<>();
        }
    
        @Override
        public void add(K key, V value) { 
            avlTree.add(key, value);
        }
    
        @Override
        public boolean contains(K key) { 
            return avlTree.contains(key);
        }
    
        @Override
        public V get(K key) { 
            return avlTree.get(key);
        }
    
        @Override
        public void set(K key, V newValue) { 
            avlTree.set(key, newValue);
        }
    
        @Override
        public V remove(K key) { 
            return avlTree.remove(key);
        }
    
        @Override
        public int getSize() { 
            return avlTree.getSize();
        }
    
        @Override
        public boolean isEmpty() { 
            return avlTree.isEmpty();
        }
    }