[TOC]

平衡二叉树

参考：https://blog.csdn.net/jyy305/article/details/70949010

一、定义

平衡二叉树，是一种二叉排序树，其中每个节点的左子树和右子树相差的高度不超过1 （左子树的高度 - 右子树的高度 <= |1|）。它是一种高度平衡的二叉排序树。高度平衡：意思是说，要么它是一颗空树，要么它的左子树和右子树都是平衡二叉树。

平衡二叉树的出现是为了优化二叉顺序树的查找效率，你可以想象下，二叉顺序树如果顺序添加一个这样的数据｛5，4，3，2，1｝,那么树成了一个链表，查找效率显然不高 。 平衡二叉树首先是一个二叉顺序树，只不过他在每次添加数据的时候会进行自我平衡，来优化查找的效率。

二、术语

最小不平衡子树：指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1;

三、插入操作

在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是： 旋转

四、我理解的旋转

旋转是为了解决平衡树的失衡，如何做呢？即将子树高的一边中的一些节点调整到另一边，（并不只是把一边的节点给移到另一边，只是总体看上去，高的一边变矮了。）调整时需要保持树依然 是有序的。

上面这颗树明显已经不是平衡数，根节点50的平衡因子(bf) 3 -1 > 1 ，此时我们需要调整该树让其再一次到达平衡。我们先把树拆成两部分。如下

第一部分：根节点深度大的子树

第二部分：根节点与深度小的子树

然后我们在将这拆开的两部分组合成一个新的平衡二叉树

为了少打点字，在下面我就把分出来的两部分 一个叫第一部分 ， 一个叫第二部分

分开的第一部分，即深度大的子树的根节点（这里是40）将会成为新树的根节点。

然后呢？第一部分（针对这个例子）所有的键值是比第二部分的键值小的（二叉顺序数 左子树< 跟节点 < 右子树），所以我们得把第二部分插入到新的根节点的右子树上。 然后我们发现新的根节点的右子树已经有值了，那不得把他给拆下来。将拆下来的这个右子树插到第二部分。我们可以看到第二部分是一定会有一边（可能会有两边）是空的，因为我们把他深度高的子树给他拆下来了 。 而我们把刚拆下来的右子树就可以插到符合顺序的子节点上，这个子节点一定会是空的。这样就完成了旋转。如图：

我们来小结一下，我们做了两个步骤（并不完全，后面还会加东西）

• 将数拆成了两部分

• • 第一部分：根节点深度大的子树
  • 第二部分：根节点与深度小的子树

• 将第二部分插入到第一部分中

第二部分插入到第一部分符合二叉顺序树的一边（子节点），如果那里已经有值了，那就把它拆出来插入到第二部分空的一方（子节点）。无值的话插就完事了

看到这如果你感觉你理解了辣么来练习一下：

上面说的就是左旋转 和 右旋转，第一个例子是左旋 ，第二个例子是右旋、我在网上找的所有博客都是旋转方法分左右来介绍，让我理解的有点难度。

那什么时候进行左旋 ， 什么时候进行右旋呢 ？通过上面的例子我们可以简单的看到哪个（左右）子树深度大就叫哪（左右）旋 。

五、需要进行两次的旋转操作

以为这样就完了吗 ？不，还有呢，来看下面这个例子!

按这前面的套路一顿操作，然后发现得到依然还是个不平衡的二叉树。。可能有些人看到这就开始了，你在写什么玩意，我看这么久是用你的方法来一顿操作然后得不到正确的结果吗？

呃呃，走远了。我们来分析下为什么对于这个树按照前面的套路得不到平衡树。按套路来、

1、首先拆成两部分，没有什么不对的。额，其实这里没啥分析的

2、我们在合成新树的时候，在将第二部分插入到第一部分满足顺序的子节点时，发现该子节点，并不是一个叶子节点（无子节点的节点），而先前成功的案例都是叶子节点。而且我们看结果问题也确实出现在42这个45的子节点上。

