摘要：可以看到，一次左單旋將右側子樹的高度減小了，而左側子樹的高度增加了。如圖，對進行右單旋，需要左子樹的右子樹的高度小于等于左子樹的高度，否則不能達到平衡的效果，只是把不平衡性從左邊轉移到了右邊。

普通二叉搜索樹可能出現一條分支有多層，而其他分支卻只有幾層的情況，如圖1所示，這會導致添加、移除和搜索樹具有性能問題。因此提出了自平衡二叉樹的概念，AVL樹（阿德爾森-維爾斯和蘭迪斯樹）是自平衡二叉樹的一種，AVL樹的任一子節點的左右兩側子樹的高度之差不超過1，所以它也被稱為高度平衡樹。

圖1

要將不平衡的二叉搜索樹轉換為平衡的AVL樹需要對樹進行一次或多次旋轉，旋轉方式分為左單旋、右單旋、左-右雙旋、右-左雙旋。

對某一節點B（圖2）做左單旋，處理過程相當于，斷開B與父節點A的連接，將B的右子節點D與A連接，將B作為D的左子節點，將D的左子節點E作為B的右子節點。以圖1的二叉樹為例，對鍵值為15的節點做左單旋，首先斷開15與11的連接，再將20與11連接，將15作為20的左子節點，最后將18作為15的右子節點；可以想象為以15為中心做了一定的逆時針旋轉。結果如圖3。

圖2

圖3

再看圖2，根據搜索二叉樹的性質，肯定有D>B>A，E>B，因此旋轉過后，能夠保證 右子節點 > 父節點 > 左子節點，不會破壞樹的結構。
可以看到，一次左單旋將右側子樹的高度減小了1，而左側子樹的高度增加了1。實現代碼如下：

function roateLeft(AvlNode) {
        var node = AvlNode.right; // 保存右子節點
        AvlNode.right = node.left; // node的左子節點連接到AvlNode成為其右子節點
        node.left = AvlNode; // AvlNode連接到node成為其左子節點
        return node; // 返回node，連接到AvlNode最初的父節點
}

右單旋與左單選類似，以某一節點B（圖4）做右單旋，首先斷開B與其父節點A的連接，將B的左子節點C與A連接，將C的右子節點F作為B的左子節點。同樣的，因為有C>A，B>F>C，因此旋轉過后，不會破壞樹的結構。可以看到，一次右單旋使節點的左側子樹高度減小了1，而右側子樹的高度增加了1。

圖4

實現代碼如下：

function roateRight(AvlNode) {
        var node = AvlNode.left; // 保存左子節點
        AvlNode.left = node.right; // 將node的右子節點連接到AvlNode成為其左子節點
        node.right = AvlNode; // AvlNode連接到node，成為其右子節點
        return node; // 返回node連接到AvlNode最初的父節點
}

左單旋、右單旋在某些情況下是不能達到平衡樹的目的的。如圖4，對B進行右單旋，需要左子樹C的右子樹F的高度小于等于左子樹E的高度，否則不能達到平衡的效果，只是把不平衡性從左邊轉移到了右邊。圖5演示了這種情況。同樣的，左單旋也有這個問題。

圖5

因此為了達到目的，需要先對旋轉節點的左子節點做左單旋，再對旋轉節點做右單旋。如圖6所示，先對節點B的左子節點C做左單旋，可以看到，這個操作，相當于將節點C的不平衡性從右側轉移到了左側，從而滿足了上述右單旋的條件；最后再對B節點做右單旋操作，最終達到了平衡的目的。

圖6

實現代碼如下：

function roateLeftRight(AvlNode) {
        AvlNode.right = roateLeft(AvlNode.right); // 對右子節點做左單旋
        return roateRight(AvlNode); // 做右單旋
}

同理，如圖2，對B進行左單旋時，需要右子樹D的右子樹F的高度大于等于左子樹E的高度，否則需要進行雙旋；即先對B的右子節點D做右單旋，再對B做左單旋。實現代碼如下：

function roateRightLeft(AvlNode) {
        AvlNode.left = roateRight(AvlNode.left); // 對左子節點做右單旋
        return roateLeft(AvlNode); // 做左單旋
}

首先實現獲取樹高度的函數：

function getAvlTreeHeight(node) {
        if (node == null) {
            // node不存在返回0
            return 0;
        } else {
            var leftHeight = getAvlTreeHeight(node.left);
            var rightHeight = getAvlTreeHeight(node.right);
            // 返回左子樹、右子樹中的最大高度
            return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
        }
}

實現平衡樹的函數：

function balance(node) {
    if (node == null) {
        return node;
    }
    // 左子樹高度比右子樹高度大1以上
    if (getAvlTreeHeight(node.left) - getAvlTreeHeight(node.right) > 1) {
        if (getAvlTreeHeight(node.left.left) >= getAvlTreeHeight(node.left.right)) {
            // 如果左子樹的左子樹高度大于等于左子樹的右子樹高度
            // 直接進行右單旋
            node = roateRight(node);
        } else {
            // 否則需要右-左雙旋
            node = roateRightLeft(node);
        }
        // 右子樹高度比左子樹高度大1以上
    } else if (getAvlTreeHeight(node.right) - getAvlTreeHeight(node.left) > 1) {
        if (getAvlTreeHeight(node.right.right) >= getAvlTreeHeight(node.right.left)) {
            // 如果右子樹的右子樹高度大于等于右子樹的左子樹高度
            // 直接進行左單旋
            node = roateLeft(node);
        } else {
            // 否則需要左-右雙旋
            node = roateLeftRight(node);
        }
    }
    return node;
}

在二叉搜索樹的基礎上，每次插入節點，都需要做一次樹的平衡處理：

var insertNode = function(node, newNode){
    if (newNode.key < node.key){
        if (node.left === null){
            node.left = newNode;
            // 插入節點后，做樹的平衡處理
            node.left = balance(node.left);
        } else {
            insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null){
            node.right = newNode;
            // 插入節點后，做樹的平衡處理
            node.right = balance(node.right);
        } else {
            insertNode(node.right, newNode);
        }
    }
}

綜上，一顆自平衡AVL樹的原理及實現就完成了。