0091 平衡二叉树

 

 

 

 

 

/*
 * 平衡二叉树
 * 1.也叫平衡二叉搜索树，也成为AVL树，可以保证查询效率较高
 * 2.特点：是一颗空树或左右子树的高度差的绝对值不超过1，且左右两个子树都是一颗平衡二叉树
 *   常见实现方法有：红黑树，AVL，替罪羊树，Treap，伸展树等
 * 
 * 应用——单旋转（左旋转）
 * 给定数列{4,3,6,5,7,8}，创建出对应的平衡二叉树
 * 左旋转
 * 1.创建一个新结点newNode,值等于当前根节点的值（4）
 * 2.把新结点的左子树设置成当前节点的左子树 
 *         newNode.left = left
 * 3.把新结点的右子树设置为当前结点的右子树的左子树
 *         newNode.right = right.left
 * 4.把当前结点的值换为右子节点的值
 *         value = right.value
 * 5.把当前结点的右子树设为右子树的右子树
 *         right = right.right
 * 6.把当前结点的左子树设为新结点
 *         left = newNode
 * 
 * 应用——单旋转（右旋转）
 * 给定数列{10,12,8,9,7,6}，创建出对应的平衡二叉树
 * 右旋转
 * 1.创建一个新结点newNode,值等于当前根节点的值（10）
 * 2.把新结点的右子树设置成当前节点的右子树 
 *         newNode.right = right
 * 3.把新结点的左子树设置为当前结点的左子树的右子树
 *         newNode.left = left.right
 * 4.把当前结点的值换为左子节点的值
 *         value = left.value
 * 5.把当前结点的左子树设为左子树的左子树
 *         left = left.left
 * 6.把当前结点的右子树设为新结点
 *         right = newNode
 * 
 * 应用——双旋转
 * 1.满足左（右）旋转条件，但左（右）旋转后仍不是平衡二叉树
 * 2.如果右（左）子树的左（右）子树高度大于右（左）子树的高度
 *   先对当前结点的右（左）子节点进行左旋转
 *   再对当前结点进行左（右）旋转
 */
public class AVL_ {
    public static void main(String[] args) {
        //int[] arr = {4,3,6,5,7,8};
        //int[] arr = {10,12,8,9,7,6};
        int[] arr = {10,11,7,6,8,9};
        //创建一个AVL对象
        AVL avl = new AVL();
        //添加节点
        for(int i = 0;i < arr.length;i++) {
            avl.add(new Node(arr[i]));
        }
        
        //中序遍历
        avl.infixOrder();
        
        //树的高度
        System.out.println("树的高度=" + avl.getRoot().height());
        System.out.println("左子树的高度=" + avl.getRoot().leftHeight());
        System.out.println("右子树的高度=" + avl.getRoot().rightHeight());
        System.out.println("当前根节点=" + avl.getRoot());
    }
}

//创建AVL树
class AVL{
    private Node root;
    
    public Node getRoot() {
        return root;
    }
    
    //添加节点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        }else {
            root.add(node);
        }
    }
    
    //中序遍历
    public void infixOrder() {
        if (root == null) {
            System.out.println("树空，无法遍历");
        }else {
            root.infixOrder();
        }
    }
}

//创建Node
class Node{
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    
    //返回左子树高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }
    
    //返回右子树高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }
    
    //返回以该结点为根节点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }
    
    //左旋转方法
    private void leftRotate() {
        //1.创建一个新结点newNode,值等于当前根节点的值（4）
        Node newNode = new Node(value);
        //2.把新结点的左子树设置成当前节点的左子树 
        newNode.left = left;
        //3.把新结点的右子树设置为当前结点的右子树的左子树
        newNode.right = right.left;
        //4.把当前结点的值换为右子节点的值
        value = right.value;
        //5.把当前结点的右子树设为右子树的右子树
        right = right.right;
        //6.把当前结点的左子树设为新结点
        left = newNode;
    }
    
    //右旋转方法
    private void rightRotate() {
        //1.创建一个新结点newNode,值等于当前根节点的值（10）
        Node newNode = new Node(value);
        //2.把新结点的右子树设置成当前节点的右子树 
        newNode.right = right;
        //3.把新结点的左子树设置为当前结点的左子树的右子树
        newNode.left = left.right;
        //4.把当前结点的值换为左子节点的值
        value = left.value;
        //5.把当前结点的左子树设为左子树的左子树
        left = left.left;
        //6.把当前结点的右子树设为新结点
        right = newNode;
    }
    
