X16数据结构部分09

• 平衡二叉树概述以及左旋转实现思路
• 树的高度求解
• 左右旋转的方法
• 实现双旋转
• 总目录

平衡二叉树概述以及左旋转实现思路

/*
    平衡二叉树(AVL树)概述
        解决了二叉排序树的一些问题
        举一个栗子
        给你1个数列{1,2,3,4,5,6}
        让你构造1棵二叉排序树
            根据左小右大原则
            你就会构造出来只有1直向右子树延申的
            所有节点最多只有1棵节点的二叉树
            也就是左子树全部为空

        此时你会发现
        你所构造的二叉排序树更像是1棵单链表
            这样的话，插入和删除速度不会受影响
            但查询速度会很慢
            甚至比单链表还要慢
            因为在查询的时候
            还需要判断左子树是否有节点

    解决方案
        平衡二叉树
        特点
            前提是二叉排序树
            是1棵空树或2棵子树的高度差绝对值不超过1
            并且左右2子树都是1棵平衡二叉树
            常见的实现方法有红黑树，替罪羊树，AVL算法，伸展树等；

    需求
        给你1个数列，要求创建1棵平衡二叉树
        {4,3,6,5,7,8}

    左旋转思路分析
        一旦右子树的高度 - 左子树的高度 > 1
        就采用左旋转
        降低右子树的高度

    如何进行左旋转
        1. 创建1个新节点，value等于当前根节点的值，创建1个当前指针，指向根节点
        2. 把新节点((NODE)value = 4)的左子树设置为当前节点((ROOT)value = 4)的左子树
        3. 把新节点的右子树设置为当前节点的右子树的左子树，如果没有指向null就行了
        4. 把当前节点的值换成右子节点的值((ROOT)value = 6)，注意只是换，还没开始移动呢
        5. 把当前节点的右子树设置为当前节点右子树的右子树((ROOT)value = 6).rightNode = ROOT.r.r
        6. 当前节点的左子树指向新节点((NODE)value = 4)

        左旋转过后
            明显地发现原先根节点指向的右子树
            这条线已经断掉了
            实际上原来的右子树已经被销毁了
            新出现相同的节点只是副本而已
            想想有一种悲伤的感觉
        代码实现的话
            我会复用之前的Node1节点类
     */

树的高度求解

// 将以下方法写进Node类，创建AVLT平衡二叉树类，将原先的二叉排序树类复制进class AVLT，这里就不展示源码了
	/**
     * 返回左子树的高度
     * 递归出口
     *
     * @return 左子树的高度
     */
    public int leftTreeHeight() {
        if (leftNode == null) {
            return 0;
        }
        return leftNode.maximumHeightOfTree();
    }

    /**
     * 返回右子树的高度
     * 递归出口
     *
     * @return 右子树的高度
     */
    public int rightTreeHeight() {
        if (rightNode == null) {
            return 0;
        }
        return rightNode.maximumHeightOfTree();
    }

    /**
     * 树的最大高度
     *
     * @return 当前二叉树的最大高度
     */
    public int maximumHeightOfTree() {
        /*
        程序进入方法体
        递归左子树和右子树
        再取最大值
        还要+1的原因是当前自己
        也要加上
         */
        return Math.max(leftNode == null ? 0 : leftNode.maximumHeightOfTree(),
                rightNode == null ? 0 : rightNode.maximumHeightOfTree()) + 1;
    }

左右旋转的方法

