平衡二叉树复习

定义

一棵，对于每一个节点，它的左右子树的高度差不超过1

树空呢？左右子树为0，当然也是平衡二叉树，而且高度定义为1。
ps：二叉查找树（英语：Binary Search Tree），也称为二叉搜索树

举反例:

为什么需要平衡二叉树

当二叉查找树不平衡时比如:

它就是链表了，而且还是带有左指针的链表（链表只包含一个指向下一个节点的指针）
需要遍历二叉查找树，然后找到对应的节点时。

• 如果它是正常的二叉搜索树的结构，那么执行该方法的算法复杂度就是O（logN）
• 但是如果是上图所示的结构那么就是链表的遍历为O(N)。

平衡因子

节点的平衡因子只能取 0 、1 或者 -1 ，分别对应 左右子树等高，左子树比较高，右子树比较高。

平衡二叉树和AVL算法

AVL是一个平衡树算法，用来平衡二叉查找树，AVL树又称为高度平衡树。
假设有如下平衡二叉树

现在需要插入99，树结构变为

节点 66 的左子树高度为 1，右子树高度为 3，此时平衡因子为 -2，树失去平衡。
上图中以节点 66 为父节点的那颗树称为 最小失衡子树

最小失衡子树

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就进行相反方向的旋转。

左旋

因为上图右子树高，进行左旋
步骤如下:

（1）节点的右孩子替代此节点位置 
（2）右孩子的左子树变为该节点的右子树 
（3）节点本身变为右孩子的左子树

左旋

（1）节点的右孩子替代此节点位置 —— 节点 66 的右孩子是节点 77 ，将节点 77 代替节点 66 的位置

（2）右孩子的左子树变为该节点的右子树 —— 节点 77 的左子树为节点 75，将节点 75 挪到节点 66 的右子树位置

（3）节点本身变为右孩子的左子树 —— 节点 66 变为了节点 77 的左子树

右旋

（1）节点的左孩子代表此节点 
（2）节点的左孩子的右子树变为节点的左子树 
（3）将此节点作为左孩子节点的右子树。

平衡二叉树代码实现

节点结构

package balancetree;
public class TreeNode {
     private int element;//节点的值
     private int balance;//节点的平衡因子，如果绝对值大于1，就表示需要调整
     private TreeNode leftChild;
     private TreeNode rightChild;
     private TreeNode parent;
     public TreeNode() {
        super();
     }
     public TreeNode(int element, TreeNode parent) {
         this.element = element;
         this.parent = parent;
     }
     @Override
     public String toString() {
         //打印当前结点以及平衡因子
         return "值:"+element + ",平衡因子:" + balance;
     }
     public int getElement() {
         return element;
     }
     public void setElement(int element) {
         this.element = element;
     }
     public int getBalance() {
         return balance;
     }
     public void setBalance(int balance) {
         this.balance = balance;
     }
     public TreeNode getLeftChild() {
         return leftChild;
     }
     public void setLeftChild(TreeNode leftChild) {
         this.leftChild = leftChild;
     }
     public TreeNode getRightChild() {
         return rightChild;
     }
     public void setRightChild(TreeNode rightChild) {
         this.rightChild = rightChild;
     }
     public TreeNode getParent() {
         return parent;
     }
     public void setParent(TreeNode parent) {
         this.parent = parent;
     }
}

定义一个树根，相当于二叉树入口一样

package balancetree;
import tree.TreeNode;
public class TreeRoot {
    private TreeNode treeRoot;
    public TreeNode getTreeRoot() {
        return treeRoot;
    }
    public void setTreeRoot(TreeNode treeRoot) {
        this.treeRoot = treeRoot;
    }
}

定义二叉树的遍历工具

package balancetree;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
import tree.TreeNode;
public class ScanTree {
    public ScanTree() {
        super();
    }
    //前序遍历
      public void preTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问根节点
                System.out.print(rootTreeNode.getElement()+" ");
                //访问左节点
                preTraverseBTree(rootTreeNode.getLeftChild());
                //访问右节点
                preTraverseBTree(rootTreeNode.getRightChild());
            }
        }
      //中序遍历
      public void inTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问左节点
                inTraverseBTree(rootTreeNode.getLeftChild());
                //访问根节点
                System.out.print(rootTreeNode.getElement()+" ");
                //访问右节点
                inTraverseBTree(rootTreeNode.getRightChild());
            }
        }
    //后序遍历
      public void endTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问左节点
                endTraverseBTree(rootTreeNode.getLeftChild());
                //访问右节点
                endTraverseBTree(rootTreeNode.getRightChild());
                //访问根节点
                System.out.print(rootTreeNode.getElement()+" ");
            }
        }
      //层序遍历
      public void cengTraverseBTree(TreeNode rootTreeNode){
          //声明一个队列
          //LinkedBlockingQueue的容量是没有上限的,也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。
          //ArrayBlockingQueue在构造时需要指定容量
          Queue<TreeNode> queue = new LinkedBlockingQueue<>();
            if (rootTreeNode == null) {
                return;
            }
            queue.add(rootTreeNode);
            while(!queue.isEmpty()) {
                TreeNode tempNode = queue.poll();
                System.out.print(tempNode.getElement()+" ");
                if(tempNode.getLeftChild()!=null)queue.add(tempNode.getLeftChild());
                if(tempNode.getRightChild()!=null)queue.add(tempNode.getRightChild());
            }
        }
}

