[数据结构与算法]Java数据结构和算法---平衡二叉树

平衡二叉树
????????给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.

上边BST 存在的问题分析:
? ? ? ? 1左子树全部为空，从形式上看，更像一个单链表.
? ? ? ? 2插入速度没有影响
? ? ? ? 3查询速度明显降低(因为需要依次比较), 不能发挥BST 的优势，因为每次还需要比较左子树，其查询速度比 单链表还慢
? ? ? ? 4解决方案-平衡二叉树(AVL)

平衡二叉树基本介绍:
????????1.平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
? ? ? ? 2.具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

单旋转(左旋转)
? ? ? ? 根据{4,3,6,5,7,8}创建出对应的平衡二叉树
????????对节点A进行左旋转的步骤
? ? ? ? ? ? ? ? ①将A 节点的 右节点 的 左节点 ，指向 A节点
? ? ? ? ? ? ? ? ②将 A节点的右节点，指向A 节点的右节点的左节点

detail:

?
单旋转(右旋转)
?????????创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
? ? ? ? ?对节点A进行右旋转的步骤
? ? ? ? ? ? ? ? ①将A 节点的 左节点 的 右节点 ，指向 A节点
? ? ? ? ? ? ? ? ②将 A节点的左节点，指向A 节点的左节点的右节点

?detail:

?双旋转
????????前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
????????int[] arr = { 10, 11, 7, 6, 8, 9 }; ?运行原来的代码可以看到，并没有转成 AVL树.
????????int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树
问题分析{ 10, 11, 7, 6, 8, 9 }

? ? ? ? ?①当符合右旋转的条件时
? ? ? ? ?②若它的左子树的右子树的高度大于它的右子树的高度
? ? ? ? ?③先对当前这个结点的左节点进行左旋转
? ? ? ? ?④再对当前结点进行右旋转
代码:

package ASDF;

public class AVLT {
    public static void main(String[] args) {
        //int []arr = {4,3,6,5,7,8};
        int []arr = {10, 11, 7, 6, 8, 9};
        AVLTree avlTree = new AVLTree();
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }
        avlTree.midOrder();
        System.out.println(avlTree.getRoot().height());
        System.out.println(avlTree.getRoot().LeftHeight());
        System.out.println(avlTree.getRoot().RighttHeight());
        System.out.println(avlTree.getRoot().left.left.value);
    }
}

