3、面试官让我手写一个平衡二叉树，我当时就笑了

骑猪看日落 2023-06-17 09:54 155阅读 0赞

平衡二叉树对于初学者一直是一个比较复杂的知识点，因为其里面涉及到了大量的旋转操作。把大量的同学都给转晕了。这篇文章最主要的特点就是通过动画的形式演示。确保大家都能看懂。最后是手写一个平衡二叉树。

**一、概念**

平衡二叉树是外国的两个大爷发明的。一开始发明的是二叉查找树。后来觉得不给力演化成了平衡二叉树。那什么是二叉查找树呢？我们给出一张图来看看：

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

看到这张图我们就会发现如下的特征。从每个节点出发，左边的节点一定小于右边的。但是你会发现这可以高低不平，看起来很不美观。于是慢慢的演化成了平衡二叉树。（当然不是因为美观演化的）。也就是说平衡二叉树的前提就是一颗二叉查找树

> **平衡二叉树定义(AVL)：**
> 
> **（1）它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，**
> 
> **（2）它的左子树和右子树都是一颗平衡二叉树。**

也就是说以上两条规则，只要破坏了一个就不是平衡二叉树了。比如说下面这张图。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 1]  
上面这张图就是破坏了二叉查找树这一条规则。当然了还有一条规则。也就是他的高度只差不能超过1.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 2]  
现在相信我们已经明白了什么是平衡二叉树。下面我们就来看看平衡二叉树的增删改查操作是怎么样的。

**二、平衡二叉树的插入操作**

我们先从最简单的入手，一步一步来。

**1、右旋**

首先我们插入几个数字，50,45,44。通过动画我们来演示一遍  
![在这里插入图片描述][20191128145250175.gif]

（1）插入50根节点不会出现任何操作

（2）插入45，往左边插入即可

（3）插入44，破坏了平衡，于是右旋。

**2、左旋**

我们插入几个数字，50,60,70。通过动画我们来演示一遍

![在这里插入图片描述][20191128145303955.gif]  
（1）插入50根节点不会出现旋转

（2）插入60，往右边插入即可

（3）插入70，破坏了平衡，于是左旋。

**3、先右旋再左旋**

我们依次插入50,60,55.通过动画我们演示一遍

![在这里插入图片描述][20191128145312288.gif]  
（1）插入55,根节点，不会出现旋转

（2）插入60，往右边插入

（3）插入55，破坏了平衡，于是先把55和60右旋，然后整体左旋。

**4、先左旋后右旋**

我们依次插入50,40,45.通过动画我们演示一遍。

![在这里插入图片描述][201911281453214.gif]

（1）插入55,根节点，不会出现旋转

（2）插入40，往左边插入

（3）插入45，破坏了平衡，于是先把45和40左旋，然后整体右旋。

现在我们基本上已经把插入的几种情况罗列出来了。现在我们画一张图，来一个总结。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 3]

上图对于每一种情况，从上往下看就好了。对于平衡二叉树的删除操作，其实也是同样的道理，找到相应的元素之后，对其进行删除，删除之后如果破坏了平衡，只需要按照上面的这几种情况进行调整即可。下面我们来分析一下平衡二叉树的查找操作。

**三、平衡二叉树的查找**

平衡二叉树的查找很简单，只需要按照二叉查找树的顺序执行就好。我们使用一张动画演示一下：

![在这里插入图片描述][20191128145335275.gif]

现在平衡二叉树的操作相信你已经能够理解。下面我们就来关注最后一个问题，那就是如何手写一颗平衡二叉树呢？

**四、手写一颗平衡二叉树**

平衡二叉树的代码操作，难点在于旋转。只要把旋转弄清楚基本上整个树就能完成了，根据上面旋转的特点我们从零开始定义一颗。

**第一步：定义节点**

public class AVLNode { 
        public int data;//保存节点数据
        public int depth;//保存节点深度
        public int balance;//是否平衡
        public AVLNode parent;//指向父节点
        public AVLNode left;//指向左子树
        public AVLNode right;//指向右子树
    
        public AVLNode(int data){ 
            this.data = data;
            depth = 1;
            balance = 0;
            left = null;
            right = null;
        }
     }

**第二步：插入数据**

