二叉平衡树左右双旋(思维导图大纲+图解看不懂来砍我！！！)

爱被打了一巴掌 2022-11-21 04:08 81阅读 0赞

### 文章目录 ###

*   *  为什么要使用二叉平衡树？
     *  平衡树的定义
     *  思路大纲
     *   *  节点类
         *  AVL树类
     *  什么时候需要左旋？
     *  什么时候需要右旋
     *  为什么要双旋？
     *  测试双旋方法
     *   *  完整代码放上

## 为什么要使用二叉平衡树？ ##

为了降低树的高度 避免出现树退化成数组的形式  
如这样  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]

## 平衡树的定义 ##

![在这里插入图片描述][20201030104205901.png_pic_center]  
划重点  
**任意节点的子树的高度差都小于等于1**  
**任意节点的子树的高度差都小于等于1**  
**任意节点的子树的高度差都小于等于1**

如果超过1 即为不平衡树 需要旋转了

## 思路大纲 ##

先看一下这两个类 为后面做准备

### 节点类 ###

方法：

1.  获取树的高度(**重点掌握 递归求树的高度**)
2.  获取左子树高度
3.  获取右子树高度
4.  根据value值插入结点方法
5.  遍历方法

获取树的高度

class Node { 
        Node left;
        Node right;
        int value;
    
    
       /** * 获取树的高度 */
        public int getHeight() { 
            return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
        }
    
        /** * 左子树可能为空 * * @return */
        public int leftHeight() { 
            if (left == null) { 
                return 0;
            } else { 
                return left.getHeight();
            }
        }
    
        /** * 右子树可能为空 * * @return */
        public int rightHeight() { 
            if (right == null) { 
                return 0;
            } else { 
                return right.getHeight();
            }
        }
    
     
        /** * 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点 * * @param node 待插入的节点 */
        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);
                }
            }
         
          
        }
    
    
        /** * 前序遍历方法 */
        public void preface() { 
            System.out.print(this.value + " ");
            if (this.left != null) { 
                this.left.preface();
            }
            if (this.right != null) { 
                this.right.preface();
            }
        }
    
    
        /** * 中序遍历方法 */
        public void midface() { 
            if (this.left != null) { 
                this.left.midface();
            }
            System.out.print(this.value + " ");
            if (this.right != null) { 
                this.right.midface();
            }
        }
    
    
        public Node(int value) { 
            this.value = value;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

### AVL树类 ###

一系列遍历方法 重点放在节点类里

class AvlTree { 
        Node root;
    
    
        /** * 二叉树添加节点方法 为空直接替换根节点 * * @param node */
        public void add(Node node) { 
            if (root == null) { 
                root = node;
            } else { 
                root.add(node);
            }
    
        }
    
    
        /** * 中序遍历树 */
        public void midlist() { 
            if (root != null) { 
                root.midface();
                System.out.println();
            }
        }
    
        /** * 前序遍历树 */
        public void prelist() { 
            if (root != null) { 
                root.preface();
                System.out.println();
            }
        }
    
    
    }

## 什么时候需要左旋？ ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 2]

如图 在没添加8节点前 还是一个平衡树 但添加过后

此时我们看到左子树的高度为1 右子树的高度为3

也就是右子树高度-左子树高度>1 超过1个单位时 我们就需要往左旋转 来保持平衡了

思路截一下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 3]  
配合图一起看  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 4]

/** * 左旋方法 */
        public void leftRotate() { 
            Node newnode = new Node(value);
            //将新节点左子树设置为当前节点左子树
            newnode.left = left;
            //新节点右子树设置为当前节点右子树的左子树
            newnode.right = right.left;
            //root的值替换为他的右子节点的值
            value = right.value;
            //root的右边指向右子树的右子节点
            right = right.right;
            //root的左边指向新节点newnode
            left = newnode;
        }

注意 我们左旋方法的添加是在节点添加方法里实现的

即 每添加一个节点 就判断左右树的高度 所以不用担心后面的子树 子树的子树之类的情况哦！

左旋过后 该树平衡

//add方法添加左旋代码
            //计算左子树的高度
            int l = leftHeight();
            //计算右子树的高度
            int r = rightHeight();
            //当他们高度相差2时 就需要旋转
            if (l - r > 1) { 
            	leftRotate();
            }

## 什么时候需要右旋 ##

也就是左子树高度-右子树高度>1 超过1个单位时 我们就需要往右旋转 来保持平衡了

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 7]

/** * 右旋方法 */
        public void rightRotate() { 
            Node newnode = new Node(value);
            newnode.right = right;
            newnode.left = left.right;
            value = left.value;
            left = left.left;
            right = newnode;
        }

同样的 也要在add方法里添加判断的条件

## 为什么要双旋？ ##

看图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 8]  
我们可以数一数 新的左右子树的 高度 发现是左边为3 右边为1 明显相差2 所以就引出了双旋

![在这里插入图片描述][20201030112949122.png_pic_center]  
我们以10为根节点 判断如果左子树大于右子树 则右旋 否则左旋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 10]

这是整个add方法的步骤

/** * 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点 * * @param node 待插入的节点 */
        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);
                }
            }
    
            //计算左子树的高度
            int l = leftHeight();
            //计算右子树的高度
            int r = rightHeight();
    
    
    
            //当他们高度相差2时 就需要旋转
            if (l - r > 1) { 
                //双旋的情况 左子树的左子树的高度小于左子树的右子树的高度
                if (left.leftHeight() < left.rightHeight()) { 
                    //要将左子树左旋 再将整个树右旋
                    left.leftRotate();
                    rightRotate();
                } else { 
                    rightRotate();
                }
            }
    
            if (r - l > 1) { 
                //双旋的情况 右子树的左子树的高度大于右子树的左子树的高度
                if (right.leftHeight() > right.rightHeight()) { 
                    //要将右子树右旋 再将整个树左旋
                    right.rightRotate();
                    leftRotate();
                } else { 
                    leftRotate();
                }
            }
        }

