平衡二叉搜索樹(shù)：簡(jiǎn)稱平衡二叉樹(shù)。由前蘇聯(lián)的數(shù)學(xué)家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉樹(shù)，根據(jù)科學(xué)家的英文名也稱為 AVL 樹(shù)。它具有如下幾個(gè)性質(zhì)：
1.可以是空樹(shù)。
2.假如不是空樹(shù)，任何一個(gè)結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)都是平衡二叉樹(shù)，并且高度之差的絕對(duì)值不超過(guò) 1。

上篇文章優(yōu)先級(jí)隊(duì)列PriorityQueue源碼分析分析了優(yōu)先級(jí)隊(duì)列PriorityQueue的實(shí)現(xiàn)，PriorityQueue所用的是二叉堆，是一種具備"下沉"和"上移"功能的二叉搜索樹(shù)。二叉搜索樹(shù)在一定程度上可以提高查找效率。但是當(dāng)原本的數(shù)據(jù)趨向于有序時(shí)，如數(shù)據(jù)123456,數(shù)據(jù)結(jié)構(gòu)將會(huì)退化成鏈表，查找時(shí)間復(fù)雜度O(n),這是平衡二叉搜索樹(shù)出現(xiàn)的原因。

鏈表/右斜樹(shù)

平衡因子

平衡因子(Balance Factor)是指某個(gè)節(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度差,平衡二叉樹(shù)的平衡因子只可能是-1,0,1,。如果平衡因子的絕對(duì)值大于1，說(shuō)明此樹(shù)不是平衡二叉樹(shù)。

平衡二叉樹(shù)和非平衡二叉樹(shù)

基礎(chǔ)節(jié)點(diǎn)設(shè)計(jì)

public class BalanceTree<E extends Comparable<E>> {//實(shí)現(xiàn)Comparable，節(jié)點(diǎn)的值必須是可比較的
    private Node root;
    private int size;

    private class Node {
        private E e;
        private Node left;
        private Node right;
        private int height;//height方便計(jì)算平衡因子

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
            this.height = 1;//高度初始值是1
        }
    }

    public BalanceTree() {
        this.root = null;
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    private int getHeight(Node node) {//獲取節(jié)點(diǎn)高度
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    private int getBalanceFactor(Node node) {//獲取節(jié)點(diǎn)平衡因子
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    public boolean isBalance(Node node) {//判斷是否是一顆平衡二叉樹(shù)，需左右子樹(shù)都是平衡二叉樹(shù)
        if (node == null) {
            return true;
        }
        int balanceFactor = Math.abs(getBalanceFactor(node));
        if (balanceFactor > 1) {
            return false;
        }
        return isBalance(node.left) && isBalance(node.right);
    }
}

• 平衡二叉樹(shù)也是二叉搜索樹(shù)，所以節(jié)點(diǎn)的值必須是可比較的，需實(shí)現(xiàn)Comparable
• 為了方便計(jì)算平衡因子的值，設(shè)置height變量
• 平衡因子等于左右子樹(shù)的高度差
• 判斷是否是一顆平衡二叉樹(shù)，需左右子樹(shù)都是平衡二叉樹(shù)

添加節(jié)點(diǎn)

往平衡二叉樹(shù)添加節(jié)點(diǎn)很有可能導(dǎo)致平衡二叉樹(shù)失去平衡，所以每次添加節(jié)點(diǎn)后我們需要進(jìn)行平衡維護(hù)，添加節(jié)點(diǎn)破壞平衡有以下四種情況

• LL(需要右旋)

LL的意思是為往左節(jié)點(diǎn)(L)添加左子節(jié)點(diǎn)(L)導(dǎo)致失去平衡的情況，需要右旋維護(hù)平衡

右旋

新插入的節(jié)點(diǎn)4，比9和5都小，所以插入到5的左邊，9變成了失衡點(diǎn)，所以將失衡點(diǎn)9作為參數(shù)進(jìn)行右旋

    private Node rightRotate(Node imbalance) {
        Node left = imbalance.left;//獲取9的左節(jié)點(diǎn)5
        Node leftRight = left.right;//5的右節(jié)點(diǎn)，這里是null
        left.right = imbalance;//5的右節(jié)點(diǎn)賦值為9
        imbalance.left = leftRight;//5的右節(jié)點(diǎn)放到9的左邊
        
        //右旋影響了9和5的高度，重新計(jì)算賦值
        imbalance.height = Math.max(getHeight(imbalance.left), getHeight(imbalance.right)) + 1;
        left.height = Math.max(getHeight(left.left), getHeight(left.right)) + 1;
        //將新的頭節(jié)點(diǎn)返回 這里是5這個(gè)節(jié)點(diǎn)
        return left;
    }

右旋思路:將失衡點(diǎn)放到失衡點(diǎn)左節(jié)點(diǎn)的右邊，并重新計(jì)算影響到節(jié)點(diǎn)的高度。

• RR(需要左旋)

RR的意思是為往右節(jié)點(diǎn)(R)添加右子節(jié)點(diǎn)(R)導(dǎo)致失去平衡的情況，需要左旋維護(hù)平衡

左旋

新插入的節(jié)點(diǎn)10，比7和9都大，所以插入到9的右邊，7變成了失衡點(diǎn)，將7作為參數(shù)左旋

    private Node leftRotate(Node imbalance) {
        Node right = imbalance.right;//獲取失衡點(diǎn)7的右節(jié)點(diǎn)，這里是9
        Node rightLeft = right.left;//獲取9的左節(jié)點(diǎn)，這里是null
        right.left = imbalance;//將9的左節(jié)點(diǎn)指向7
        imbalance.right = rightLeft;//7的右節(jié)點(diǎn)指向9的原來(lái)的左節(jié)點(diǎn)
         
        //影響了7和9，重新計(jì)算高度賦值
        right.height = Math.max(getHeight(right.left), getHeight(right.right)) + 1;
        imbalance.height = Math.max(getHeight(imbalance.left), getHeight(imbalance.right)) + 1;
        //返回新的根節(jié)點(diǎn)9
        return right;
    }

左旋思路:將失衡點(diǎn)放到失衡點(diǎn)右節(jié)點(diǎn)的左邊，并重新計(jì)算影響到節(jié)點(diǎn)的高度。

• LR(需要先左旋再右旋)

先左旋再右旋

新插入的節(jié)點(diǎn)8，比9小，比7大，所以插在7的右邊，形成LR的情況，先將左節(jié)點(diǎn)7左旋，再將根節(jié)點(diǎn)9右旋

        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {//LR
            //先左旋 再右旋
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

先左旋再右旋思路:先將根節(jié)點(diǎn)的左節(jié)點(diǎn)左旋，再把根節(jié)點(diǎn)右旋

RL(需要先右旋再左旋)

新插入的節(jié)點(diǎn)9，比7大，比7的右節(jié)點(diǎn)10小，所以放在了10的左節(jié)點(diǎn)上。需要先對(duì)10右旋

右旋

然后根節(jié)點(diǎn)7左旋

左旋

        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {//RL
            //先右旋 再左旋
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

先右旋再左旋思路:先將根節(jié)點(diǎn)的右節(jié)點(diǎn)右旋，再把根節(jié)點(diǎn)左旋

添加節(jié)點(diǎn)

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

        int balanceFactor = getBalanceFactor(node);
        if (balanceFactor > 1 && getBalanceFactor(node.left) > 0) {//LL  
            //右旋
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.right) < 0) {//RR
            //左旋
            return leftRotate(node);
        }
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {//LR
            //先左旋 再右旋
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {//RL
            //先右旋 再左旋
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

刪除節(jié)點(diǎn)

    public E remove(E e) {
        Node node = getNode(root, e);
        if (node != null) {
            root = remove(root, e);
            return node.e;
        }
        return null;
    }

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            retNode = node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            retNode = node;
        } else {
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                retNode = rightNode;
            } else if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                retNode = leftNode;
            } else {
                Node successor = minimum(node.right);
                successor.right = remove(node.right, successor.e);
                successor.left = node.left;

                node.left = node.right = null;
                retNode = successor;
            }
        }
        if (retNode == null) {
            return null;
        }
        retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
        int balanceFactor = getBalanceFactor(retNode);
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) > 0) {
            return rightRotate(retNode);
        }
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
            return leftRotate(retNode);
        }
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
            node.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            node.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return node;
    }

