平衡二叉树的简单总结

1、简述

平衡二叉树定义：平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

为什么会有平衡二叉树的出现呢？假设一个树增加元素时递增，则会出现已有一个右树出现。递减会出现只有一个左树的情况。如此二叉树的查询遍历和单链表是一样的复杂度。为了避免这种情况，让左右树平衡达到最高的查询效率，就出现了平衡二叉树。

2、平衡二叉树的旋转算法

主要分为四种旋转：

1、左左旋转， 根左=左右，左右=根
2、右右旋转，根右=右左，右左=跟
3、左右旋转，根的左树先进行右右旋转，然后整个根进行左左旋转
4、右左旋转，根的右树先进行左左旋转，然后整个根进行右右旋转

伪代码描述如下：

public class BTree<K, V> {

    K value;
    V key;

    BTree<K, V> leftTree;
    BTree<K, V> rightTree;
    int height;


    private static BTree llRotation(BTree tree) {
        BTree temTree = tree.leftTree;
        tree.leftTree = temTree.rightTree;
        temTree.rightTree = tree;
        return temTree;
    }

    private static BTree rrRotation(BTree tree) {
        BTree temTree = tree.rightTree;
        tree.rightTree = temTree.leftTree;
        temTree.leftTree = tree;
        return temTree;
    }

    private static BTree lrRotation(BTree tree) {
        tree.leftTree = rrRotation(tree.leftTree);
        return llRotation(tree);
    }

    private static BTree rlRotation(BTree tree) {
        tree.rightTree = llRotation(tree.rightTree);
        return rrRotation(tree);
    }

    public static BTree add(BTree tree, BTree data) {
        if (data.key.hashCode() > tree.key.hashCode()) {
            if (tree.rightTree == null) {
                tree.rightTree = data;
            }
            add(tree.rightTree, data);
            if (Math.abs(tree.leftTree.height - tree.rightTree.height) >= 2) {
                if (data.key.hashCode() > tree.key.hashCode()) {
                    rrRotation(tree);
                }else {
                    rlRotation(tree);
                }
            }
        }else {
            if (tree.leftTree == null) {
                tree.leftTree = data;
            }
            add(tree.leftTree, data);
            if (Math.abs(tree.leftTree.height - tree.rightTree.height) >= 2) {
                if (data.key.hashCode() < tree.key.hashCode()) {
                    llRotation(tree);
                }else {
                    lrRotation(tree);
                }
            }
        }
        return tree;
    }

    public BTree get(K key) {
        BTree tree = null;
        if (key.hashCode() == this.key.hashCode()) {
            tree = this;
        } else if (key.hashCode() < this.key.hashCode()){
            tree = this.leftTree.get(key);
        } else {
            tree = this.rightTree.get(key);
        }
        return tree;
    }


}

参考：https://blog.csdn.net/innobase/article/details/51298037