现在问题找到了，那怎么办呢 ？？答案是，将第一部分在给他旋转一次，旋转是干什么的，就是为了将左右子树尽量的平衡。虽然第一部分是平衡树，但他这个平衡在我们进行旋转时，我们觉得他这样子不行，那就给他旋转一下。

用旋转后的第一部分在与前面的第二部分进行合成，即可。

这种旋转也有个名字，叫 XX 旋（X的取值是左右。） 比如上面这个例子，他先是进行左旋，然后右旋 ，所以称之为 左右旋 。同理就有右左旋。但是没有左左旋和右右旋，因为这样的一次旋转就可以达到再次平衡.

贴一个右左旋转的例子，这里就不在画图演示了，辣么快去练习一下吧。

六、旋转的总结

6.1 步骤

1. 将树拆成两部分

   1. • 第一部分：根节点深度大的子树
      • 第二部分：根节点与深度小的子树

2. 将第二部分插入到第一部分中

   第二部分插入到第一部分符合二叉顺序树的一边（子节点），然后

   • • • a、如果那个节点是空节点，直接加进去就完成了
       • b、如果那个节点不是空节点，且是个叶子节点，那就把它拆出来插入到第二部分空的子节点上（满足顺序的一方）
       • c、如果那个节点不是空节点，且是个非叶子节点，那就需要对第一部分进行一次旋转，然后在进行上面的操做。

6.2 分类

1. 左旋 ：深度大的一边是左子树，且左子树的右节点是叶子节点或空节点

步骤：旧根节点的左子节点成为新的根节点，新根节点的右子节点（若存在）成为旧根节点的的左子节点，旧根节点成为新根节点的右子节点

1. 右旋： 深度大的一边是右子树，且右子树的左节点是叶子节点或空节点

步骤：旧根节点的右子节点成为新的根节点，新根节点的左子节点（若存在）成为旧根节点的的右子节点，旧根节点成为新根节点的左子节点

1. 左右选 ： 深度大的一边是左树，且左子树的右节点是非叶子节点

步骤：我不知道怎么描述。。哈哈

1. 右左旋： 深度大的一边是右子树，且左子树的左节点是非叶子节点

步骤：我不知道怎么描述。。哈哈

七、插入的什么时候去执行旋转，执行什么旋转，旋转哪些节点？

每次进行插入操作的时候，我们都需要进行一次检查，检查插入后是否还是平衡树，如果不是平衡树，那么需要找到最小不平衡子树（可以是整个树），通常就是找到最小不平衡子树的根节点，然后对最小不平衡子树进行旋转操作。

如何判断是不是平衡树：挨个遍历（采用后序遍历）非叶子节点，如过有节点 左子树的高度 - 右子树的高度 的绝对值大于1，那么这棵树就是非平衡的了，找到的这个节点就是最小不平衡子树的根节点

八、删除操作

当树进行删除操作时，如果待删除节点有子节点，那么会导致树会被拆开成两个部分，而我们则需要合成这两部分，并保证该树依然是个平衡二叉树。即三个步骤

拆开->合并->调整

拆开没什么讲的主要是合并与再次调整。

合并分为几种情况。

1. 没有子节点 ： 直接去除即可，不需要合并
2. 只有一个子节点 ：用待删除节点的子节点替代他
3. 两个子节点 ：有两种方式，用删除节点的左子树最右侧节点代替删除节点、用删除节点的右子树的最左侧的节点代替删除节点。

然后在继续进行自我平衡。

九、Java实现

package com.ss.study.tree.binary;

import lombok.Data;

import javax.validation.constraints.NotNull;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;

/**
 * 平衡二叉树
 * @author xia17
 * @date 2019/12/19 11:02
 */
public class BalancedBinaryTree {

    private Node root ;

    /**
     * 给树添加
     * @param key 值
     */
    public void push(int key){
        if (root == null){
            //空树直接加到根节点
            root = new Node(key,null);
        }else {
            //否则递归插入相应位置
            push(root,key);
        }
    }

