平衡二叉树(AVL)的原理和java实现

妖狐艹你老母 2023-06-09 11:25 23阅读 0赞

### 目录 ###

*  什么是AVL
 *  左旋转
 *  右旋转
 *  双旋转
 *  java实现

# 什么是AVL #

平衡二叉树（AVL：下面我们都统称AVL）也是一种二叉排序树，但是它的左子树和右子树的高度差不超过1，可以认为是二叉排序树优化之后的一种数据结构。  
**（如果对二叉排序树不了解的，可以看我之前的博客[二叉排序树的创建和节点删除][Link 1]）**  
那么，为什么会产生AVL这种数据结构呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]  
如果，我们对\{1,2,3,4,5,6\}这样一个数组来创建二叉排序树，那么就会是上面图片的样子，那么它存在什么问题呢？

1.  左子树全部为空，从形式上看，更像一个单链表.
2.  插入速度没有影响
3.  查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，因为每次还需要比较左子、树，其查询速度比单链表还慢。

# 左旋转 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]  
对于右子树的高度比左子树的高度大于1的时候，我们就需要进行左旋转，具体步骤如下：  
\* 1.新建一个节点，并根节点的值赋值给新节点  
\* 2.新节点的左子树设置为根节点的左子树  
\* 3.新节点的右子树设置为根节点的右子树的左子树  
\* 4.将根节点的值修改为根节点的右子树的值  
\* 5.将新节点设置为根节点的左子树  
\* 6.将根子树的右子树的右子树设置为根节点的右子树

# 右旋转 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]  
同样的道理，当左子树的高度比右子树的高度大于1的时候，就需要进行右旋转。  
\* 1.新建一个节点，并将根节点的值赋值给新节点  
\* 2.新节点的右子树设置为根节点的右子树  
\* 3.新节点的左子树设置为根节点的左子树的右子树  
\* 4.将根节点的值修改为根节点的左子树的值  
\* 5.将根节点的右子树设置为新节点  
\* 6.将根节点的左子树设置为根节点的左子树的左子树

# 双旋转 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]  
当加入节点9的时候，满足右旋转的条件，但是进行了右旋转之后，可以发现仍然不是平衡二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 4]  
此时就需要使用双旋转了，即就需要先对根节点的左子树进行左旋转，然后再进行右旋转，才能够调整为平衡二叉树。

为什么需要这么做呢？其实看图就可以想象出来：

1.  对需要右旋转的二叉树，如果当根节点的左子树的右子树高度大于根节点的左子树的左子树时，进行右旋转之后反而会使得右子树的高度比左子树的高度大于1，仍然不是平衡二叉树；
2.  而当根节点的左子树的右子树高度不大于根节点的左子树的左子树时，直接进行右旋转就可以调整为平衡二叉树了；
3.  所以，当根节点的左子树的右子树高度大于根节点的左子树的左子树时，需要先对根节点的左子树进行左旋转，使得根节点的左子树的右子树高度不大于根节点的左子树的左子树。

# java实现 #

其实，代码跟二叉排序树的代码很多是一样的，只是在添加或删除节点的时候，要判断是否需要进行旋转。

