AVL二叉树的左旋和右旋保持平衡

以你之姓@ 2023-10-02 19:39 43阅读 0赞

1.什么是AVL二叉树  
平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

2.图示

![03a7a0eec7764a3eb9056e9ec24dec64.png][]

3.二叉树的左旋和右旋保持平衡

当我们左子树和右子树的深度大于1时，这个二叉树就不是平衡二叉树，我们就需要左旋或右旋来让二叉树保持平衡，如下图非平衡二叉树

![63f5d7c7a170434bb803991792de6de8.png][]

上述二叉树根节点3的左子树深度为2，而右子树深度为4，他们相差为二，所以不是平衡二叉树，需要通过左旋来保持平衡

1.创建一个新节点targetNode,将根节点的值赋给targetNode

![a74a8924b31949e590ed5733c7e33d75.png][]

2.将新节点的左子节点指向原根节点的左子节点

![4b2c7276f6464f298a61e0b5a282e925.png][]

3.将targetNode的右子节点指向根节点3的右节点7的左节点5

![206c45a91d5f4f9687c78bc072e09e82.png][]

4.将根节点的值赋值为他的右子节点的值

![baba9f58eeff47e99da73fc1525625a3.png][]

5.将原根节点7的右子节点指向原根节点7的右子节点7的右子节点9

![bf1f854df67f489097e3aefd0327e8b5.png][]

6.将当前根节点7的左子节点指向targetNode节点3

![cc2d941c44674507ae81ed813935451b.png][]

7.节点7因为没有被引用从而被虚拟机回收，得到左旋如下

![3a0c46a0f2094e21bec5c5070aa2be27.png][]

4.代码实现

/**
     * @author wangli
     * @data 2022/5/30 15:37
     * @Description:
     */
    public class testTree {
        @Test
        public void AVLTree(){
            binaryTree binaryTree = new binaryTree();
            TreeNode node1 = new TreeNode(3);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(7);
            TreeNode node4 = new TreeNode(5);
            TreeNode node5 = new TreeNode(9);
            TreeNode node6 = new TreeNode(8);
            TreeNode node7 = new TreeNode(10);
            node1.left=node2;
            node1.right=node3;
            node3.left=node4;
            node3.right=node5;
            node5.left=node6;
            node5.right=node7;
            System.out.println("binaryTree.getDeep(node2) = " + binaryTree.getDeep(node2));
            System.out.println("binaryTree.getDeep(node3) = " + binaryTree.getDeep(node3));
            binaryTree.leftRotate(node1);
            System.out.println("node1 = " + node1);
            System.out.println("node1.left = " + node1.left);
            System.out.println("node1.right = " + node1.right);
            System.out.println("node1.left.left = " + node1.left.left);
            System.out.println("node1.left.right = " + node1.left.right);
    
        }
        /**
         * 二叉树结点
         */
    
        public static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
    
            public TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
    
            public TreeNode(int val) {
                this.val = val;
            }
    
            @Override
            public String toString() {
                return "TreeNode{" +
                        "val=" + val +
                        '}';
            }
        }
    
        public  class binaryTree {
            private TreeNode root;
            //查找结点
             int num = 0;
             //查询是否有该节点
            public  boolean isExistTreeNode(TreeNode root, TreeNode target) {
                if (root == null) return false;
                if (root.val == target.val) return true;
                num++;
                return target.val > root.val ? isExistTreeNode(root.right, target) : isExistTreeNode(root.left, target);//利用二叉排序树特点进行查找
            }
    
            //求二叉树的深度
            public  int getDeep(TreeNode root) {
                if (root == null) return 0;
                int leftDeep = getDeep(root.left);
                int rightDeep = getDeep(root.right);
                return leftDeep > rightDeep ? leftDeep + 1 : rightDeep + 1;
            }
    
            //左旋
            public  void leftRotate(TreeNode root) {
                //1.创建targetNode节点，将root节点的值赋给他
                TreeNode targetNode = new TreeNode(root.val);
                //2.将targetNode的左子节点指向root节点的左子节点
                targetNode.left=root.left;
                //3.将targetNode的右子节点指向root节点的右节点的左节点
                targetNode.right=root.right.left;
                //4.将root节点的值赋值为root节点的右节点的值
                root.val=root.right.val;
                //5.将root节点的右子针指向root节点的右节点的右节点
                root.right=root.right.right;
                //6.将root的左子节点指向targetNode节点
                root.left=targetNode;
            }
        }
    }

运行结果如下

![ea42a73e94ac44ef83117546a70e091e.png][]

[03a7a0eec7764a3eb9056e9ec24dec64.png]: https://img-blog.csdnimg.cn/03a7a0eec7764a3eb9056e9ec24dec64.png
[63f5d7c7a170434bb803991792de6de8.png]: https://img-blog.csdnimg.cn/63f5d7c7a170434bb803991792de6de8.png
[a74a8924b31949e590ed5733c7e33d75.png]: https://img-blog.csdnimg.cn/a74a8924b31949e590ed5733c7e33d75.png
[4b2c7276f6464f298a61e0b5a282e925.png]: https://img-blog.csdnimg.cn/4b2c7276f6464f298a61e0b5a282e925.png
[206c45a91d5f4f9687c78bc072e09e82.png]: https://img-blog.csdnimg.cn/206c45a91d5f4f9687c78bc072e09e82.png
[baba9f58eeff47e99da73fc1525625a3.png]: https://img-blog.csdnimg.cn/baba9f58eeff47e99da73fc1525625a3.png
[bf1f854df67f489097e3aefd0327e8b5.png]: https://img-blog.csdnimg.cn/bf1f854df67f489097e3aefd0327e8b5.png
[cc2d941c44674507ae81ed813935451b.png]: https://img-blog.csdnimg.cn/cc2d941c44674507ae81ed813935451b.png
[3a0c46a0f2094e21bec5c5070aa2be27.png]: https://img-blog.csdnimg.cn/3a0c46a0f2094e21bec5c5070aa2be27.png
[ea42a73e94ac44ef83117546a70e091e.png]: https://img-blog.csdnimg.cn/ea42a73e94ac44ef83117546a70e091e.png