class AVLTree{
    private Node root;



    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    //添加结点
    public void add(Node node){
        if(root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
    public void midOrder(){
        if(root!=null){
            root.midOrder();
        }else {
            System.out.println("empty!");
        }
    }
    public Node search(int value){
        if(root==null){
            return null;
        }else {
            return root.Search(value);
        }
    }
    public Node parentSearch(int value){
        if(root==null){
            return null;
        }else {
            return root.searchParent(value);
        }
    }

    //返回

    /**
     *
     * @param node 当做二叉排序树的根节点
     * @return 返回以node为根节点的二叉排序树的最小结点的值
     */
    public int delRigthTreeMin(Node node){
       Node t = node;
        while (t.left!=null){
            t=t.left;
        }
        delNode(t.getValue());
        return t.getValue();
    }
    public void delNode(int value){
        if(root==null){
            return;
        }else {
            //1.先找到要删除的节点
            Node targetNode = search(value);
            if (targetNode == null) {
                return;
            }
            //若当前这个二叉排序树只有一个结点
            if(root.getLeft()==null&&root.getRight()==null){
                root=null;
                return;
            }
            //找targetNode的父节点
           Node parent = parentSearch(value);
            //若要删除的是叶子结点
            if(targetNode.getLeft()==null&&targetNode.getRight()==null){
                //判断targetNode是父结点的左还是右子结点
                if(parent.getLeft()!=null&&parent.getLeft().getValue()==value){
                    parent.setLeft(null);
                }else if(parent.getRight()!=null&&parent.getRight().getValue()==value) {
                    parent.setRight(null);
                }
            }else if(targetNode.getLeft()!=null&&targetNode.getRight()!=null){//删除有两颗子树的结点
                int i = delRigthTreeMin(targetNode.right);
                targetNode.setValue(i);
            }else {//删除只有一颗子树的结点
                //若要删除的结点有左子节点
                if (targetNode.left!=null){
                    if(parent!=null){
                        if(parent.getLeft().getValue()==value){//若targetNode是parent的左子节点
                            parent.left=targetNode.left;
                        }else if(parent.right==targetNode){
                            parent.right=targetNode.left;
                        }
                    }else {
                        root=targetNode.left;
                    }

                }else {
                    if(parent!=null){
                        if(parent.left.getValue()==value){//若targetNode是parent的左子节点
                            parent.left=targetNode.right;
                        }else if(parent.right==targetNode){
                            parent.right=targetNode.right;
                        }
                    }else {
                        root=targetNode.right;
                    }

                }
            }

        }
    }
}
class Node {
    int value;//结点权值
    Node left;//指向左子节点
    Node right;//指向右子节点


    //返回当前结点的(以该结点为根节点的树的高度)
    public int height(){
        return Math.max(left==null?0: left.height(),right==null?0: right.height())+1;
    }
    //返回左子树的高度
    public int LeftHeight(){
       if(left==null){
           return 0;
       }else {
           return left.height();
       }
    }
    //返回右子树的高度
    public int RighttHeight(){
        if(right==null){
            return 0;
        }else {
            return right.height();
        }
    }

    //左旋转
    public void leftRotate(){
        //创建新结点(以当前根节点的值)
        Node node = new Node(value);
        //把新的结点的左子树 设置成当前结点的左子树
        node.left=left;
        //把新的结点的右子树 设置成当前结点的右子树的左子树
        node.right=right.left;
        //把当前结点的值 替换成右子结点的值
        this.value = right.value;
        //把当前结点的右子树 设置成当前结点的右子树的右子树
        this.right = right.right;
        //把当前结点的左子树(左子节点) 设置为新的结点
        left=node;
    }
    //右旋转
    public void rightRotate(){
        //创建新结点(以当前根节点的值)
        Node node = new Node(value);
        //把新的结点的右子树 设置成当前结点的右子树
        node.right=right;
        //把新的结点的左子树 设置成当前结点的左子树的右子树
        node.left=left.right;
        //把当前结点的值 替换成左子结点的值
        this.value = left.value;
        //把当前结点的左子树 设置成当前结点的左子树的左子树
        this.left = left.left;
        //把当前结点的右子树(右子节点) 设置为新的结点
        right=node;
    }

    //双旋转
    public void Rotate(){
        //创建新结点(以当前根节点的值)
        Node node = new Node(value);
        //把新的结点的右子树 设置成当前结点的右子树
        node.right=right;
        //把新的结点的左子树 设置成当前结点的左子树的右子树
        node.left=left.right;
        //把当前结点的值 替换成左子结点的值
        this.value = left.value;
        //把当前结点的左子树 设置成当前结点的左子树的左子树
        this.left = left.left;
        //把当前结点的右子树(右子节点) 设置为新的结点
        right=node;
    }
    //查找要删除的结点
    public Node Search(int value){
        if(value==this.value){
            return this;
        }else if(value<this.value){
            if(this.left==null){
                return null;
            }
            return this.left.Search(value);
        }else {
            if(this.right==null){
                return null;
            }
            return this.right.Search(value);
        }
    }
    //查找要删除结点的父结点
    public Node searchParent(int value){
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
                return this;
        }else {
            //若查找的值 小于当前结点的值 且当前结点的左子节点不为空
            if(value<this.value&&this.left!=null){
                return this.left.searchParent(value);
            }else if(value>=this.value&&this.right!=null){
                return this.right.searchParent(value);
            }else{
                return null;//没有父节点
            }
        }

    }

    //添加结点的方法
    //递归的形式添加结点 注意需要满足二叉排序树的要求
    public void add(Node node){
        if (node==null){
            return;
        }
        if(node.value<this.value){
            if (this.left==null){//若当前结点 左子节点为null
                this.left = node;
            }else{
                this.left.add(node);//递归的向左子树添加
            }
        }else {//添加的结点的值>当前结点的值
            if(this.right==null){
                this.right=node;
            }else{
                this.right.add(node);//递归的向右子树添加
            }
        }
        //当添加完一个结点后 若:右子树的高度-左子树的高度>1，左旋转
        if((RighttHeight()-LeftHeight())>1){
            //若它右子树的左子树的高度大于它的右子树的高度
            if(right!=null&&right.LeftHeight()>right.RighttHeight()){
                //先对当前结点的左子树 左旋转
                right.rightRotate();
                //再对当前结点进行右旋转
                leftRotate();
            }else {
                leftRotate();
            }
            return;
        }
        if((LeftHeight()-RighttHeight())>1){
               //若它左子树的右子树的高度大于它的左子树的高度
            if(left!=null&&left.RighttHeight()>left.LeftHeight()){
                //先对当前结点的左子树 左旋转
                left.leftRotate();
                //再对当前结点进行右旋转
                rightRotate();
            }else {
                rightRotate();
            }
        return;
        }
    }

    public void midOrder(){
        if(this.left!=null){
            this.left. midOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right. midOrder();
        }
    }

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }


}