/**
     * 左旋转方法
     */
    public void rotateLeft() {
        /*
        程序开始进行左旋转操作
        
        1. 创建1个新节点，value等于当前根节点的值，创建1个当前指针，指向根节点
        2. 把新节点((NODE)value = 4)的左子树设置为当前节点((ROOT)value = 4)的左子树
        3. 把新节点的右子树设置为当前节点的右子树的左子树，如果没有指向null就行了
        4. 把当前节点的值换成右子节点的值((ROOT)value = 6)，注意只是换，还没开始移动呢
        5. 把当前节点的右子树设置为当前节点右子树的右子树((ROOT)value = 6).rightNode = ROOT.r.r
        6. 当前节点的左子树指向新节点((NODE)value = 4)

        此时
        默认value是根节点
        leftNode是根节点的左子树
         */
        
        Node1 newNode = new Node1(value);
        newNode.leftNode = leftNode;
        newNode.rightNode = rightNode.leftNode;
        value = rightNode.value;
        rightNode = rightNode.rightNode;
        leftNode = newNode;
    }

    /**
     * 右旋转方法
     */
    public void rotateRight() {
        /*
        右旋转实现思路
            1. 创建1个新节点，为当前根节点的值((NEW_NODE)value = 10)
            2. 新节点的右子树((NEW_NODE).r)设置为当前节点的右子树((ROOT).r)
            3. 新节点的左子树((NEW_NODE).l)设置为当前节点左子树的右子树((ROOT).l.r)
            4. 把当前根节点的值((ROOT).value)换成左子树节点的值((ROOT).l.value)
            5. 当前节点的左子树设置为当前节点左子树的左子树
            6. 把当前节点的右子树设置为新节点

            此时根节点的左子树节点已经被销毁了
            因为没有任何引用指向该节点
         */
        Node1 newNode = new Node1(value);
        newNode.rightNode = rightNode;
        newNode.leftNode = leftNode.rightNode;
        value = leftNode.value;
        leftNode = leftNode.leftNode;
        rightNode = newNode;
    }
    
    /**
     * 插入节点的方法
     *
     * @param node 需要插入的节点
     */
    public void insertNode(Node1 node) {
        if (node == null) {
            return;
        }
        /*
        程序运行到此处
        此时可以判断插入的节点和根节点的关系
        this.value表示根节点的值
         */
        if (node.value < this.value) {
            if (this.leftNode == null) {
                /*
                程序运行到此处
                说明当前插入的节点比根节点的值小
                并且根节点的左子树位空
                直接插入即可
                 */
                this.leftNode = node;
            } else {
                this.leftNode.insertNode(node);
            }
        } else {
            /*
            程序运行到此处
            说明当前节点比根节点大
            需要插入到右子树
             */
            if (this.rightNode == null) {
                this.rightNode = node;
            } else {
                this.rightNode.insertNode(node);
            }
        }
        /*
        程序运行到此处
        应该判断左子树和右子树的高度
        如果右子树的高度 - 左子树的高度 > 1
        应该左旋转
        如果左子树的高度 - 右子树的高度 > 1
        应该右旋转
         */
        if (rightTreeHeight() - leftTreeHeight() > 1) {
            /*
            程序运行到此处
            先不考虑那么多
            直接左旋转
             */
            rotateLeft();
        }
        if (leftTreeHeight() - rightTreeHeight() > 1) {
            rotateRight();
        }
    }

实现双旋转

/*
    这里分析几个特殊的情况比如给你1个数组
    {10,11,7,6,8,9}
    构造完二叉排序树
    此时满足右旋转的条件
    但进行右旋转过后
    仍然不是1棵平衡二叉树

    双旋转思路分析和条件
    1. 满足右旋转的条件
    2. 左子树的右子树高度 > 右子树高度
    3. 先对当前这个节点的左节点进行左旋转
    4. 再对当前根节点进行右旋转即可
     */
     /**
     * 插入节点的方法
     *
     * @param node 需要插入的节点
     */
    public void insertNode(Node1 node) {
        if (node == null) {
            return;
        }
        /*
        程序运行到此处
        此时可以判断插入的节点和根节点的关系
        this.value表示根节点的值
         */
        if (node.value < this.value) {
            if (this.leftNode == null) {
                /*
                程序运行到此处
                说明当前插入的节点比根节点的值小
                并且根节点的左子树位空
                直接插入即可
                 */
                this.leftNode = node;
            } else {
                this.leftNode.insertNode(node);
            }
        } else {
            /*
            程序运行到此处
            说明当前节点比根节点大
            需要插入到右子树
             */
            if (this.rightNode == null) {
                this.rightNode = node;
            } else {
                this.rightNode.insertNode(node);
            }
        }
        /*
        程序运行到此处
        应该判断左子树和右子树的高度
        如果右子树的高度 - 左子树的高度 > 1
        应该左旋转
        如果左子树的高度 - 右子树的高度 > 1
        应该右旋转
        注意这里需要判断是否满足双旋转的条件
         */
        if (rightTreeHeight() - leftTreeHeight() > 1) {
            if (rightNode != null && rightNode.leftTreeHeight() > rightNode.rightTreeHeight()) {
                rightNode.rotateRight();
                rotateLeft();
            }else {
                rotateLeft();
            }
            return;
        }

        if (leftTreeHeight() - rightTreeHeight() > 1) {
            if (leftNode != null && leftNode.rightTreeHeight() > leftNode.leftTreeHeight()) {
                leftNode.rotateLeft();
                rotateRight();
            }else {
                rotateRight();
            }
        }
    }

总目录