自己动手实现java数据结构（七） AVL树

　　AVL树的实现继承自前面介绍的普通二叉搜索树—TreeMap类。由于AVL树通过树高作为判断平衡的依据，因此在二叉搜索树TreeMap的节点中增加了一个height(高度)属性。

/**
     * 二叉搜索树 内部节点
     * */
    static class EntryNode<K,V> implements Map.EntryNode<K,V>{
        
         * key值
         * */
        K key;

        
         * value值
         * 
        V value;

        
         * 高度值
         * */
        int height;

        
         * 左孩子节点
         * 
        EntryNode<K,1)"> left;

        
         * 右孩子节点
         *  right;

        
         * 双亲节点
         *  parent;

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

        EntryNode(K key,V value,EntryNode<K,1)"> parent) {
            this.parent = parent;
            ;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
         V getValue() {
             value;
        }

        @Override
        public void setValue(V value) {
             String toString() {
            return key + "=" + value + " height=" + height;
        }
    }

3.2 辅助方法

　　在AVL树的实现过程中，存在一些通用的，细节的逻辑，将其抽取成辅助函数，简化主要代码逻辑，增强代码可读性和可维护性。

   
     * 当前节点 是否满足AVL树约定的平衡条件
     * private boolean isAVLBalanced(EntryNode<K,1)"> entryNode){
        //获得 左子树高度
        int leftChildHeight = getHeight(entryNode.left);
        获得右子树高度
        int rightChildHeight = getHeight(entryNode.right);

        获得左右子树高度差
        int difference = leftChildHeight - rightChildHeight;

        高度差绝对值在1之内,认为是满足AVL平衡条件
        return -1 <= difference && difference <= 1;
    }

    
     * 更新当前节点高度
     * void updateHeight(EntryNode<K,1)">int leftHeight =int rightHeight =左右子树高度较高者 + 1
        entryNode.height = 1 + Math.max(leftHeight,rightHeight);
    }

    
     * 获得当前节点的高度
     * int getHeight(EntryNode<K,1)">if(entryNode == null){
            return 0;
        }else{
             entryNode.height;
        }
    }
    
    
     * 获得较高子树分支孩子节点
     private EntryNode<K,V> getTallerChild(EntryNode<K,1)">if(leftChildHeight > rightChildHeight){
            左子树高度 > 右子树高度
             entryNode.left;
        }左子树高度 <= 右子树高度
             entryNode.right;
        }
    }

    
     * 是否是左孩子
     * boolean isLeftChild(EntryNode<K,V> parent,EntryNode<K,1)"> target){
        return getRelativeByParent(parent,target) == RelativePosition.LEFT;
    }

3.3 3+4重构实现

（编辑：网站开发网_盐城站长网 ）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!