    @Override
    public String toString() {
        return "Node [value=" + value + "]";
    }

    //添加
    //递归形式添加节点，满足二叉排序树要求
    public void add(Node node) {
        if (node == null) {
            return;
        }
        
        //判断传入节点的值，和当前子树的根节点的值的关系
        //添加节点值小于当前节点值
        if (node.value < this.value) {
            //如果当前左子节点为null
            if (this.left == null) {
                this.left = node;
            }else {
                //向左递归
                this.left.add(node);
            }
        //添加节点值大于当前节点值
        }else {
            if (this.right == null) {
                this.right = node;
            }else {
                //向右递归
                this.right.add(node);
            }
        }
        
        //当添加完一个结点后，如果 (右子树高度 - 左子树高度) > 1，左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果右子树的左子树高度大于右子树的高度
            if (right != null && right.leftHeight() > right.rightHeight()) {
                //先对当前结点的右子节点进行右旋转
                right.rightHeight();
                //再对当前结点进行左旋转
                leftRotate();
            }else {
                leftRotate();//左旋转
            }
            return;
        }
        
        //当添加完一个结点后，如果 (左子树高度 - 右子树高度) > 1，右旋转
        if (leftHeight() - rightHeight() > 1) {
            //如果左子树的右子树高度大于左子树的高度
            if (left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前结点的左子节点进行左旋转
                left.leftRotate();
                //再对当前结点进行右旋转
                rightRotate();
            }else {
                rightRotate();//右旋转
            }
        }
    }
    
    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

/*
 * 多叉树（了解）
 * 1.在二叉树中，每个结点有数据项，最多有两个子节点
 *   如果允许每个结点可以有更多的数据项和更多的子节点，就是多叉树
 * 2.如2-3树，2-3-4树....多叉树通过重新组织结点，减少树的高度，对二叉树进行了优化
 * 
 * B树
 * B树通过重新组织结点，减少树的高度，且减少I/O读写次数来提升效率
 * 1.文件系统及数据库系统的设计者利用了磁盘预读原理，将一个结点的大小设为等于一个页
 *   （页的大小通常为4k)，这样每个结点只需一次I/O就可以完全载入
 * 2.将树的度M设置为1024，在600亿个元素中最多只需4次I/O操作就可以读取想要的元素
 *   B树广泛应用于文件存储系统以及数据库系统中
 *   
 * 2-3树
 * 是最简单的B树结构，具有以下特点：
 * 1.2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件）
 * 2.有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
 * 3.有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
 * 4.2-3树是由二节点和三节点构成的树
 * 
 * 2-3-4树：概念和2-3类似，由二节点，三节点和四节点构成
 * 
 * B树
 * 1.B树的阶：节点的最多子节点个数。如2-3树的阶是3，2-3-4树的阶是4
 * 2.B树的搜索：从根节点开始，对节点内的关键字（有序）序列进行二分查找
 *      如果命中则结束，否则进入查询关键字所属范围的子节点，重复，
 *   直到所对应的子指针为空，或已是叶子节点
 * 3.关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据
 * 4.搜索有可能在非叶子节点结束
 * 5.其搜索性能等价于在关键字全集内做一次二分查找
 * 
 * B+树
 * B+树是B树的变体，也是一种多路搜索树
 * 1.B+树的搜索与B树基本相同，区别是B+树只要达到叶子节点才命中
 *      其性能也等价于在关键字全集做一次二分查找
 * 2.所有关键字都出现在叶子节点的链表中（即数据只能在叶子节点）
 *   且链表中的关键字恰好是有序的
 * 3.非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储数据的数据层
 * 4.适用于文件索引系统
 * 
 * B*树
 * B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针
 * 1.B*树定义了非叶子节点关键字个数至少为（2/3）*M，即块的最低使用率为2/3
 *   而B+树块的最低使用率为1/2
 * 2.B*树分配节点的概率比B+树要低，空间使用率更高
 * 
 */