    /**
     * 递归方法 插入到满足顺序的地方
     * @param node 比较节点
     * @param key 值
     */
    private void push(@NotNull Node node , int key){
        if (key > node.getKey()){
            //大于则加到右子树
            if (node.getRight() == null){
                //右子节点空则插入 ， 否则继续比较
                node.setRight(new Node(key,node));
                //检查是否破坏了平衡
                if (this.balanced()){
                    System.out.println("在添加键值：" + key +"的时候造成非平衡，自动调整完成");
                }
            }else {
                //继续递归比较
                push(node.getRight(),key);
            }
        }else if (key < node.getKey()){
            //小于则加入左子节点
            if (node.getLeft() == null){
                node.setLeft(new Node(key,node));
                //检查是否破坏了平衡
                if (this.balanced()){
                    System.out.println("在添加键值：" + key +"的时候造成非平衡，自动调整完成");
                }
            }else {
                //检查是否破坏了平衡
                push(node.getLeft(),key);
            }
        }else {
            // 等于则报错
            throw new RuntimeException("树中已经有了该键值：" + key);
        }
    }

    /**
     * 删除
     * @param key 值
     * @return 是否删除
     */
    public boolean delete(int key){
        if (root == null){
            //空树直接加到根节点
            return false;
        }
        return delete(root,key);
    }

    /**
     * 删除
     * @param node 节点
     * @param key 值
     * @return 是否删除
     */
    public boolean delete(Node node , int key){
        if (key > node.getKey()){
            //大于则去右子树
            if (node.getRight() == null){
                //没有这个节点
                return false;
            }else {
                //继续递归比较
                delete(node.getRight(),key);
            }
        }else if (key < node.getKey()){
            //小于则去左子树
            if (node.getLeft() == null){
                //没有这个节点
                return false;
            }else {
                //继续递归比较
                delete(node.getLeft(),key);
            }
        }
        // 等于则删除
        Node father = node.getFather();
        if (node.isLeaf()){
            //没有子节点 ： 直接去除即可，不需要合并
            if (father == null){
                this.root = null;
            }else if (father.getKey() >  key){
                father.setLeft(null);
            }else {
                father.setRight(null);
            }
        }else if (node.getLeft() != null && node.getRight() == null){
            //只有一个子节点 ：用待删除节点的子节点替代他
            //判断该节点是左节点还是右节点
            if (father == null){
                this.root = node.getLeft();
            }else if (father.getKey() >  key){
                father.setLeft(node.getLeft());
            }else {
                father.setRight(node.getLeft());
            }
            //维持父子关系
            node.getLeft().setFather(father);
        }else if (node.getRight() != null && node.getLeft() == null){
            //只有一个子节点 ：用待删除节点的子节点替代他
            if (father == null){
                this.root = node.getRight();
            }else if (father.getKey() >  key){
                father.setLeft(node.getRight());
            }else {
                father.setRight(node.getRight());
            }
            node.getRight().setFather(father);
        }else {
            // 有两种方式，1、用删除节点的左子树最右侧节点代替删除节点、2、用删除节点的右子树的最左侧的节点代替删除节点。
            // 这里采用方式 1
            // 获取删除节点左子树的最大的值（即最右侧节点）
            Node max = this.findMax(node.getLeft());
            if (father == null){
                this.root = max;
            }else if (father.getKey() >  key){
                father.setLeft(max);
            }else {
                father.setRight(max);
            }
            max.setFather(father);
            max.setLeft(node.getLeft());
            max.setRight(node.getRight());
            node.getLeft().setFather(max);
            node.getRight().setFather(max);
        }
        //调整
        if (this.balanced()){
            System.out.println("在删除节点：" + key +"时造成非平衡，自动调整完成。");
        }
        return true;
    }

    /**
     * 获取一个节点最小值节点
     * @param node 节点
     * @return 节点
     */
    private Node findMin(@NotNull Node node){
        if (node.getLeft()==null){
            return node;
        }
        return findMin(node.getLeft());
    }

    /**
     * 获取一个节点最大值节点
     * @param node 节点
     * @return 节点
     */
    private Node findMax(@NotNull Node node){
        if (node.getRight() == null){
            return node;
        }
        return this.findMax(node.getRight());
    }