平衡二叉树代码实现

package balancetree;
import tree.TreeNode;
public class BalanceTreeDemo {
    private static TreeRoot root;
    //左旋代码
    private static void leftRotate(TreeNode p) {
        if (p != null) {
            //得到它的右孩子
            TreeNode rc = p.getRightChild();
            //右孩子的左子树变为该节点的右子树
            p.setRightChild(rc.getLeftChild());
            //改变右孩子的左子树的父母
            if (rc.getLeftChild() != null) {
                rc.getLeftChild().setParent(p);
            }
            //节点的右孩子替代此节点位置,所以需要照顾它的父母
            rc.setParent(p.getParent());
            //如果该节点没有父母，表示它是根节点，rc也就同时代替了根的位置
            if (p.getParent() == null) {
                root.setTreeRoot(rc);
            }else {
                if(p.getParent().getLeftChild()!=null) {
                    if(p.getElement() == p.getParent().getLeftChild().getElement()) {//如果该节点原来为父的左孩子
                        p.getParent().setLeftChild(rc);
                    }
                }else {
                }
                if(p.getParent().getRightChild()!=null) {
                    if(p.getElement() == p.getParent().getRightChild().getElement()) {//如果该节点原来为父的右孩子
                        p.getParent().setRightChild(rc);
                    }
                }else {
                }
            }
            //节点本身变为右孩子的左子树
            rc.setLeftChild(p);
            p.setParent(rc);
        }
    }
    //右旋代码
    private static void rightRotate(TreeNode p) {
        if (p != null) {
            //得到它的左孩子
            TreeNode lc = p.getLeftChild();
          //左孩子的右子树变为该节点的左子树
            p.setLeftChild(lc.getRightChild());
          //改变左孩子的右子树的父母
            if (lc.getRightChild() != null) {
                lc.getRightChild().setParent(p);
            }
            lc.setParent(p.getParent());
            if (p.getParent() == null) {
                root.setTreeRoot(lc);
            }else {
                if(p.getParent().getLeftChild()!=null) {
                    if(p.getElement() == p.getParent().getLeftChild().getElement()) {
                        p.getParent().setLeftChild(lc);
                    }
                }else {
                }
                if(p.getParent().getRightChild()!=null) {
                    if(p.getElement() == p.getParent().getRightChild().getElement()) {
                        p.getParent().setRightChild(lc);
                    }
                }else {
                }
            }
          //节点本身变为左孩子的右子树
            lc.setRightChild(p);
            p.setParent(lc);
        }
    }
  //该节点左边高（平衡因子大于1），要进行左平衡操作
    private static void leftBalance(TreeNode t) {
        //得到节点的左子树
        TreeNode lc = t.getLeftChild();
        //只知道lc是导致t的平衡度除了问题，但是不知道是那种情况，是lc的左边，右边，还是左右平衡，因此需要进行判断
        switch (lc.getBalance()) {
            case 1://lc的左边出了问题，直接进行右旋，但是是旋转t的整个部分
                rightRotate(t);//★★★★标志  下面的情况4
                lc.setBalance(0);
                t.setBalance(0);
                break;
            case -1://lc的右边出了问题 又分3种情况
                TreeNode rc = lc.getRightChild();
                switch (rc.getBalance()) {
                    case 1://★★★★标志  下面的情况2和3
                        lc.setBalance(0);
                        t.setBalance(-1);
                        rc.setBalance(0);
                        break;
                    case -1:
                        t.setBalance(0);
                        rc.setBalance(0);
                        lc.setBalance(1);
                        break;
                    case 0:
                        t.setBalance(0);
                        rc.setBalance(0);
                        lc.setBalance(0);
                        break;
                }
                //统一旋转
                leftRotate(t.getLeftChild());
                rightRotate(t);
                break;
            case 0:
                break;
        }
    }
  //该节点右边高（平衡因子小于-1），要进行右平衡操作
    private static void rightBalance(TreeNode t) {
        //得到节点的右子树
        TreeNode rc = t.getRightChild();
        //判断右子树的平衡因子
        switch (rc.getBalance()) {
            case 1:
                TreeNode lc = rc.getLeftChild();
                switch (lc.getBalance()) {
                    case 1:
                        t.setBalance(0);
                        rc.setBalance(-1);
                        lc.setBalance(0);
                        break;
                    case -1://★★★★标志  下面的情况1
                        t.setBalance(1);
                        rc.setBalance(0);
                        lc.setBalance(0);
                        break;
                    case 0:
                        t.setBalance(0);
                        rc.setBalance(0);
                        lc.setBalance(0);
                        break;
                }
                rightRotate(t.getRightChild());
                leftRotate(t);
                break;
            case -1:
                leftBalance(t);
                //旋转之后节点的平衡度发生了变化
                rc.setBalance(0);
                t.setBalance(0);
                break;
            case 0:
                break;
        }
    }
     //根据某个不平衡的节点对树进行旋转，使其平衡
    private static void fixAfterInsert(TreeNode parent) {
        if (parent.getBalance() == 2) {
            //说明左边高,要进行做平衡操作
            leftBalance(parent);
        } else if (parent.getBalance() == -2) {
            //说明右边高，要进行右平衡操作
            rightBalance(parent);
        }
    }
     //插入一个元素，同时需要计算平衡因子,检查平衡情况，做出旋转调整
    public static boolean insertElement(int element) {
        //树根一个节点都没有，构造节点，作为根节点
        if (root.getTreeRoot() == null) {
            //构造一个新节点 默认父亲为空
            TreeNode t = new TreeNode(element, null);
            root.setTreeRoot(t);
            return true;
        }
        //如果走到这里，说明已经有了根节点，就需要先判断插入的位置
        //这里隐含了一个前提条件，在插入之前，整棵树已经平衡了，
        //实际上这个条件是一定满足的，因为在插入之后，就会判断树是否是平衡的
        //获得根节点
        TreeNode t = root.getTreeRoot();
        do {//把当前结点和父节点比较大小，
            if(element<t.getElement()){//向左走
                if(t.getLeftChild()==null)
                    break;
                t=t.getLeftChild();
            }else if(element>t.getElement()){//向右走
                if(t.getRightChild()==null)
                    break;
                t=t.getRightChild();
            }else {
                //相等就不需要插入
                return false;
            }
            //直到找到叶子
        } while (t!=null);
        //while循环结束之后，就找到了需要插入节点的位置,即在那个叶子下插入，
        // 但是还不能确定是插入在这个叶子的左边，还是右边，这个需要判断
        TreeNode newchild = new TreeNode(element,t);
        //插入左边还是右边
        if (element < t.getElement()) {
            //插入左边
            t.setLeftChild(newchild);
        } else {
            //插入右边
            t.setRightChild(newchild);
        }
        //节点的位置已经找到了，并且成功插入，接下来就要判断新的树是否平衡了
        //因为在插入之前树已经是平衡的了，所以如果树是不平衡的，一定是因为新插入的节点引起的，
        //因此采用回溯法来判断新插入的节点的父节点，爷爷节点。。。等等是否平衡
        TreeNode parent = newchild.getParent();
        while (parent != null) {
            if (element < parent.getElement()) {
                //相当于插在parent的左子树上，因此parent的平衡因子+1
                parent.setBalance(parent.getBalance()+1);
            } else {
                parent.setBalance(parent.getBalance()-1);
            }
            //平衡因子更新完了就需要看是否平衡了
            if (parent.getBalance()==0) {
                //即插入的节点使得树平衡了，说明插入的节点不影响树的平衡性
                break;
            }
            //某一个节点的平衡度最大值只能为2，可能出现的值为-2，-1，0，1，2
            //当为-2，2时，需要调整，这里才出现问题
            if (Math.abs(parent.getBalance()) == 2) {
                fixAfterInsert(parent);
            }
            //如果当前节点没有问题，就接着回溯
            parent = parent.getParent();
        }
        return true;
    }
    public static void main(String[] args) {
        root = new TreeRoot();
        int[] arrays = {37, 31, 43, 10, 40, 55};
        ScanTree scanTree = new ScanTree();
        for(int value:arrays) {
            insertElement(value);
        }
        System.out.println("前序遍历");
        scanTree.preTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("中序遍历");
        scanTree.inTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("后序遍历");
        scanTree.endTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("层序遍历");
        scanTree.cengTraverseBTree(root.getTreeRoot());
        insertElement(8);
        System.out.println("");
        System.out.println("插入8后中序遍历");
        scanTree.inTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("插入8后根的左子树的值");
        System.out.println(root.getTreeRoot().getLeftChild().getElement());
    }
}

上面的例子是如下图

插入8后如下图

运行截图（判断root的左子树）

附上少许其他的旋转情况动态

可以在实现代码上找对应的标志
①情况1

右平衡-右子树的-左子树的-右孩子-高
②情况2
左平衡-左子树的-右子树-右孩子-高
③情况3
左平衡-左子树的-右子树-右孩子-高
④情况4
失横点是66哦
左平衡-左子树的-左孩子-高