平衡二叉树详解（逻辑加代码）

目的：提高查找效率

判断平衡：任意一个结点的左子树和右子树的高度差不能超过绝对值1

平衡因子：1,0，-1

如何平衡：旋转

左旋

1. 失衡结点的右孩子代替结点的位置
2. 右孩子的左子树变成失衡结点的右子树
3. 该失衡结点变成它右孩子的左子树

右旋

1. 失衡结点的左孩子代替它的位置
2. 失衡结点的左孩子的右子树变成失衡结点的左子树
3. 失衡结点变成左孩子的右子树

插入情况分析：

• 如果插入的结点在失衡结点的左孩子的左子树上面，只进行一次右旋
• 当插入的结点在失衡结点的左孩子的右子树上面（如果进行右旋，右子树在右旋第二步变成了失衡结点的左子树，加上第三步把失衡结点连为右子树相当于又多加了一层，导致依旧失衡），先进行失衡结点左孩子的左旋，再进行失衡结点的右旋（注意旋点）
• 如果插入的结点在失衡结点的右孩子的右子树上面，只进行一次左旋
• 当插入的结点在失衡结点的右孩子的左子树上面，先进行失衡结点右孩子的右旋，再进行失衡结点左旋

删除情况分析：

• 删除的结点是叶子结点
• 删除的结点只有左子树
• 删除的结点只有右子树
• 删除的结点既有左子树又有右子树

package Tree.AVLTree;

import java.util.ArrayList;
import java.util.List;

public class AVLTree {
    public AVLTreeNode root;

    
    public int getHeight(AVLTreeNode node) {
        if (node == null) {
            return 0;
        }
        int left= (node.leftNode == null ? 0 : node.leftNode.height) ;
        int right=(node.rightNode == null ? 0 : node.rightNode.height);
        return Math.max(left,right);
    }

    public void insert(int data) {
        root = insert(data, root);
    }

    
    public AVLTreeNode insert(int data, AVLTreeNode node) {
        if (node == null) {
            node = new AVLTreeNode(data);
        }
        if (data < node.data) {
            node.leftNode = insert(data, node.leftNode);
            //作为左子树插入，只可能左子树高
            if (getHeight(node.leftNode) - getHeight(node.rightNode) == 2) {
                if (data < node.leftNode.data) {
                    //左子树的左孩子，右旋
                    node = rightRotate(node);
                } else{
                    //左子树的右孩子，先左旋再右旋
                    node = leftRightRotate(node);
                }
            }
        }
        if(data>node.data){
            node.rightNode = insert(data,node.rightNode);
            //作为右子树插入，只可能右子树高
            if(getHeight(node.rightNode)-getHeight(node.leftNode)==2){
                if(datagetHeight(node.rightNode.rightNode)){
                    node = rightLeftRotate(node);
                } else{
                    node = leftRotate(node);
                }
            }
        } else if(data > node.data){
            node.rightNode = deleteNode(data,node.rightNode);
            if(getHeight(node.leftNode)-getHeight(node.rightNode)==2){
                if(getHeight(node.leftNode.rightNode)>getHeight(node.leftNode.leftNode)){
                    node = leftRightRotate(node);
                } else{
                    node = rightRotate(node);
                }
            }

        } else if(node.leftNode !=null&&node.rightNode != null){
            //删除的结点既有左子树也有右子树
            node.data = findMin(node.rightNode).data;
            node.rightNode = deleteNode(node.data,node.rightNode);
        } else {
            //删除的结点只有一个孩子或者为叶子结点
            node = (node.leftNode != null) ? node.leftNode : node.rightNode;
        }

        node.height = getHeight(node) + 1;
        return node;
    }

    
    public AVLTreeNode findMin(AVLTreeNode node){
        if(node.leftNode == null){
            return node;
        }else{
            return findMin(node.leftNode);
        }

    }
}