    /**
     * 自动调整平衡
     * @return 返回是否进行了调整操作
     */
    private boolean balanced(){
        if (root == null){
            return false;
        }
        //采用前序遍历是找的第一个，可能不是最小非平衡树，所以这里采用后续遍历
        Iterator<Node> iterator = backIterator();
        while (iterator.hasNext()){
            Node next = iterator.next();
            // 平衡因子的绝对值 > 1 ， 则需要调整
            int bf = next.getLeftLength() - next.getRightLength();
            if (bf < -1 || bf > 1){
                //调整 ， 传入最小非平衡树的根节点，与平衡因子，传入平衡因子是因为不想计算两次 getLeftLength()方法也是采用递归的、
                rotate(next, bf);
                return true;
            }
        }
        return false;
    }

    /**
     * 旋转
     * @param node 最小非平衡子树的根节点
     * @param bf 平衡因子 为了不再次去算
     * @return 新的根节点
     */
    private Node rotate(@NotNull Node node , int bf){
        // one 是第一部分（根节点深度大的子树）  , node 是第二部分（根节点与深度小的子树）
        // two 是第二部分插入第一部分可能会覆盖的节点，（其实就是 one的一个子节点 ，左右取决于 one 的左右【与 one 的左右相反】 ）
        // 注意下面左右旋的差别 即if块里的差别 （主要是看 左 右）
        Node one , two ;
        // bf（平衡因子 ） 大于0 说明根节点深度大的子树在左边 ， 即 左旋
        if (bf>0){
            // 左旋
            one = node.getLeft();
            if (one.getRight() != null && !one.getRight().isLeaf()){
                // 如果不是叶子节点 ， 进行第二次旋转
                // 第二次旋转是用第一部分的根节点进行旋转 ， 第二次是右旋
                one = rotate(one, one.getBf());
            }
            // 截取two , 左旋取右节点  反之
            two = one.getRight();
            // 修改节点位置 ， 重新合并one node two
            // two 成为node 的 左节点
            node.setLeft(two);
            // node 成为 one 的右节点
            one.setRight(node);
        }else {
            //右旋
            one = node.getRight();
            if (one.getLeft() != null && !one.getLeft().isLeaf()){
                // 如果不是叶子节点 ， 进行第二次旋转
                // 第二次旋转是用第一部分的根节点进行旋转 ， 第二次是左旋
                one = rotate(one, one.getBf());
            }
            two = one.getLeft();
            // 修改节点位置 ， 重新合并one node two
            // two 成为node 的 右节点
            node.setRight(two);
            // node 成为 one 的左节点
            one.setLeft(node);
        }
        //维护父子关系 （修改了节点位置 ， 子节点记录的父节点需要重新定位）
        // 这里 two 节点可能是空的
        if (two !=null){
            two.setFather(node);
        }
        if (node.getFather()==null){
            // 如果传入的最小非平衡子树的根节点 是整棵树的根节点 那么需要修改 树对象 记录的根节点
            one.setFather(null);
            root = one;
        }else {
            // 不是上面这个条件时 ， 传入的最小非平衡子树的根节点的父节点的 左 或者 右 节点需要修改成one 。
            one.setFather(node.getFather());
            if (bf > 0){
                node.getFather().setLeft(one);
            }else {
                node.getFather().setRight(one);
            }
        }
        // node 的 父亲是 新树根节点
        node.setFather(one);
        //返回one
        return one;
    }

    /**
     * 前序遍历 先访问根节点，再访问左子树，最后访问右子树
     *  ----------- 这里采用的方法时顺序加入到list中 ， 这里感觉应该用数组效率会好一点， 因为这里的数据其实是固定大小的
     * @return 迭代器
     */
    public Iterator<Node> frontIterator(){
        ArrayList<Node> nodes = new ArrayList<>();
        if (this.root != null){
            addToFrontNodeList(nodes,this.root);
        }
        return nodes.iterator();
    }

    /**
     * 前序遍历 的 递归方法
     * @param nodes 结果
     * @param node 节点
     */
    private void addToFrontNodeList(List<Node> nodes,Node node){
        nodes.add(node);
        if (node.getLeft()!=null){
            addToFrontNodeList(nodes,node.getLeft());
        }
        if (node.getRight()!=null){
            addToFrontNodeList(nodes,node.getRight());
        }
    }


