栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

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

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

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

2.图示

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

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

 

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

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

 

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

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

 

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

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

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

 

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

 

 4.代码实现

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;
        }
    }
}

运行结果如下

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936711.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号