public void insert(AVLNode root, int data){ 
       //如果说插入的数据小于根节点，往左边递归插入
       if (data < root.data){ 
           if (root.left != null){ 
                insert(root.left, data);
           }else { 
                root.left = new AVLNode(data);
                root.left.parent = root;
           }
       }
       //如果说插入的数据小于根节点，往左边递归插入
       else { 
            if (root.right != null){ 
                insert(root.right, data);
            }else { 
                root.right = new AVLNode(data);
                root.right.parent = root;
           }
      }
      //插入之后，计算平衡银子
       root.balance = calcBalance(root);
      // 左子树高，应该右旋
      if (root.balance >= 2){ 
          // 右孙高，先左旋
          if (root.left.balance == -1){ 
              left_rotate(root.left);
          }
          right_rotate(root);
      }
      // 右子树高，左旋
      if (root.balance <= -2){ 
          // 左孙高，先右旋
          if (root.right.balance == 1){ 
              right_rotate(root.right);
          }
          left_rotate(root);
      }
      //调整之后，重新计算平衡因子和树的深度
      root.balance = calcBalance(root);
      root.depth = calcDepth(root);
    }

**第三步：左旋和右旋的调整**

**1、右旋**

// 右旋
        private void right_rotate(AVLNode p){ 
            // 一次旋转涉及到的结点包括祖父，父亲，右儿子
            AVLNode pParent = p.parent;
            AVLNode pLeftSon = p.left;
            AVLNode pRightGrandSon = pLeftSon.right;
            // 左子变父
            pLeftSon.parent = pParent;
            if (pParent != null){ 
                if (p == pParent.left){ 
                    pParent.left = pLeftSon;
                }else if (p == pParent.right){ 
                    pParent.right = pLeftSon;
                }
            }
            pLeftSon.right = p;
            p.parent = pLeftSon;
            // 右孙变左孙
            p.left = pRightGrandSon;
            if (pRightGrandSon != null){ 
                pRightGrandSon.parent = p;
            }
            p.depth = calcDepth(p);
            p.balance = calcBalance(p);
            pLeftSon.depth = calcDepth(pLeftSon);
            pLeftSon.balance = calcBalance(pLeftSon);
        }

**2、左旋**

private void left_rotate(AVLNode p){ 
            // 一次选择涉及到的结点包括祖父，父亲，左儿子
            AVLNode pParent = p.parent;
            AVLNode pRightSon = p.right;
            AVLNode pLeftGrandSon = pRightSon.left;
            // 右子变父
            pRightSon.parent = pParent;
            if (pParent != null){ 
                if (p == pParent.right){ 
                    pParent.right = pRightSon;
                }else if (p == pParent.left){ 
                    pParent.left = pRightSon;
                }
            }
            pRightSon.left = p;
            p.parent = pRightSon;
            // 左孙变右孙
            p.right = pLeftGrandSon;
            if (pLeftGrandSon != null){ 
                pLeftGrandSon.parent = p;
            }
            p.depth = calcDepth(p);
            p.balance = calcBalance(p);
            pRightSon.depth = calcDepth(pRightSon);
            pRightSon.balance = calcBalance(pRightSon);
        }

**第四步：计算平衡和深度**

**1、计算平衡**

public int calcBalance(AVLNode p){ 
            int left_depth;
            int right_depth;
            //左子树深度
            if (p.left != null){ 
                left_depth = p.left.depth;
            }else { 
                left_depth = 0;
            }
            //右子树深度
            if (p.right != null){ 
                right_depth = p.right.depth;
            }else { 
                right_depth = 0;
            }
            return left_depth - right_depth;
        }

**2、计算深度**

public int calcDepth(AVLNode p){ 
            int depth = 0;
            if (p.left != null){ 
                depth = p.left.depth;
            }
            if (p.right != null && depth < p.right.depth){ 
                depth = p.right.depth;
            }
            depth++;
            return depth;
        }

看起来代码有些多，其实梳理一下就不多了。

（1）首先定义一个节点，里面有get和set方法，构造函数等等做准备工作

（2）直接写业务流程，比如说这里的insert操作，里面涉及到的旋转操作先用方法代替

（3）对主业务流程的操作，缺哪一个方法，写哪一个方法即可

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191128145221639.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191128145226665.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191128145243351.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw=,size_16,color_FFFFFF,t_70
[20191128145250175.gif]: https://img-blog.csdnimg.cn/20191128145250175.gif
[20191128145303955.gif]: https://img-blog.csdnimg.cn/20191128145303955.gif
[20191128145312288.gif]: https://img-blog.csdnimg.cn/20191128145312288.gif
[201911281453214.gif]: https://img-blog.csdnimg.cn/201911281453214.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191128145330122.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw=,size_16,color_FFFFFF,t_70
[20191128145335275.gif]: https://img-blog.csdnimg.cn/20191128145335275.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2019112814534954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw=,size_16,color_FFFFFF,t_70