    /**
     * 后序遍历 先左子树，再右子树，最后根节点
     *  ----------- 这里采用的方法时顺序加入到list中 ， 这里感觉应该用数组效率会好一点， 因为这里的数据其实是固定大小的
     * @return 迭代器
     */
    public Iterator<Node> backIterator(){
        ArrayList<Node> nodes = new ArrayList<>();
        if (this.root != null){
            addToBackNodeList(nodes,this.root);
        }
        return nodes.iterator();
    }

    /**
     * 后续遍历的递归方法
     * @param nodes 结果
     * @param node 节点
     */
    private void addToBackNodeList(List<Node> nodes,Node node){
        if (node.getLeft()!=null){
            addToBackNodeList(nodes,node.getLeft());
        }
        if (node.getRight()!=null){
            addToBackNodeList(nodes,node.getRight());
        }
        nodes.add(node);
    }

    /**
     * 查找
     * @param key 兼职
     * @return 节点
     */
    public Optional<Node> find(int key){
        if (root == null){
            return Optional.empty();
        }else {
            return find(root,key);
        }
    }

    /**
     * 查找的递归方法
     * @param node 查找子树的根节点
     * @param key 值
     * @return 节点
     */
    private Optional<Node> find(@NotNull Node node , int key){
        if (key > node.getKey()){
            //大于则加到右子树
            if (node.getRight() == null){
                return Optional.empty();
            }else {
                return find(node.getRight() , key);
            }
        }else if (key < node.getKey()){
            if (node.getLeft() == null){
                return Optional.empty();
            }else {
                return find(node.getLeft() , key);
            }
        }
        return Optional.of(node);
    }

    /**
     * 测试
     * @param args 😄
     */
    public static void main(String[] args) {
        BalancedBinaryTree tree = new BalancedBinaryTree();
        tree.push(3);
        tree.push(2);
        tree.push(1);
        tree.push(4);
        tree.push(5);
        tree.push(7);
        tree.push(8);
        int leftLength = tree.root.getLeftLength();
        int rightLength = tree.root.getRightLength();
        tree.find(8).ifPresent(System.out::println);
        tree.find(9).ifPresent(System.out::println);
        System.out.println();
    }

}

/**
 * 这个节点的 set 方法应该不让外部操作。
 */
@Data
class Node{

    Node(int key , Node father){
        this.key = key;
        this.father = father;
    }

    /**
     * 键值
     */
    private int key;
    /**
     * 左节点
     */
    private Node left ;
    /**
     * 右节点
     */
    private Node right;
    /**
     * 父节点
     */
    private Node father;

    /**
     * 递归求一个节点的最大子树的深度
     *  ---------------注意 ： 最大子树的深度不包括该节点。
     *  这个方法感觉可以独立出去成为一个静态方法
     * @param node 节点
     * @return int 最大子树深度
     */
    private int findMaxLength(@NotNull Node node){
        int left = node.left == null ? 0 : findMaxLength(node.left);
        int right = node.right == null ? 0 : findMaxLength(node.right);
        return Math.max(left,right) + 1;
    }

    /**
     * 获取左子树的深度
     * @return 成
     */
    public int getLeftLength(){
        return this.left == null ? 0 : this.findMaxLength(this.left);
    }

    /**
     * 获取右子树的深度
     * @return int 只有跟节点是0
     */
    public int getRightLength(){
        return this.right == null ? 0 : this.findMaxLength(this.right);
    }

    /**
     * 平衡因子
     * @return int
     */
    public int getBf(){
        return this.getLeftLength() - this.getRightLength();
    }

    /**
     * 是否是叶子节点 ， 左节点和右节点都是空说明是叶子节点
     *  ps : 叶子节点 是没有孩子节点的节点
     * @return boolean
     */
    public boolean isLeaf(){
        return left == null && right == null;
    }



    @Override
    public String toString(){
        return String.valueOf(key);
    }

}