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

　　refactor34方法：方法的参数为3+4重构目标拓扑结构所需的三个节点(左，中，右)，左右孩子的分别挂载的四颗子树。在refactor34方法中，依照3+4重构的原理直接调整节点和子树的关系引用，拼接成最终的所需的结果。

　　rotateAt方法：方法的参数为重平衡所涉及到的祖孙三代节点(Node、Son、GrandSon)，通过判断N、S、GS的拓扑结构，决定调用refactor34方法时传递的参数。方法的返回值为3+4重构后的子树树根节点，便于重平衡操作之后，将重构后新的子树重新接入整颗AVL树中。

   
     * 3+4 重构
     *  refactor34(
        EntryNode<K,V> leftNode,V> middleNode,1)"> rightNode,V> llChild,1)"> lrChild,V> rlChild,1)"> rrChild){

        调整 左节点和对应子树的拓扑结构
        leftNode.left = llChild;
        if(llChild != ){
            llChild.parent = leftNode;
        }

        leftNode.right = lrChild;
        if(lrChild != ){
            lrChild.parent = leftNode;
        }
        更新高度
        updateHeight(leftNode);

        调整 右节点和对应子树的拓扑结构
        rightNode.left = rlChild;
        if(rlChild != ){
            rlChild.parent = rightNode;
        }

        rightNode.right = rrChild;
        if(rrChild != ){
            rrChild.parent = rightNode;
        }
                updateHeight(rightNode);

        调整 中间节点 和左、右节点的拓扑结构
        middleNode.left = leftNode;
        middleNode.right = rightNode;

        leftNode.parent = middleNode;
        rightNode.parent = middleNode;
                updateHeight(middleNode);
    }

    
     * 进行旋转,使用3+4重构完成重平衡
     * @return 重构之后子树的树根节点
     *  grandSonNode){
        if(isLeftChild(currentNode,sonNode)){
            左 zig
            (isLeftChild(sonNode,grandSonNode)){
                左-左   zig-zig旋转
                refactor34(grandSonNode,sonNode,currentNode,grandSonNode.left,grandSonNode.right,sonNode.right,currentNode.right);

                 sonNode;
            }{
                左-右   zig-zag旋转
                refactor34(sonNode,grandSonNode,sonNode.left,1)"> grandSonNode;
            }
        }右 zag
            右-左   zag-zig旋转
                refactor34(currentNode,currentNode.left,sonNode.right);

                 grandSonNode;
            }右-右   zag-zag旋转
 sonNode;
            }
        }
    }

3.4 插入方法重写

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

　　afterNewNodeInsert方法：

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

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

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