package com.hong.tree;
    
    public class AVLTree { 
        private Node root = null;
        private int order = 0;
    
        /** * 左旋转 * 1.新建一个节点，并根节点的值赋值给新节点 * 2.新节点的左子树设置为根节点的左子树 * 3.新节点的右子树设置为根节点的右子树的左子树 * 4.将根节点的值修改为根节点的右子树的值 * 5.将新节点设置为根节点的左子树 * 6.将根子树的右子树的右子树设置为根节点的右子树 */
        public void leftRotate(Node root){ 
            Node newNode = new Node(root.val);
            newNode.left = root.left;
            newNode.right = root.right.left;
            root.val = root.right.val;
            root.left = newNode;
            root.right = root.right.right;
        }
    
        /** * 右旋转 * 1.新建一个节点，并将根节点的值赋值给新节点 * 2.新节点的右子树设置为根节点的右子树 * 3.新节点的左子树设置为根节点的左子树的右子树 * 4.将根节点的值修改为根节点的左子树的值 * 5.将根节点的右子树设置为新节点 * 6.将根节点的左子树设置为根节点的左子树的左子树 * @param root */
        public void rightRotate(Node root){ 
            Node newNode = new Node(root.val);
            newNode.right = root.right;
            newNode.left = root.left.right;
            root.val = root.left.val;
            root.right = newNode;
            root.left = root.left.left;
        }
    
        /** * 获取左子树的高度 * @return // */
        public int leftHeight(){ 
            if (root.left == null){ 
                return 0;
            } else{ 
                return getHeight(root.left);
            }
        }
    
        /** * 返回右子树的高度 * @return */
        public int rightHeight(){ 
            if (root.right == null){ 
                return 0;
            } else{ 
                return getHeight(root.right);
            }
        }
    
        /** * 返回以当前节点为根节点的树的高度 * @param root * @return */
        private int getHeight(Node root){ 
            return Math.max(root.left == null ? 0 : getHeight(root.left),
                    root.right == null ? 0 : getHeight(root.right)) + 1;
        }
    
        /** * 节点添加 * @param node */
        public void add(Node node){ 
            // 第一次添加元素时
            if (root == null){ 
                root = node;
                return;
            }
    
            Node temp = root;
            while (temp != null){ 
                if (node.val <= temp.val){ 
                    if (temp.left == null){ 
                        temp.left = node;
                        break;
                    } else{ 
                        temp = temp.left;
                    }
                } else{ 
                    if (temp.right == null){ 
                        temp.right = node;
                        break;
                    } else{ 
                        temp = temp.right;
                    }
                }
            }
    
            // 当右子树的高度大于左子树的高度时，需要进行左旋转
            if (rightHeight() - leftHeight() > 1){ 
                // 当根节点的右子树的左子树高度大于根节点的右子树的右子树时，需要先对根节点的右子树进行右旋转
                if (getHeight(root.right.left) - getHeight(root.right.right) > 0){ 
                    rightRotate(root.right);
                }
                leftRotate(root);
            }
            // 当左子树的高度大于右子树的高度时，需要进行右旋转
            if (leftHeight() - rightHeight() > 1){ 
                // 当根节点的左子树的右子树高度大于根节点的左子树的左子树时，需要先对根节点的左子树进行左旋转
                if (getHeight(root.left.right) - getHeight(root.left.left) > 0){ 
                    leftRotate(root.left);
                }
                rightRotate(root);
            }
        }
    
        /** * 打印整颗二叉树 */
        public void show(){ 
            if (root == null){ 
                System.out.println("二叉树为空！！！");
                return;
            }
    
            showRecusion(root);
    
        }
    
        /** * 打印的递归体 * @param node */
        private void showRecusion(Node node){ 
            // 一直向左递归，直到左叶子节点
            if (node.left != null){ 
                showRecusion(node.left);
            }
            // 然后开始回溯，打印父节点，接着打印右叶子节点，刚好符合二叉排序树的排序
            System.out.println(String.format("第一个%d数值为：%d", order, node.val));
            order ++;
            if (node.right != null){ 
                showRecusion(node.right);
            }
        }
    
        /** * 删除节点 * @param node */
        public void del(Node node){ 
            Node parent = root;
            Node temp = null;
            if (root.val == node.val){  // 需要先判断删除的节点是否为根节点
                if (root.left == null && root.right == null){ 
                    root = null;
                } else if (root.left != null && root.right != null){ 
                    Node left = root.left;
                    root = root.right;
                    temp = root.left;
                    while (temp.left != null){ 
                        temp = temp.left;
                    }
                    temp.left = left;
                }
                return;
            } else if (root.val > node.val){ 
                temp = root.left;
            } else { 
                temp = root.right;
            }
            // 迭代找到想删除的节点
            while (temp != null){ 
                if (temp.val == node.val){ 
                    break;
                } else if (temp.val > node.val){ 
                    parent = temp;
                    temp = temp.left;
                } else{ 
                    parent = temp;
                    temp = temp.right;
                }
            }
            if (temp == null){ 
                System.out.println("该节点不存在，无法删除");
                return;
            }
            // 如果要删除的为叶子节点，则直接删除即可
            if (temp.left == null && temp.right == null){ 
                if (parent.left == temp){ 
                    parent.left = null;
                } else{ 
                    parent.right = null;
                }
            } else if (temp.left != null && temp.right != null) { 
                // 删除节点有两个子树
                // 将右子树代替要删除节点的位置，然后左子树放在右子树的最底层左子树
                // 因为整颗左子树都是比右子树小的，所以左子树需要移动到右子树最小的子树上，即右子树上最左的子树
                if (parent.left == temp){ 
                    parent.left = temp.right;
                } else{ 
                    parent.right = temp.right;
                }
                Node left = temp.left;
                temp = temp.right;
                while (temp.left != null) { 
                    temp = temp.left;
                }
                temp.left = left;
            } else{ 
                // 删除的节点只有一颗子树
                // 直接将子树替换其位置即可
                if (temp.right != null){ 
                    if (parent.left == temp){ 
                        parent.left = temp.right;
                    } else{ 
                        parent.left = temp.right;
                    }
                } else{ 
                    if (parent.left == temp){ 
                        parent.left = temp.left;
                    } else{ 
                        parent.left = temp.left;
                    }
                }
            }
    
            // 当右子树的高度大于左子树的高度时，需要进行左旋转
            if (rightHeight() - leftHeight() > 1){ 
                // 当根节点的右子树的左子树高度大于根节点的右子树的右子树时，需要先对根节点的右子树进行右旋转
                if (getHeight(root.right.left) - getHeight(root.right.right) > 0){ 
                    rightRotate(root.right);
                }
                leftRotate(root);
            }
            // 当左子树的高度大于右子树的高度时，需要进行右旋转
            if (leftHeight() - rightHeight() > 1){ 
                // 当根节点的左子树的右子树高度大于根节点的左子树的左子树时，需要先对根节点的左子树进行左旋转
                if (getHeight(root.left.right) - getHeight(root.left.left) > 0){ 
                    leftRotate(root.left);
                }
                rightRotate(root);
            }
        }
    
        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 avl = new AVLTree();
            for (int a: arr){ 
                avl.add(new Node(a));
            }
            avl.show();
            System.out.println(avl.leftHeight());
            System.out.println(avl.rightHeight());
        }
    }
    
    
    /** * 节点类 */
    class Node{ 
        public int val;
        public Node left = null;
        public Node right = null;
    
        public Node(int val){ 
            this.val = val;
        }
    }

代码已经上传至[github][]

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114414173.jpg]

[Link 1]: https://blog.csdn.net/sgyuanshi/article/details/102614863
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: /images/20230531/80cb30f89e894e55a13d4d900ac06de8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/d22fdece2c8040e8bc4d794de0ab0915.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]: /images/20230531/83cbb7a442f34eb48b34c03f94818c5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]: /images/20230531/5f1c9c25a808403689ec0960fe12c3c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 4]: /images/20230531/2771133ad0fe4e9db8599493afc6c926.png
[github]: https://github.com/SGyuanshi/DataStructures/blob/master/src/com/hong/tree/AVLTree.java
[20200430114414173.jpg]: /images/20230531/8448de0d287943019c477affcd91b8e4.png