平衡二叉树（AVL）（Java实现）

待我称王封你为后i 2023-07-14 10:32 8阅读 0赞

## 平衡二叉树（AVL）（Java实现） ##

#### 1.二叉搜索树存在的问题 ####

虽然二叉树搜索在查询，删除，添加上具有一定的优势，但是在一些情况下的效率也特别低。比如下面的这个二叉搜索树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]  
我们发现，它的右子树非常地高，这就失去了二叉树本来具备的高效查找的功能，它的查找效率甚至比链表还低，因为每遍历到一个节点时还要判断其是否有左子树或右子树。为了避免这种情况，就引入了平衡二叉树。

#### 2.平衡二叉树（AVL）的定义 ####

首先，平衡二叉树是特殊的二叉搜索树。其次，平衡二叉树的左子树和右子树高度的绝对值不超过1.

#### 3.求二叉树的高度 ####

递归，直接看代码不太好理解，如果一边画图一边理解的话很容易就理清楚了。

/** * 二叉树的高度 * @return */
        public int height(){ 
            return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
        }

理解了上面的代码，同样地，左右子树的高度也很好求了。

/** * 左子树的高度 * @return */
        public int leftHeight(){ 
            if (left==null){ 
                return 0;
            }
            return left.height();
        }
    
        /** * 右子树的高度 * @return */
        public int rightHeight(){ 
            if (right==null){ 
                return 0;
            }
            return right.height();
        }

我们来测试一下，这棵二叉树的高度、左子树高度、右子树高度.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]

public class AVLTreeDemo { 
        public static void main(String[] args) { 
            int[] arr={ 4,3,6,5,7,8};
            //创建一个AVLTree对象
            AVLTree avlTree = new AVLTree();
            //添加节点
            for (int i = 0; i < arr.length; i++) { 
                avlTree.add(new Node(arr[i]));
            }
            System.out.println("中序遍历");
            avlTree.infixOrder();
            System.out.println("没有平衡处理前");
            System.out.println("树的高度:"+avlTree.getRoot().height());
            System.out.println("左子树的高度:"+avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度:"+avlTree.getRoot().rightHeight());
        }
    }

输出结果如下，确实和我们看到的图片一样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 2]

#### 4.BST左旋转形成AVL ####

**左旋转发生的条件**：当添加完一个节点后，右子树的高度-左子树的高度>1，发生左旋转。

/** * 左旋转方法 */
        public void leftRotate(){ 
            //创建新的节点，以当前根节点的值为值
            Node newNode = new Node(this.value);
            //把新的节点的左子树设置成当前节点的左子树
            newNode.left=this.left;
            //把新的节点的右子树设置成当前节点的右子树的左子树
            newNode.right=this.right.left;
            //把当前节点的值替换成右子节点的值
            this.value=this.right.value;
            //把当前节点的右子树设置成当前节点的右子树的右子树
            this.right=this.right.right;
            //把当前节点的左子节点设置成新的节点
            this.left=newNode;
        }
    	 //添加节点的方法
        public void add(Node node){ 
            if (node==null){ 
                return;
            }
            //判断传入的节点的值，和当前子树的节点的值的关系
            if (node.value<this.value){ 
                //如果当前节点的左子节点为空
                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){ 
           		leftRotate();//左旋转
            }
        }

继续测试一把现在二叉树的高度，我们发现，BTS已经自平衡成为了AVL。左旋转之后，原二叉树变成了这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 4]

#### 5.BST右旋转形成AVL ####

**右旋转发生的条件：** 当添加完一个节点后，左子树的高度-右子树的高度>1，发生右旋转。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 5]

/** * 右旋转方法 */
        public void rightRotate(){ 
            //创建新的节点，以当前根节点的值为值
            Node newNode = new Node(this.value);
            //把新的节点的右子树设置为当前节点的右子树
            newNode.right=this.right;
            //把新的节点的左子树设置为当前节点的左子树的右子树
            newNode.left=this.left.right;
            //把当前节点的值替换成左子节点的值
            this.value=this.left.value;
            //把当前节点的左子树设置成当前节点的左子树的左子树
            this.left=this.left.left;
            //把当前节点的右子节点设置成新的节点
            this.right=newNode;
        }
        //添加节点的方法
        public void add(Node node){ 
            if (node==null){ 
                return;
            }
            //判断传入的节点的值，和当前子树的节点的值的关系
            if (node.value<this.value){ 
                //如果当前节点的左子节点为空
                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 (this.right!=null&&this.right.rightHeight()<this.right.leftHeight()){ //先对右子树进行旋转 }*/
               leftRotate();//左旋转
            }
            //当添加完一个节点后，左子树的高度-右子树的高度>1，发生右旋转
            if (leftHeight()-rightHeight()>1){ 
                rightRotate();//右选择
            }
        }

测试一把：

public class AVLTreeDemo { 
        public static void main(String[] args) { 
            //int[] arr={4,3,6,5,7,8};
            int[] arr={ 10,12,8,9,7,6};
            //创建一个AVLTree对象
            AVLTree avlTree = new AVLTree();
            //添加节点
            for (int i = 0; i < arr.length; i++) { 
                avlTree.add(new Node(arr[i]));
            }
            System.out.println("中序遍历");
            avlTree.infixOrder();
            //System.out.println("没有平衡处理前");
            System.out.println("平衡处理后");
            System.out.println("树的高度:"+avlTree.getRoot().height());
            System.out.println("左子树的高度:"+avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度:"+avlTree.getRoot().rightHeight());
        }
    }

运行结果如下，确实已经平衡了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 6]  
我们看一下右旋转后的二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 7]

