博客

平衡二叉树 是为了防止 二叉排序树会出现树的两端长度不均匀 严重影响查找的性能

package AVLTree;



public class AVLTreeTest {
    public static void main(String[] args) {
        int []x = {10,11,7,6,8,9};
//        int []x = {9,8,7,6,5,4,3};
        String []z = {"阿狸","亚索","鱼人","猴子","琴女","螳螂"};
        binarySortTree avlTree = new binarySortTree();
        for (int i = 0; i < x.length; i++) {
            avlTree.add(x[i],z[i]);
        }
        //树的高度
        System.out.println("树的高度："+avlTree.root.getHeight());
        System.out.println("树的左子树的高度："+avlTree.root.getLeftHeight());
        System.out.println("树的右子树高度："+avlTree.root.getRightHeight());
        System.out.println("当前根节点为："+avlTree.root);
        avlTree.fixOrder();
    }
}
//创建AVL树
class binarySortTree{
    //根节点
    node root;

    //添加节点
    public void add(int id, String name){
        if (root == null){
            root = new node(id,name);
        }else{
            node test = new node(id,name);
            root.add(test);
        }
        //在这里判断 当前树是否符合AVL树 不符合的话 进行相应旋转 使其符合
        //如果当前树的右子树的高度 - 左子树的高度 差值大于1 那么进行左旋转
        if (root.getRightHeight() - root.getLeftHeight() >1){
            //如果当前树的 右子树的左子树的高度 > 右子树的右子树的高度  那么需要把他的右子树进行右旋转 然后再对树左旋转
            if (root.right!=null&&root.right.getLeftHeight() > root.right.getRightHeight()){
                root.right.rightRotate();
                root.leftRotate();
            }else {
                root.leftRotate();
            }
            //这个必须要 因为经过这个判断后 二叉排序树已经平衡了 再向下判断没有必要 还可能出错
            return;
        }
        //如果当前树的左子树的高度 - 右子树的高度 差值大于1 那么进行右旋转  同上
        if (root.getLeftHeight() - root.getRightHeight() > 1){
            if (root.left!=null&&root.left.getRightHeight() > root.left.getLeftHeight()){
                root.left.leftRotate();
                root.rightRotate();
            }else{
                root.rightRotate();
            }
        }
    }
    //二叉排序树中序遍历
    public void fixOrder(){
        if (root == null){
            System.out.println("树空！！！！");
        }else{
            root.fixOrder();
        }

    }
    //搜索目标节点
    public node search(int id){
        if (root == null){
            return null;
        }
        return root.search(id);
    }
    //搜索目标节点的父节点
    public node searchf(int id){
        if (root == null){
            return null;
        }
        node mb = root.search(id);
        return root.searchf(mb);
    }
    //找以目标节点的右子节点为根节点的情况下 值最小的节点 获取并返回他的值 并删除这个最小节点
    public Object[] searchlittle(node node){
        while (node.left!=null){
            node = node.left;
        }
        Object[] mb = {node.id,node.name};
        node delmb = searchf(node.id);
        if (delmb.left==node){
            delmb.left = null;
        }else{
            delmb.right = null;
        }
        return mb;
    }
    //通过id删除目标节点
    public void delete(int id){
        node target = this.search(id);
        node ftarget = this.searchf(target.id);
        if (target != null){
            //目标节点没有子节点的情况
            if (target.left == null && target.right == null) {
                if (ftarget.left == target) {
                    ftarget.left = null;
                }
                if (ftarget.right == target) {
                    ftarget.right = null;
                }
                //目标节点有两个子节点的情况
            }else if (target.left!=null&&target.right!=null){
                Object[] x = searchlittle(target.right);
                target.id = (int) x[0];
                target.name = (String) x[1];

                //那么剩下的就是只有一个子节点的情况
            }else{
                if (ftarget!=null) {
                    if (ftarget.left == target) {
                        if (target.left != null) {
                            ftarget.left = target.left;
                        }
                        if (target.right != null) {
                            ftarget.left = target.right;
                        }
                    } else {
                        if (target.left != null) {
                            ftarget.right = target.left;
                        }
                        if (target.right != null) {
                            ftarget.right = target.right;
                        }
                    }
                }else{
                    if (target.left!=null){
                        root = target.left;
                    }else{
                        root = target.right;
                    }
                }
            }

        }else{
            System.out.println("未找到目标，删除失败！");
        }

    }
}


