数据结构之平衡二叉树及Java实现

绝地灬酷狼 2022-05-27 13:15 156阅读 0赞

## 一、平衡二叉树的基本介绍 ##

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap等。最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

平衡二叉树是对二叉排序树的优化，防止二叉排序树在最坏情况（插入顺序恰好是有序的）下平均查找时间为n，二叉排序树在此时形如一个单链表，而平衡二叉树查找元素的次数不超过树的深度，时间复杂度为logN 。

## 二、平衡二叉树的实现 ##

[参考资料——java数据结构与算法之平衡二叉树(AVL树)的设计与实现][java_AVL]

实现代码：

public class AVLTree<T extends Comparable>{
        
    
    
        class Node<T>{
        
            private T data = null;
            int height = 0;
            private Node left;
            private Node right;
    
            public Node(T data){
                this.data = data;
            }
            public Node(Node<T> left, Node<T> right, T data) {
                this(left,right,data,0);
            }
    
            public Node(Node<T> left, Node<T> right, T data, int height) {
                this.left=left;
                this.right=right;
                this.data=data;
                this.height = height;
            }
        }
        /** The tree root. */
        public Node<T> root;
    
    
        public boolean isEmpty() {
            return root==null;
        }
    
        public int size() {
            return size(root);
        }
    
        @SuppressWarnings("unchecked")
        public int size(Node<T> subtree){
            if(subtree==null){
                return 0;
            }else {
                return size(subtree.left) + 1 + size(subtree.right);
            }
        }
    
        public int height() {
            return height(root);
        }
    
    
        /**
         * @param p
         * @return
         */
        public int height(Node<T> p){
            return p == null ? -1 : p.height;
        }
    
    
    
        public String preOrder() {
            String sb=preOrder(root);
            if(sb.length()>0){
                //去掉尾部","号
                sb=sb.substring(0,sb.length()-1);
            }
            return sb;
        }
    
        /**
         * 先根遍历
         * @param subtree
         * @return
         */
        public String preOrder(Node<T> subtree){
            StringBuilder sb =new StringBuilder();
            if (subtree!=null) {
                //先访问根结点
                sb.append(subtree.data).append(",");
                //访问左子树
                sb.append(preOrder(subtree.left));
                //访问右子树
                sb.append(preOrder(subtree.right));
            }
            return sb.toString();
        }
    
    
        public String inOrder() {
            String sb=inOrder(root);
            if(sb.length()>0){
                //去掉尾部","号
                sb=sb.substring(0,sb.length()-1);
            }
            return sb;
        }
    
        /**
         * 中根遍历
         * @param subtree
         * @return
         */
        private String inOrder(Node<T> subtree){
            StringBuilder sb =new StringBuilder();
            if (subtree!=null) {
                //访问左子树
                sb.append(inOrder(subtree.left));
                //访问根结点
                sb.append(subtree.data).append(",");
                //访问右子树
                sb.append(inOrder(subtree.right));
            }
            return sb.toString();
        }
    
        public String postOrder() {
            String sb=postOrder(root);
            if(sb.length()>0){
                //去掉尾部","号
                sb=sb.substring(0,sb.length()-1);
            }
            return sb;
        }
    
        /**
         * 后根遍历
         * @param subtree
         * @return
         */
        private String postOrder(Node<T> subtree){
            StringBuilder sb =new StringBuilder();
            if (subtree!=null){
                //访问左子树
                sb.append(postOrder(subtree.left));
                //访问右子树
                sb.append(postOrder(subtree.right));
                //访问根结点
                sb.append(subtree.data).append(",");
            }
            return sb.toString();
        }
    
    
        /**
         * 插入方法
         * @param data
         */
        public void insert(T data) {
            if (data==null){
                throw new RuntimeException("data can\'t not be null ");
            }
            this.root=insert(data,root);
        }
    
        private Node<T> insert(T data , Node<T> p){
    
            //说明已没有孩子结点,可以创建新结点插入了.
            if(p==null){
                p=new Node<T>(data);
            }
    
            int result=data.compareTo(p.data);
    
            if(result<0){
       //向左子树寻找插入位置
                p.left=insert(data,p.left);
    
                //插入后计算子树的高度,等于2则需要重新恢复平衡,由于是左边插入,左子树的高度肯定大于等于右子树的高度
                if(height(p.left)-height(p.right)==2){
                    //判断data是插入点的左孩子还是右孩子
                    if(data.compareTo(p.left.data)<0){
                        //进行LL旋转
                        p=singleRotateLeft(p);
                    }else {
                        //进行左右旋转
                        p=doubleRotateWithLeft(p);
                    }
                }
            }else if (result>0){
       //向右子树寻找插入位置
                p.right=insert(data,p.right);
    
                if(height(p.right)-height(p.left)==2){
                    if (data.compareTo(p.right.data)<0){
                        //进行右左旋转
                        p=doubleRotateWithRight(p);
                    }else {
                        //进行RR旋转
                        p=singleRotateRight(p);
                    }
                }
            }
            else
                ;//if exist do nothing
            //重新计算各个结点的高度
            p.height = Math.max( height( p.left ), height( p.right ) ) + 1;
    
            return p;//返回根结点
        }
    
    
        /**
         * 删除方法
         * @param data
         */
        public void remove(T data) {
            if (data==null){
                throw new RuntimeException("data can\'t not be null ");
            }
            this.root=remove(data,root);
        }
    