#### 6.双旋转 ####

//当添加完一个节点后，右子树的高度-左子树的高度>1，发生左旋转
            if (rightHeight()-leftHeight()>1){ 
                //如果当前节点的右子树的左子树的高度大于它的右子树的右子树的高度
                if (this.right!=null&&this.right.rightHeight()<this.right.leftHeight()){ 
                    //先对右子树进行右旋转
                    this.right.rightRotate();
                    //在对当前节点进行左旋转
                    this.leftRotate();
                }else { 
                    this.leftRotate();//左旋转
                }
                return;//必须要return
            }
            //当添加完一个节点后，左子树的高度-右子树的高度>1，发生右旋转
            if (leftHeight()-rightHeight()>1){ 
                //如果它的左子树的右子树高度大于它的左子树的高度
                if (this.left!=null&&this.left.rightHeight()>this.left.leftHeight()){ 
                    //先对当前节点的左子树左旋转
                    this.left.leftRotate();
                    //再对当前节点进行右旋转
                    this.rightRotate();
                }else { 
                    //直接进行右旋转即可
                    this.rightRotate();
                }
                return;
            }

#### 7.总结 ####

所有的代码都在这里了，最重要的思想还是掌握如何进行旋转，其实把每一个步骤都搞清楚了，代码实现起来就很简单的。