//创建节点
class node{
    //id
    int id;
    String name;
    node left;
    node right;
    public node(int id,String name){
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    //对树进行右旋转  降低左子树的高度
    public void rightRotate(){
        //创建一个新的节点  并设置他的值为 你当前传入的根节点的值
        node newNode = new node(this.id,this.name);
        //设置新节点的 右子节点 为 当前传入节点的右子节点
        newNode.right = this.right;
        //设置新节点的左子节点为 当前传入节点的左子节点的 右子节点
        newNode.left = this.left.right;
        //设置当前节点的值为 当前节点的左子节点的值
        this.id = this.left.id;
        this.name = this.left.name;
        //设置当前节点的左子节点 为 当前节点的左子节点的左子节点
        this.left = this.left.left;
        //设置当前节点的右子节点为 新节点
        this.right = newNode;
    }

    //对树进行左旋转  降低右子树的高度
    public void leftRotate(){
        //创建一个新的节点  并设置他的值为 你当前传入的根节点的值
        node newNode = new node(this.id,this.name);
        //设置新节点的 左子节点为 当前传入节点的左子节点
        newNode.left = this.left;
        //设置新节点的右子树 为 当前传入节点的右子树的左子树
        newNode.right = this.right.left;
        //替换当前传入节点的值为 当前传入节点的右子节点的值
        this.id = this.right.id;
        this.name = this.right.name;
        //然后设置当前传入节点的右子节点为 当前传入节点的右子节点的右子节点
        this.right = this.right.right;
        //然后设置当前传入节点的左子节点为 新节点
        this.left = newNode;

    }
    //获取左子树的高度
    public int getLeftHeight(){
        if (left==null){
            return 0;
        }
        return left.getHeight();
    }
    //获取右子树的高度
    public int getRightHeight(){
        if (right==null){
            return 0;
        }
        return right.getHeight();
    }
    //获取树的高度
    public int getHeight(){
        //递归 从跟节点向下找 直到当前代表的节点的左右都没有子节点的时候 回溯 根据递归/回溯的次数（也就是向树下走） 每次+1 就得到高度了
        return Math.max(left == null?0: left.getHeight(), right == null?0: right.getHeight())+1;
    }

    //给二叉排序树添加节点
    public void add(node node){
        //如果传入的节点的id 小于 当前节点的值
        if (node.id < this.id){
            //并且当前根节点的左子节点为空 那么当前节点的左子节点就为 穿的的节点
            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);
            }
        }
    }
    //中序遍历二叉排序树
    public void fixOrder(){
        //如果当前节点的左子节点不为空 那么就以当前节点的左子节点为根节点继续找
        if (this.left!=null){
            this.left.fixOrder();
        }
        System.out.println(this);
        //同上
        if (this.right!=null){
            this.right.fixOrder();
        }
    }


    //二叉排序树删除节点

    //搜索目标节点
    public node search(int id){
        if (this.id == id){
            return this;
        }else if (id <this.id){
            return this.left.search(id);
        }else{
            return this.right.search(id);
        }
    }
    //搜索目标节点的父节点
    public node searchf(node mb){
        if (this.left!=null&&this.left==mb||this.right!=null&&this.right==mb ){
            return this;
        }
        if (mb.id < this.id){
            return this.left.searchf(mb);
        }
        if (mb.id > this.id){
            return this.right.searchf(mb);
        }
        return null;
    }

}

二分查找

public class BinarySearch {
    public static void main(String[] args) {
        int []x = {1,4,6,8,20,98};
        System.out.println(binarySearch(x,0,x.length-1,8));
        System.out.println(binarySearch(x,0,x.length-1,80));
        System.out.println("非递归二分查找");
        System.out.println(binarySearch(x,8));
        System.out.println(binarySearch(x,80));
    }
    //二分查找 非递归
    public static int binarySearch(int []arr,int findValue){
        int left = 0;
        int right = arr.length-1;
        while (left<=right){
            int mid = (left + right)/2;
            if (findValue < arr[mid]){
                right = mid-1;
            }else if(findValue > arr[mid]){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    //二分查找  需要传入 数组（一定要是有序的）  数组的左边界  数组的右边界 要查找的值
    public static int binarySearch(int []arr,int left,int right,int findValue){
        //判断左边界和右边界是否符合要求 当不符合要求时证明找不到目标 直接返回异常
        if (left>right){
            return -1;
        }
        //找中心点
        int mid = (left + right)/2;
        //用中心点跟目标比较 找目标的位置方向
        if (findValue < arr[mid]){
            return binarySearch(arr,left,mid-1,findValue);
        }else if(findValue > arr[mid]){
            return binarySearch(arr,mid+1,right,findValue);
        }else{
            return mid;
        }
    }

}