        /**
         * 删除操作
         * @param data
         * @param p
         * @return
         */
        private Node<T> remove(T data,Node<T> p){
    
            if(p ==null)
                return null;
    
            int result=data.compareTo(p.data);
    
            //从左子树查找需要删除的元素
            if(result<0){
                p.left=remove(data,p.left);
    
                //检测是否平衡
                if(height(p.right)-height(p.left)==2){
                    Node<T> currentNode=p.right;
                    //判断需要那种旋转
                    if(height(currentNode.left)>height(currentNode.right)){
                        //RL
                        p=doubleRotateWithRight(p);
                    }else{
                        //RR
                        p=singleRotateRight(p);
                    }
                }
    
            }
            //从右子树查找需要删除的元素
            else if(result>0){
                p.right=remove(data,p.right);
                //检测是否平衡
                if(height(p.left)-height(p.right)==2){
                    Node<T> currentNode=p.left;
                    //判断需要那种旋转
                    if(height(currentNode.right)>height(currentNode.left)){
                        //LR
                        p=doubleRotateWithLeft(p);
                    }else{
                        //LL
                        p=singleRotateLeft(p);
                    }
                }
            }
            //已找到需要删除的元素,并且要删除的结点拥有两个子节点
            else if(p.right!=null&&p.left!=null){
    
                //寻找替换结点
                p.data=findMin(p.right).data;
    
                //移除用于替换的结点
                p.right = remove( p.data, p.right );
            }
            else {
                //只有一个孩子结点或者只是叶子结点的情况
                p=(p.left!=null)? p.left:p.right;
            }
    
            //更新高度值
            if(p!=null)
                p.height = Math.max( height( p.left ), height( p.right ) ) + 1;
            return p;
        }
    
    
        /**
         * 查找最小值结点
         * @param p
         * @return
         */
        private Node<T> findMin(Node<T> p){
            if (p==null)//结束条件
                return null;
            else if (p.left==null)//如果没有左结点,那么t就是最小的
                return p;
            return findMin(p.left);
        }
    
        public T findMin() {
            return findMin(root).data;
        }
    
        public T findMax() {
            return findMax(root).data;
        }
    
        /**
         * 查找最大值结点
         * @param p
         * @return
         */
        private Node<T> findMax(Node<T> p){
            if (p==null)
                return null;
            else if (p.right==null)//如果没有右结点,那么t就是最大的
                return p;
            return findMax(p.right);
        }
    
    
    
        public boolean contains(T data) {
            return data != null && contain(data, root);
        }
    
        public boolean contain(T data , Node<T> subtree){
    
            if (subtree==null)
                return false;
    
            int result =data.compareTo(subtree.data);
    
            if (result<0){
                return contain(data,subtree.left);
            }else if(result>0){
                return contain(data,subtree.right);
            }else {
                return true;
            }
        }
    
        public void clear() {
           this.root=null;
        }
    
        /**
         * 左左单旋转(LL旋转) w变为x的根结点, x变为w的右子树
         * @param x
         * @return
         */
        private Node<T> singleRotateLeft(Node<T> x){
            //把w结点旋转为根结点
            Node<T> w=  x.left;
            //同时w的右子树变为x的左子树
            x.left=w.right;
            //x变为w的右子树
            w.right=x;
            //重新计算x/w的高度
            x.height=Math.max(height(x.left),height(x.right))+1;
            w.height=Math.max(height(w.left),x.height)+1;
            return w;//返回新的根结点
        }
    
        /**
         * 右右单旋转(RR旋转) x变为w的根结点, w变为x的左子树
         * @return
         */
        private Node<T> singleRotateRight(Node<T> w){
    
            Node<T> x=w.right;
    
            w.right=x.left;
            x.left=w;
    
            //重新计算x/w的高度
            x.height=Math.max(height(x.left),w.height)+1;
            w.height=Math.max(height(w.left),height(w.right))+1;
    
            //返回新的根结点
            return x;
        }
    
        /**
         * 左右旋转(LR旋转) x(根) w y 结点 把y变成根结点
         * @return
         */
        private Node<T> doubleRotateWithLeft(Node<T> x){
            //w先进行RR旋转
            x.left=singleRotateRight(x.left);
            //再进行x的LL旋转
            return singleRotateLeft(x);
        }
    
        /**
         * 右左旋转(RL旋转)
         * @param w
         * @return
         */
        private Node<T> doubleRotateWithRight(Node<T> w){
            //先进行LL旋转
            w.right=singleRotateLeft(w.right);
            //再进行RR旋转
            return singleRotateRight(w);
        }
    
    
        private void printTree( Node<T> t )
        {
            if( t != null )
            {
                printTree( t.left );
                System.out.println( t.data );
                printTree( t.right );
            }
        }
    
    
        /**
         * 测试
         * @param arg
         */
        public  static void main(String arg[]){
    
            AVLTree<Integer> avlTree=new AVLTree<Integer>();
    
            for (int i = 1; i <18 ; i++) {
                avlTree.insert(i);
            }
    
            avlTree.printTree(avlTree.root);
            //删除11,8以触发旋转平衡操作
            avlTree.remove(11);
            avlTree.remove(8);
    
            System.out.println("================");
    
            avlTree.printTree(avlTree.root);
            System.out.println("findMin:"+avlTree.findMin());
            System.out.println("findMax:"+avlTree.findMax());
            System.out.println("15 exist or not : " + avlTree.contains(15) );
            System.out.println("先根遍历:"+avlTree.preOrder());
            System.out.println("中根遍历:"+avlTree.inOrder());
            System.out.println("后根遍历:"+avlTree.postOrder());
    
        }
    
    }

[java_AVL]: https://blog.csdn.net/javazejian/article/details/53892797