温故而知新--AVL树 插入自动平衡 手撕代码

/ 默认分类 / 2 条评论 / 2553浏览

数据结构AVL置顶

一.树节点定义

public class AVLTreeNode { 
    //节点的数据
    private int data;
    //当前节点的高度
    private int height;
    //当前节点的左节点
    private AVLTreeNode left; 
    //当前节点的右节点
    private AVLTreeNode right; 
}

二.自动平衡的旋转操作

2.1 LL插入情况的右旋转

AVLTreeNode LLInsertRightRotate (AVLTreeNode loseBalanceNode) { 
    //失衡节点的左节点先拎出来作为tempNode
    AVLTreeNode tempNode = loseBalanceNode.left;
    //用tempNode的右节点先替换tempNode作为失衡节点的左节点
    //(如果tempNode没有右节点就算了，那么这一步等于没有执行，因为指向null)
    loseBalanceNode.left = tempNode.right;
    //把失衡节点作为tempNode的右节点
    tempNode.right = loseBalanceNode;
    //重新计算失衡节点的高度
    loseBalanceNode.height = Math.max(calHeight(loseBalanceNode.left), calHeight(loseBalanceNode.right)) + 1; 
    //重新计算tempNode的高度（即最开始的失衡节点的左节点）
    tempNode.height = Math.max(calHeight(tempNode.left), calHeight(tempNode.right)) + 1;
    //返回失衡的子树平衡之后的新的根节点
    return tempNode; 
}

2.2 RR插入情况的左旋转

AVLTreeNode RRInsertLeftRotate (AVLTreeNode loseBalanceNode) { 
    //失衡节点的右节点先拎出来作为tempNode
    AVLTreeNode tempNode = loseBalanceNode.right;
    //用tempNode的左节点先替换tempNode作为失衡节点的右节点
    loseBalanceNode.right = tempNode.left;
    //把失衡节点作为tempNode的左节点
    tempNode.left = loseBalanceNode;
    //重新计算失衡节点的高度
    loseBalanceNode.height = Math.max(calHeight(loseBalanceNode.left), calHeight(loseBalanceNode.right)) + 1; 
    //重新计算tempNode的高度（即最开始的失衡节点的右节点）
    tempNode.height = Math.max(calHeight(tempNode.left), calHeight(tempNode.right)) + 1;
    //返回失衡的子树平衡之后的新的根节点
    return tempNode; 
}

2.3 LR插入情况的先左后右旋转

    AVLTreeNode LRInsertLeftAndRightRotate (AVLTreeNode loseBalanceNode) {
        //先将失衡节点的左节点为轴,进行左旋转
        loseBalanceNode.setLeft(RRInsertLeftRotate(loseBalanceNode.left));
        //再以失衡节点为轴,进行一次右旋转
        return LLInsertRightRotate(loseBalanceNode);
    }

2.4 RL插入情况的先右后左旋转

    AVLTreeNode RLInsertRightAndLeftRotate (AVLTreeNode loseBalanceNode) {
        //先将失衡节点的右节点为轴,进行右旋转
        loseBalanceNode.setRight(LLInsertRightRotate(loseBalanceNode.right));
        //再以失衡节点为轴,进行一次左旋转
        return RRInsertLeftRotate(loseBalanceNode);
    }

三.AVL树的插入操作

public class AVLTree {
    public AVLTreeNode root;

    public AVLTreeNode insert(AVLTreeNode root,int data){
        //如果当前树是空的,那么当前插入的元素就是这颗树的根节点
        if(root == null){
            root = new AVLTreeNode();
            root.setData(data);
            root.setHeight(0);
            root.setLeft(null);
            root.setRight(null);
        } else if (data < root.getData()) {
            //如果当前数据值小于当前树根节点的数据,按照BST的规则,就是插入到左子树中
            root.setLeft(this.insert(root.getLeft(),data));
            //插完之后,判断是否失衡
            if(this.balanceHeightCal(root.getLeft(),root.getRight()) > 1){
                if(data < root.getLeft().getData()){
                    //说明插在左子树,所以才比根小,因此执行LL插入的单右旋
                    root = this.LLInsertRightRotate(root);
                }else{
                    root = this.LRInsertLeftAndRightRotate(root);
                }
            }
        }else if (data > root.getData()) {
            //如果当前数据值大于当前树根节点的数据,按照BST的规则,就是插入到右子树中
            root.setRight(this.insert(root.getRight(),data));
            //插完之后,判断是否失衡(插在根节点的哪边说明哪边会变得更高一些，所以拿插入边高度和另一边相减)
            if(this.balanceHeightCal(root.getRight(),root.getLeft()) > 1){
                if(data > root.getRight().getData()){
                    //说明插在右子树,所以才比根大,因此执行RR插入的单左旋
                    root = this.RRInsertLeftRotate(root);
                }else{
                    root = this.RLInsertRightAndLeftRotate(root);
                }
            }
        }
        root.setHeight(this.compHeight(root.getLeft(),root.getRight())+1);
        return root;
    }