## 测试双旋方法 ##

//对双旋做个测试 写入
     public static void main(String[] args) { 
            int[] arr = { 7, 6, 10, 9, 8, 11};
            AvlTree tree = new AvlTree();
            for (int i : arr) { 
                tree.add(new Node(i));
            }
            System.out.println("整个树的高度为"+tree.root.getHeight());
            System.out.println("左子树高度为"+tree.root.leftHeight());
            System.out.println("右子树高度为"+tree.root.rightHeight());
            //前序
            tree.prelist();
            //中序
            tree.midlist();
    
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 11]  
打印结果

整个树的高度为3  
左子树高度为2  
右子树高度为2  
9 7 6 8 10 11  
6 7 8 9 10 11

### 完整代码放上 ###

package cn.bb.study;
    
    
    /** * @program: datastructure * @description: 平衡二叉树 * @author: sharpbb * @create: 2020-10-29 08:11 **/
    
    public class Demo { 
    //对双旋做个测试 写入
     public static void main(String[] args) { 
            int[] arr = { 7, 6, 10, 9, 8, 11};
            AvlTree tree = new AvlTree();
            for (int i : arr) { 
                tree.add(new Node(i));
            }
            System.out.println("整个树的高度为"+tree.root.getHeight());
            System.out.println("左子树高度为"+tree.root.leftHeight());
            System.out.println("右子树高度为"+tree.root.rightHeight());
            //前序
            tree.prelist();
            //中序
            tree.midlist();
    
        }
    }
    
    
    class AvlTree { 
        Node root;
    
    
        /** * 二叉树添加节点方法 为空直接替换根节点 * * @param node */
        public void add(Node node) { 
            if (root == null) { 
                root = node;
            } else { 
                root.add(node);
            }
    
        }
    
    
        /** * 中序遍历树 */
        public void midlist() { 
            if (root != null) { 
                root.midface();
                System.out.println();
            }
        }
    
        /** * 前序遍历树 */
        public void prelist() { 
            if (root != null) { 
                root.preface();
                System.out.println();
            }
        }
    
    
    }
    
    
    class Node { 
        Node left;
        Node right;
        int value;
    
        /** * 左旋方法 */
        public void leftRotate() { 
            Node newnode = new Node(value);
            //将新节点左子树设置为当前节点左子树
            newnode.left = left;
            //新节点右子树设置为当前节点右子树的左子树
            newnode.right = right.left;
            value = right.value;
            right = right.right;
            left = newnode;
        }
    
        /** * 右旋方法 */
        public void rightRotate() { 
            Node newnode = new Node(value);
            newnode.right = right;
            newnode.left = left.right;
            value = left.value;
            left = left.left;
            right = newnode;
        }
    
        /** * 左子树可能为空 * * @return */
        public int leftHeight() { 
            if (left == null) { 
                return 0;
            } else { 
                return left.getHeight();
            }
        }
    
        /** * 右子树可能为空 * * @return */
        public int rightHeight() { 
            if (right == null) { 
                return 0;
            } else { 
                return right.getHeight();
            }
        }
    
        /** * 获取树的高度 */
        public int getHeight() { 
            return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
        }
    
        /** * 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点 * * @param node 待插入的节点 */
        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);
                }
            }
    
            //计算左子树的高度
            int l = leftHeight();
            //计算右子树的高度
            int r = rightHeight();
            //当他们高度相差2时 就需要旋转
            if (l - r > 1) { 
                //双旋的情况 左子树的左子树的高度小于左子树的右子树的高度
                if (left.leftHeight() < left.rightHeight()) { 
                    //要将左子树左旋 再将整个树右旋
                    left.leftRotate();
                    rightRotate();
                } else { 
                    rightRotate();
                }
            }
    
            if (r - l > 1) { 
                //双旋的情况 右子树的左子树的高度大于右子树的左子树的高度
                if (right.leftHeight() > right.rightHeight()) { 
                    //要将右子树右旋 再将整个树左旋
                    right.rightRotate();
                    leftRotate();
                } else { 
                    leftRotate();
                }
            }
        }
    
    
        /** * 前序遍历方法 */
        public void preface() { 
            System.out.print(this.value + " ");
            if (this.left != null) { 
                this.left.preface();
            }
            if (this.right != null) { 
                this.right.preface();
            }
        }
    
    
        /** * 中序遍历方法 */
        public void midface() { 
            if (this.left != null) { 
                this.left.midface();
            }
            System.out.print(this.value + " ");
            if (this.right != null) { 
                this.right.midface();
            }
        }
    
    
        public Node(int value) { 
            this.value = value;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

ps：**要多想 在那以前要多想**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1e174645b5024c3cbe35fd03f65b5bed.png
[20201030104205901.png_pic_center]: https://img-blog.csdnimg.cn/20201030104205901.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201030105359148.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201030105812370.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201030110635596.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201030110711774.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201030111622660.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201030111729759.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201030111757990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201030112833890.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[20201030112949122.png_pic_center]: https://img-blog.csdnimg.cn/20201030112949122.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201030113018465.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/2020103011322374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20201030113934220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw==,size_16,color_FFFFFF,t_70#pic_center