整體代碼

public class BalanceTree<E extends Comparable<E>> {
    private Node root;
    private int size;

    private class Node {
        private E e;
        private Node left;
        private Node right;
        private int height;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }

    public BalanceTree() {
        this.root = null;
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    public boolean isBalance(Node node) {
        if (node == null) {
            return true;
        }
        int balanceFactor = Math.abs(getBalanceFactor(node));
        if (balanceFactor > 1) {
            return false;
        }
        return isBalance(node.left) && isBalance(node.right);
    }

    private Node rightRotate(Node imbalance) {
        Node left = imbalance.left;
        Node leftRight = left.right;
        left.right = imbalance;
        imbalance.left = leftRight;

        imbalance.height = Math.max(getHeight(imbalance.left), getHeight(imbalance.right)) + 1;
        left.height = Math.max(getHeight(left.left), getHeight(left.right)) + 1;
        return left;
    }

    private Node leftRotate(Node imbalance) {
        Node right = imbalance.right;
        Node rightLeft = right.left;
        right.left = imbalance;
        imbalance.right = rightLeft;

        right.height = Math.max(getHeight(right.left), getHeight(right.right)) + 1;
        imbalance.height = Math.max(getHeight(imbalance.left), getHeight(imbalance.right)) + 1;
        return right;
    }

    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

        int balanceFactor = getBalanceFactor(node);
        if (balanceFactor > 1 && getBalanceFactor(node.left) > 0) {//LL  
            //右旋
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.right) < 0) {//RR
            //左旋
            return leftRotate(node);
        }
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {//LR
            //先左旋 再右旋
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {//RL
            //先右旋 再左旋
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    private Node getNode(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.equals(node.e)) {
            return node;
        } else if (e.compareTo(node.e) < 0) {
            return getNode(node.left, e);
        } else {
            return getNode(node.right, e);
        }
    }

    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    public E remove(E e) {
        Node node = getNode(root, e);
        if (node != null) {
            root = remove(root, e);
            return node.e;
        }
        return null;
    }

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            retNode = node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            retNode = node;
        } else {
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                retNode = rightNode;
            } else if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                retNode = leftNode;
            } else {
                Node successor = minimum(node.right);
                successor.right = remove(node.right, successor.e);
                successor.left = node.left;

                node.left = node.right = null;
                retNode = successor;
            }
        }
        if (retNode == null) {
            return null;
        }
        retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right)) + 1;
        int balanceFactor = getBalanceFactor(retNode);
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) > 0) {
            return rightRotate(retNode);
        }
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
            return leftRotate(retNode);
        }
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
            node.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            node.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return node;
    }
}