下次再让你讲平衡二叉树，可别说不会了

我不是女神ヾ 2023-01-09 12:31 170阅读 0赞

### 引言 ###

公众号原文链接：[下次再让你讲平衡二叉树，可别说不会了][Link 1] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

完整项目我已经上传到我的码云git仓库上了，如果就需要的话请访问我的码云git仓库获取，附上地址：[https://gitee.com/bobo\_tea/datastructure/tree/master/src/main/datastructure/com/bobo/group/tree/avl][https_gitee.com_bobo_tea_datastructure_tree_master_src_main_datastructure_com_bobo_group_tree_avl]。或者点击公众号底部菜单->资源汇总->仓库汇总。或者联系我。

### **1、平衡二叉树基本概念** ###

平衡二叉树，也是一种二叉查找树，但它是平衡的，即左子树与右子树的高度差最多等于1。

平衡二叉树也叫AVL树，取自发明平衡二叉树算法的人的人名。

平衡因子BF：左子树深度减去右子树深度的值。平衡二叉树所有结点的平衡因子只能是-1,0,1。

最小不平衡子树：假设新插入了一个结点A，然后导致树不平衡了，距离结点A最近且BF绝对值大于1的那个结点为B，以B结点为根的树称为最小不平衡子树

### **2、平衡二叉树实现原理** ###

在构建二叉查找树过程中，每插入一个结点，先检查是否破坏了树的平衡。若是，则找出最小不平衡子树，在保持二叉查找树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之达到新的平衡。

旋转分两种：左旋和右旋。右旋会减小BF，左旋增加BF。

上面的说辞比较抽象，下面就来具体一点的。为了更好地讲解原理，我们以依次插入结点3,2,1,4,5,6,7,10,9,8为例。

**第一步**

首先插入3和2是没问题的。

**第二步**

当插入1时，发现结点3的BF变成了2，因此需要右旋，如下图所示。

![图片][79b5f7b28ed66c3177a2dda62efcd86f.png]

**第三步**

插入4没问题。

**第四步**

当插入5时，结点3的BF变成了-2，因此左旋。

![图片][1e9c73b625fba5024d84af150f7836b7.png]

**第五步**

当插入结点6时，结点2的BF变成了-2，将根结点左旋。但3有点多余，将它设置为结点2的右孩子。

大家有没有担心这种情况：结点4的左子树，不单单是一个结点，而是一颗高度大于1的子树？其实不会的，它只能是一个结点。大家可以用笔在纸上画一下，平衡二叉树不会出现这样的情况。

![图片][c87859490385e83169ef79d7a8218265.png]

**第六步**

当插入结点7时，结点5的BF变成-2，左旋。

![图片][c7da5e9fc67bf7d2a61aa1e097f43c67.png]

**第七步**

插入10没问题。

**第八步**

当插入9时，7的BF为-2，理论上左旋就行了，但会不满足二叉查找树的特性。

![图片][9b661969181e806a945dbb97bedc4e4d.png]

导致这种情况的原因是：结点7和它的孩子结点10，两者的BF符号不一致。既然不一致，先将结点9和结点10组成的子树右旋，然后再以结点7为根结点进行左旋。

![图片][93ba13bcdbd5593ed2390763c2319105.png]

**第九步**

当插入结点8时，结点6的BF为-2，而结点9的BF为1，为了保证符号统一，因此以结点9为根结点进行右旋，注意，结点8本来是结点7的右孩子，但是右旋之后，因为7<8<9，所以只能将结点8当成结点9的左孩子。

![图片][6b21ecb3a3bae308ea6be6beedde254f.png]

### **3、平衡二叉树代码实现** ###

平衡二叉树实现原理中的九个步骤，是代码实现的铺垫，建议大家将九个步骤都看懂，然后再看代码，这九个步骤几乎涵盖了所有可能的情况。

我的平衡二叉树实现分四个类：

*  Ancestor：祖先类
 *  AVLInsert：平衡二叉树结点插入核心实现
 *  AVLMain：main方法所在类，包含示例程序
 *  AVLNode：avl树结点类

**AVLNode**

import com.bobo.group.tree.draw.Drawable;
    
    public class AVLNode implements Drawable {
        private int val;
        private AVLNode left;
        private AVLNode right;
    
        public AVLNode(int val) {
            this.val = val;
        }
    
        public AVLNode(int val, AVLNode left, AVLNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    
        //省略getter/setter方法
    
        @Override
        public String getValue() {
            return String.valueOf(this.val);
        }
    
        @Override
        public Drawable getLeftNode() {
            return this.left;
        }
    
        @Override
        public Drawable getRightNode() {
            return this.right;
        }
    }

**Ancestor**

/**
     * 结点的祖先信息
     */
    public class Ancestor {
        private AVLNode ancestor;
        private boolean isLeft;
    
        public Ancestor(AVLNode ancestor) {
            this.ancestor = ancestor;
        }
    
        public Ancestor(AVLNode ancestor, boolean isLeft) {
            this.ancestor = ancestor;
            this.isLeft = isLeft;
        }
        // 省略getter/setter方法
    }

**AVLInsert**

import com.bobo.group.common.CommonUtil;
    import com.bobo.group.tree.draw.DrawTree;
    import java.util.ArrayList;
    import java.util.List;
    
    public class AVLInsert {
        //记录插入的每个结点
        private List<AVLNode> avlNodes = new ArrayList<>();
        //画二叉树对象
        private DrawTree drawTree = new DrawTree();
        //可变的根结点，因为根结点也会旋转
        private AVLNode variableRoot;
        //生成图片时计数
        private int drawCounter=1;
        //树偏移量数组，画图用
        //private int[] offset_x_arr = new int[]{60,30,25,20,20,20,10,10};
        private int[] offset_x_arr = new int[]{120,80,30,30,20,20,10,10};
    
        /**
         * 每插入一个结点，就画一次图
         * @param key
         */
        private void drawStep(int key){
            drawTree.drawEntrance(variableRoot, CommonUtil.getResourceRoot()+"tree/avl/avlinsert_"+drawCounter+"_"+key+".png",false,offset_x_arr);
            drawCounter++;
        }
    
        /**
         * 平衡二叉树插入结点核心算法
         * @param avlNode 当前结点
         * @param key 要插入的关键字
         * @param ancestorChain 祖先信息链
         */
        private void insert(AVLNode avlNode,int key,List<Ancestor> ancestorChain){
            if(key < avlNode.getVal()){
                //新增一个祖先信息
                ancestorChain.add(new Ancestor(avlNode,true));
                //左孩子为null，则执行插入
                if(avlNode.getLeft() == null){
                    AVLNode keyNode = new AVLNode(key);
                    avlNodes.add(keyNode);
                    avlNode.setLeft(keyNode);
                    //平衡算法
                    calculateBFAndRotate(ancestorChain);
                    //平衡后，画图
                    drawStep(key);
                    return;
                }else{
                    //递归搜索
                    insert(avlNode.getLeft(),key,ancestorChain);
                }
            }
    
            if(key > avlNode.getVal()){
                //新增一个祖先信息
                ancestorChain.add(new Ancestor(avlNode,false));
                //右孩子为null，则执行插入
                if(avlNode.getRight() == null){
                    AVLNode keyNode = new AVLNode(key);
                    avlNodes.add(keyNode);
                    avlNode.setRight(keyNode);
                    //平衡算法
                    calculateBFAndRotate(ancestorChain);
                    //平衡后，画图
                    drawStep(key);
                    return;
                }else{
                    //递归搜索
                    insert(avlNode.getRight(),key,ancestorChain);
                }
            }
    
        }
    
        /**
         * 计算平衡因子，如果有必要的话，还要旋转
         * @param ancestorChain 祖先链
         */
        private void calculateBFAndRotate(List<Ancestor> ancestorChain){
            //ancestorChain持有的都是新插入的那个导致树不平衡的结点的祖先
            // 祖先的顺序是：index为0时，为距离最远的祖先，index为size-1时，为距离最近的祖先
            //所以，如果我们要找出最小不平衡子树，则需要从最近的祖先开始判断
            for (int i = ancestorChain.size()-1;i >= 0;i--){
                //当前祖先
                AVLNode ancestorNode = ancestorChain.get(i).getAncestor();
                boolean leftOfAncestor = ancestorChain.get(i).isLeft();
    
                //分别计算当前祖先的左右子树深度
                int leftDepth = searchDepth(ancestorNode.getLeft(),1);
                int rightDepth = searchDepth(ancestorNode.getRight(),1);
                //计算当前祖先的平衡因子
                int bf = leftDepth-rightDepth;
                //如果bf绝对值大于1，则表示树不平衡，需要进行相应的处理；否则，不做任何事情
                if(Math.abs(bf) > 1){
                    //先判断当前祖先的子节点 与 当前祖先 的BF符号是否一致
                    AVLNode child = leftOfAncestor?ancestorNode.getLeft():ancestorNode.getRight();
                    int childLeftDepth = searchDepth(child.getLeft(),1);
                    int childRightDepth = searchDepth(child.getRight(),1);
                    int childBf = childLeftDepth-childRightDepth;
    
                    //符号不一致，以子结点为根结点进行旋转
                    if(childBf > 0 && bf < 0){
                        //右旋，旋转一个单位即可，应该没有特殊情况
                        rightRotate(ancestorNode,child,leftOfAncestor);
                    }else if(childBf < 0 && bf > 0){
                        //左旋
                        leftRotate(ancestorNode,child,leftOfAncestor);
                    }
                    //符号统一之后，再旋转当前结点
                    if(bf > 0){
                        // 右旋
                        if(i == 0){
                            //根结点的旋转特殊处理
                            AVLNode rootLeftRight = ancestorNode.getLeft().getRight();
                            AVLNode rootLeft = ancestorNode.getLeft();
                            rootLeft.setRight(ancestorNode);
                            ancestorNode.setLeft(rootLeftRight);
                            //更新可变根结点
                            variableRoot = rootLeft;
                        }else{
                            //非根结点处理，将当前祖先的父节点，当前祖先，当前祖先与其父节点的关系传给rightRotate方法
                            rightRotate(ancestorChain.get(i-1).getAncestor(),ancestorNode,ancestorChain.get(i-1).isLeft());
                        }
    
                    }else if(bf < 0){
                        // 左旋
                        if(i == 0){
                            //根结点的旋转特殊处理
                            AVLNode rootRightLeft = ancestorNode.getRight().getLeft();
                            AVLNode rootRight = ancestorNode.getRight();
                            rootRight.setLeft(ancestorNode);
                            ancestorNode.setRight(rootRightLeft);
                            //更新可变根结点
                            variableRoot = rootRight;
                        }else{
                            //非根结点处理，将当前祖先的父节点，当前祖先，当前祖先与其父节点的关系传给rightRotate方法
                            leftRotate(ancestorChain.get(i-1).getAncestor(),ancestorNode,ancestorChain.get(i-1).isLeft());
                        }
    
                    }
    
                }
            }
        }
    
        //左旋时，防止右节点的左孩子不为空
        private void leftRotate(AVLNode parent,AVLNode node,boolean isLeft){
            //由于是左旋，为了避免不满足二叉查找树特性，所以要先判断node的右孩子的左孩子是否为null
            AVLNode nodeRightLeft = node.getRight().getLeft();
            if(isLeft){
                parent.setLeft(node.getRight());
                parent.getLeft().setLeft(node);
                node.setRight(nodeRightLeft);
            }else{
                parent.setRight(node.getRight());
                parent.getRight().setLeft(node);
                node.setRight(nodeRightLeft);
            }
        }
    
        //右旋时，防止左节点的右孩子不为空
        private void rightRotate(AVLNode parent,AVLNode node,boolean isLeft){
            //由于是右旋，为了避免不满足二叉查找树特性，所以要先判断node的左孩子的右孩子是否为null
            AVLNode nodeLeftRight = node.getLeft().getRight();
            if(isLeft){
                parent.setLeft(node.getLeft());
                parent.getLeft().setRight(node);
                node.setLeft(nodeLeftRight);
            }else{
                parent.setRight(node.getLeft());
                parent.getRight().setRight(node);
                node.setLeft(nodeLeftRight);
            }
    
        }
    
        //查找树的深度
        private int searchDepth(AVLNode avlNode, int depth){
            if(avlNode == null){
                return 0;
            }
            if(avlNode.getLeft() == null && avlNode.getRight() == null){
                return depth;
            }else if(avlNode.getLeft() == null){
                return searchDepth(avlNode.getRight(),depth+1);
            }else if(avlNode.getRight() == null){
                return searchDepth(avlNode.getLeft(),depth+1);
            }else{
                int a = searchDepth(avlNode.getLeft(),depth+1);
                int b = searchDepth(avlNode.getRight(),depth+1);
                return a>b?a:b;
            }
        }
    
    
        /**
         * 平衡二叉树结点插入入口
         * @param root 根结点
         * @param keys 要插入的关键字数组
         */
        public void insertEntrance(AVLNode root,int[] keys){
    
            if(null == root){
                root = new AVLNode(keys[0]);
                variableRoot = root;
                this.avlNodes.add(root);
                for (int i = 1; i < keys.length; i++) {
                    List<Ancestor> parentPoints = new ArrayList<>();
                    insert(variableRoot,keys[i],parentPoints);
                }
            }else{
                variableRoot = root;
                for (int i = 0; i < keys.length; i++) {
                    List<Ancestor> parentPoints = new ArrayList<>();
                    insert(variableRoot,keys[i],parentPoints);
                }
            }
        }
    
    }

**AVLMain**

public class AVLMain {
        public static void main(String[] args) {
            AVLInsert avlInsert = new AVLInsert();
            avlInsert.insertEntrance(null,new int[]{3,2,1,4,5,6,7,10,9,8});
        }
    }

运行main方法，我将每一步的结果生成了图片，供大家参考，暂时我还没测出bug来，应该没啥问题。

![图片][14a8318fa972ff070651516f6e656bd4.png]

平衡二叉树应该还挺重要的，它的算法有一定难度，不过掌握了思想之后，代码写起来就很快了。

### 我的二维码 ###

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![20210121085816775.jpg][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484774&idx=1&sn=b96d062bfcd83a48afda94b34c8b7688&chksm=ea307da4dd47f4b24a14234228579d56dacd899dc03b33898d067d7c8592fd1ae26dfcf6af6e&token=1909849060&lang=zh_CN#rd
[https_gitee.com_bobo_tea_datastructure_tree_master_src_main_datastructure_com_bobo_group_tree_avl]: https://gitee.com/bobo_tea/datastructure/tree/master/src/main/datastructure/com/bobo/group/tree/avl
[79b5f7b28ed66c3177a2dda62efcd86f.png]: /images/20221119/6956d54f1eac4cf7b219f49a048e0240.png
[1e9c73b625fba5024d84af150f7836b7.png]: /images/20221119/345bb1683156430daa653c56c4c2b1c6.png
[c87859490385e83169ef79d7a8218265.png]: https://img-blog.csdnimg.cn/img_convert/c87859490385e83169ef79d7a8218265.png
[c7da5e9fc67bf7d2a61aa1e097f43c67.png]: https://img-blog.csdnimg.cn/img_convert/c7da5e9fc67bf7d2a61aa1e097f43c67.png
[9b661969181e806a945dbb97bedc4e4d.png]: https://img-blog.csdnimg.cn/img_convert/9b661969181e806a945dbb97bedc4e4d.png
[93ba13bcdbd5593ed2390763c2319105.png]: https://img-blog.csdnimg.cn/img_convert/93ba13bcdbd5593ed2390763c2319105.png
[6b21ecb3a3bae308ea6be6beedde254f.png]: https://img-blog.csdnimg.cn/img_convert/6b21ecb3a3bae308ea6be6beedde254f.png
[14a8318fa972ff070651516f6e656bd4.png]: https://img-blog.csdnimg.cn/img_convert/14a8318fa972ff070651516f6e656bd4.png
[20210121085816775.jpg]: https://img-blog.csdnimg.cn/20210121085816775.jpg