package Day42;
    
    /** * @Author Zhongger * @Description 平衡二叉树-+- * @Date 2020.3.14 */
    public class AVLTreeDemo { 
        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};//双旋转
            //创建一个AVLTree对象
            AVLTree avlTree = new AVLTree();
            //添加节点
            for (int i = 0; i < arr.length; i++) { 
                avlTree.add(new Node(arr[i]));
            }
            System.out.println("中序遍历");
            avlTree.infixOrder();
            //System.out.println("没有平衡处理前");
            System.out.println("平衡处理后");
            System.out.println("树的高度:"+avlTree.getRoot().height());
            System.out.println("左子树的高度:"+avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度:"+avlTree.getRoot().rightHeight());
        }
    }
    class AVLTree{ 
        private Node root;
    
        public Node getRoot() { 
            return root;
        }
    
        /** * 返回以node为根节点的二叉排序树的最小节点，并删除这个最小的节点 * @param node * @return */
        public int deleteRightTreeMin(Node node){ 
            Node target=node;
            //循环查找左节点，就会找到最小值
            while (target.left!=null){ 
                target=target.left;
            }
            //这是target就指向了最小节点
            deleteNode(target.value);//删除之
            return target.value;
        }
    
        //查找要删除的节点
        public Node search(int value){ 
            if (root==null){ 
                return null;
            }else { 
                return root.search(value);
            }
        }
        //查找要删除的节点的父节点
        public Node searchParent(int value){ 
            if (root==null){ 
                return null;
            }else { 
                return root.searchParent(value);
            }
        }
    
        public void deleteNode(int value){ 
            if (root==null){ 
                return;
            }else { 
                Node targetNode = search(value);
                if (targetNode==null){ //未找到要删除的节点
                    return;
                }
                //如果targetNode没有父节点
                if (root.left==null&&root.right==null){ 
                    root=null;
                }
                //遭到targetNode的父节点
                Node parentNode = searchParent(value);
                //如果要删除的节点是叶子节点
                if (targetNode.left==null&&targetNode.right==null){ 
                    //判断targetNode是父节点的左子节点还是右子节点
                    if ((parentNode.left!=null)&&(parentNode.left.value==value)){ 
                        parentNode.left=null;
                    }else if ((parentNode.right!=null)&&(parentNode.right.value==value)){ 
                        parentNode.right=null;
                    }
                }else if (targetNode.left!=null&&targetNode.right!=null){ //删除有两棵子树的节点
                    int minVal = deleteRightTreeMin(targetNode.right);
                    targetNode.value=minVal;
                }else { //删除只有一棵子树的节点
                    if (targetNode.left!=null){ //有左子树
                        if (parentNode!=null){ 
                            //如果targetNode是parentNode的左子节点
                            if (parentNode.left.value==value){ 
                                parentNode.left=targetNode.left;
                            }else { //targetNode是parentNode的右子节点
                                parentNode.right=targetNode.left;
                            }
                        }else { 
                            root=targetNode.left;
                        }
    
                    }else { //有右子树
                        if (parentNode!=null){ 
                            if (parentNode.left.value==value){ 
                                parentNode.left=targetNode.right;
                            }else { 
                                parentNode.right=targetNode.right;
                            }
                        }else { 
                            root=targetNode.right;
                        }
    
                    }
                }
            }
        }
    
        //添加节点的方法
        public void add(Node node){ 
            if (root==null){ 
                root=node;//如果root为空，直接让root指向node
            }else { 
                root.add(node);
            }
        }
    
        //中序遍历
        public void infixOrder(){ 
            if (root!=null){ 
                root.infixOrder();
            }
            else { 
                System.out.println("二叉排序树为空，无法遍历");
            }
        }
    }
    
    
    class Node{ //节点
        int value;
        Node left;
        Node right;
    
        public Node(int value) { 
            this.value = value;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        /** * 左旋转方法 */
        public void leftRotate(){ 
            //创建新的节点，以当前根节点的值为值
            Node newNode = new Node(this.value);
            //把新的节点的左子树设置成当前节点的左子树
            newNode.left=this.left;
            //把新的节点的右子树设置成当前节点的右子树的左子树
            newNode.right=this.right.left;
            //把当前节点的值替换成右子节点的值
            this.value=this.right.value;
            //把当前节点的右子树设置成当前节点的右子树的右子树
            this.right=this.right.right;
            //把当前节点的左子节点设置成新的节点
            this.left=newNode;
        }
    
        /** * 右旋转方法 */
        public void rightRotate(){ 
            //创建新的节点，以当前根节点的值为值
            Node newNode = new Node(this.value);
            //把新的节点的右子树设置为当前节点的右子树
            newNode.right=this.right;
            //把新的节点的左子树设置为当前节点的左子树的右子树
            newNode.left=this.left.right;
            //把当前节点的值替换成左子节点的值
            this.value=this.left.value;
            //把当前节点的左子树设置成当前节点的左子树的左子树
            this.left=this.left.left;
            //把当前节点的右子节点设置成新的节点
            this.right=newNode;
        }
    
        /** * 左子树的高度 * @return */
        public int leftHeight(){ 
            if (left==null){ 
                return 0;
            }
            return left.height();
        }
    
        /** * 右子树的高度 * @return */
        public int rightHeight(){ 
            if (right==null){ 
                return 0;
            }
            return right.height();
        }
    
        /** * 二叉树左右子树的高度 * @return */
        public int height(){ 
            return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
        }
    
    
        /** * 查找要删除的节点 * @param value 要删除的节点的值 * @return 如果找到返回该节点，否则返回null */
        public Node search(int value){ 
            if (this.value==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);
            }
        }
    
        /** * 查找要删除节点的父节点 * @param value 要删除的节点的值 * @return 如果找到就返回该节点，否则就返回null */
        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){ 
                    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 (this.right!=null&&this.right.rightHeight()<this.right.leftHeight()){ 
                    //先对右子树进行右旋转
                    this.right.rightRotate();
                    //在对当前节点进行左旋转
                    this.leftRotate();
                }else { 
                    this.leftRotate();//左旋转
                }
                return;//必须要return
            }
            //当添加完一个节点后，左子树的高度-右子树的高度>1，发生右旋转
            if (leftHeight()-rightHeight()>1){ 
                //如果它的左子树的右子树高度大于它的左子树的高度
                if (this.left!=null&&this.left.rightHeight()>this.left.leftHeight()){ 
                    //先对当前节点的左子树左旋转
                    this.left.leftRotate();
                    //再对当前节点进行右旋转
                    this.rightRotate();
                }else { 
                    //直接进行右旋转即可
                    this.rightRotate();
                }
                return;
            }
        }
    
        //中序遍历
        public void infixOrder(){ 
            if (this.left!=null){ 
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right!=null){ 
                this.right.infixOrder();
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20230529/96188c539ea84b3bacec065f1485c3f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]: /images/20230529/34ec1904528a4c03936b726cb53bc10a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 2]: /images/20230529/83980d7ae09349bb989d42a4d2291928.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 3]: /images/20230529/2da7290a478849108136b426b25bad89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 4]: /images/20230529/400fad5f653444519317ba3b71ae96c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 5]: /images/20230529/0c12529dfe7749a6b7d211342654446f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 6]: /images/20230529/af0d8793edfe4ccab85eb3450460fb47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 7]: /images/20230529/0b0e7032ab9f462fb4429e2d7f90ba2c.png