    private int balanceHeightCal(AVLTreeNode right, AVLTreeNode left) {
        if(right == null && left == null){
            return 0;
        }
        if(right == null){
            return left.height;
        }
        if(left == null){
            return right.height;
        }
        return right.getHeight() - left.getHeight();
    }

    private int compHeight(AVLTreeNode left, AVLTreeNode right) {
        if(left == null && right == null){
            return 0;
        }
        if(left == null){
            return right.height;
        }
        if(right == null){
            return left.height;
        }
        return Math.max(right.height, left.height);
    }

    AVLTreeNode LLInsertRightRotate (AVLTreeNode loseBalanceNode) {
        //失衡节点的左节点先拎出来作为tempNode
        AVLTreeNode tempNode = loseBalanceNode.left;
        //用tempNode的右节点先替换tempNode作为失衡节点的左节点
        //(如果tempNode没有右节点就算了，那么这一步等于没有执行，因为指向null)
        loseBalanceNode.left = tempNode.right;
        //把失衡节点作为tempNode的右节点
        tempNode.right = loseBalanceNode;
        //重新计算失衡节点的高度
        loseBalanceNode.height = Math.max(calHeight(loseBalanceNode.left), calHeight(loseBalanceNode.right)) + 1;
        //重新计算tempNode的高度（即最开始的失衡节点的左节点）
        tempNode.height = Math.max(calHeight(tempNode.left), calHeight(tempNode.right)) + 1;
        //返回失衡的子树平衡之后的新的根节点
        return tempNode;
    }

    private int calHeight(AVLTreeNode node) {
        if(node == null){
            return 0;
        }
        return node.height;
    }

    AVLTreeNode RRInsertLeftRotate (AVLTreeNode loseBalanceNode) {
        //失衡节点的右节点先拎出来作为tempNode
        AVLTreeNode tempNode = loseBalanceNode.right;
        //用tempNode的左节点先替换tempNode作为失衡节点的右节点
        loseBalanceNode.right = tempNode.left;
        //把失衡节点作为tempNode的左节点
        tempNode.left = loseBalanceNode;
        //重新计算失衡节点的高度
        loseBalanceNode.height = Math.max(calHeight(loseBalanceNode.left), calHeight(loseBalanceNode.right)) + 1;
        //重新计算tempNode的高度（即最开始的失衡节点的右节点）
        tempNode.height = Math.max(calHeight(tempNode.left), calHeight(tempNode.right)) + 1;
        //返回失衡的子树平衡之后的新的根节点
        return tempNode;
    }

    AVLTreeNode LRInsertLeftAndRightRotate (AVLTreeNode loseBalanceNode) {
        //先将失衡节点的左节点为轴,进行左旋转
        loseBalanceNode.setLeft(RRInsertLeftRotate(loseBalanceNode.left));
        //再以失衡节点为轴,进行一次右旋转
        return LLInsertRightRotate(loseBalanceNode);
    }

    AVLTreeNode RLInsertRightAndLeftRotate (AVLTreeNode loseBalanceNode) {
        //先将失衡节点的右节点为轴,进行右旋转
        loseBalanceNode.setRight(LLInsertRightRotate(loseBalanceNode.right));
        //再以失衡节点为轴,进行一次左旋转
        return RRInsertLeftRotate(loseBalanceNode);
    }

    public void printTreeDescription(AVLTreeNode root) {
        printNodeDescription(root, "");
    }

    private void printNodeDescription(AVLTreeNode node, String indent) {
        if (node == null) {
            return;
        }

        System.out.println(indent + "节点 " + node.data);

        if (node.left != null) {
            System.out.println(indent + "├── 左孩子 " + node.left.data);
            printNodeDescription(node.left, indent + "│   ");
        }

        if (node.right != null) {
            System.out.println(indent + "└── 右孩子 " + node.right.data);
            printNodeDescription(node.right, indent + "    ");
        }
    }

}

public class AVLTreeTest {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        // 插入节点
        tree.root = tree.insert(tree.root,6);
        tree.root = tree.insert(tree.root,4);
        tree.root = tree.insert(tree.root,8);
        tree.root = tree.insert(tree.root,7);
        tree.root = tree.insert(tree.root,12);
        tree.root = tree.insert(tree.root,14);

        // 打印整棵树
        tree.printTreeDescription(tree.root);
    }
}

测试结果: image.png

节点 8
├── 左孩子 6
│   节点 6
│   ├── 左孩子 4
│   │   节点 4
│   └── 右孩子 7
│       节点 7
└── 右孩子 12
    节点 12
    └── 右孩子 14
        节点 14

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2024/05/02 18:21

  1. 热心网友

    真的厉害啊！牛牛牛

  2. 热心网友

    终于找到了可以跑起来的代码，支持

  1. 1