插入节点时，导致的失衡不会向上传播，所属子树的高度能够复原，在恢复平衡之后，直接结束方法的执行，不再继续向上检查。另外，对于未失衡的祖先节点，其子树插入新节点时可能会导致高度上升，因此需要更新其高度。

    @Override
     V put(K key,V value) {
        if(this.root == this.root = new EntryNode<>(key,value);
            this.size++;
            return ;
        }

        获得目标节点
        TargetEntryNode<K,V> targetEntryNode = getTargetEntryNode(key);
        if(targetEntryNode.relativePosition == RelativePosition.CURRENT){
            目标节点存在于当前容器

            暂存之前的value
            V oldValue = targetEntryNode.target.value;
            替换为新的value
            targetEntryNode.target.value =返回之前的value
             oldValue;
        }目标节点不存在于当前容器
            EntryNode<K,V> parent = targetEntryNode.parent;
            EntryNode<K,V> newEntryNode =  RelativePosition.LEFT){
                目标节点位于左边
                parent.left = newEntryNode;
            }目标节点位于右边
                parent.right = newEntryNode;
            }

            插入新节点后进行重平衡操作
            afterNewNodeInsert(newEntryNode);

            ;
        }
    }

   
     * 插入后 重平衡操作
     * @param newEntryNode 新插入的节点
     * void afterNewNodeInsert(EntryNode<K,1)"> newEntryNode){
        EntryNode<K,V> currentAncestorNode = newEntryNode.parent;

        遍历新插入节点的祖先节点,逐层向上
        while(currentAncestorNode != 判断当前祖先节点是否失去平衡
            if(!isAVLBalanced(currentAncestorNode)){
                不平衡

                获得重构之前 失衡节点的父节点及其相对位置，用于之后重新连接重平衡后的子树
                EntryNode<K,1)"> currentAncestorNode.parent;

                获得更高子树分支对应的孙辈节点，决定AVL树重平衡的策略
                EntryNode<K,V> tallerSonNode = getTallerChild(currentAncestorNode);
                EntryNode<K,V> tallerGrandSonNode = getTallerChild(tallerSonNode);
                以孙辈节点为基准，进行旋转，重平衡
                EntryNode<K,V> newSubTreeRoot = rotateAt(currentAncestorNode,tallerSonNode,tallerGrandSonNode);

                重构之后的子树 重新和全树对接
                newSubTreeRoot.parent = parent;
                可能currentAncestorNode是根节点，不存在双亲节点
                if(parent != ){
                    原子树根节点的双亲节点 和新的子树进行连接
                    (isLeftChild(parent,currentAncestorNode)){
                        parent.left = newSubTreeRoot;
                    }{
                        parent.right = newSubTreeRoot;
                    }
                }{
                    this.root = newSubTreeRoot;
                }
                插入时，最低失衡节点重平衡后，全树即恢复平衡，因此结束循环
                ;
            }平衡

                更新当前祖先节点的高度
                updateHeight(currentAncestorNode);
            }

            指向上一层祖先节点
            currentAncestorNode = currentAncestorNode.parent;
        }
    }

3.5 删除方法重写

　　AVL树的实现中，重写了普通二叉搜索树的删除方法(remove)，整体逻辑和之前TreeMap的实现大致一样，唯一的区别在于，当删除了之前老的节点之后，会调用afterNodeRemove方法，进行AVL树重平衡的一系列操作。

　　afterNodeRemove方法：

　　参数为之前被删除节点的双亲节点。从下至上，遍历检查被删除节点双亲的历代祖先，判断其是否失衡。一旦发现当前迭代的祖先节点失衡，则调用rotateAt方法，使其恢复平衡，全树重新接入子树。

　　删除节点时，失衡现象会向上传播，因此必须一直向上遍历至根节点。另外，对于未失衡的祖先节点，子树删除老节点时可能会导致高度降低，因此需要更新其高度。

 @Override
     V remove(K key) {
        查询目标节点
        TargetEntryNode<K,1)">if(targetEntryNode.relativePosition !=没有找到目标节点
            找到了目标节点
            EntryNode<K,V> target = targetEntryNode.target;
            先保存被删除节点 删除之前的双亲节点
            EntryNode<K,1)"> target.parent;

            从二叉树中删除目标节点
            deleteEntryNode(target);

            删除节点后，对其历代祖先节点进行重平衡操作
            afterNodeRemove(parent);

             targetEntryNode.target.value;
        }
    }

    deletedNode 被删除的节点
     * void afterNodeRemove(EntryNode<K,1)"> deletedNode){
        EntryNode<K,1)"> deletedNode;

        获得重构之前 失衡节点的父节点及其相对位置
                EntryNode<K,1)"> currentAncestorNode.parent;
                 newSubTreeRoot;
                }
            } currentAncestorNode.parent;
        }
    }

4.AVL树性能

4.1 插入性能

　　AVL树的插入操作引起的失衡不会向上传播，只需要一次重平衡操作。

　　相比普通二叉搜索树，AVL树插入重平衡操作额外引入的时间复杂度为O(1)，十分高效。

4.2 删除性能

　　AVL树的删除操作引起的失衡会向上传播，最坏情况下每一个祖先节点都需要进行重平衡。

　　相比普通二叉搜索树，AVL树删除重平衡操作额外引入的时间复杂度为O(logN)，删除效率比起红黑树(O(1))等更加高效的BBST相对要差。

4.3 查询性能

（编辑：清远站长网）

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