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

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

圖1

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

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

圖2

圖3

再看圖2，根據(jù)搜索二叉樹的性質(zhì)，肯定有D>B>A，E>B，因此旋轉(zhuǎn)過后，能夠保證 右子節(jié)點(diǎn) > 父節(jié)點(diǎn) > 左子節(jié)點(diǎn)，不會(huì)破壞樹的結(jié)構(gòu)。
可以看到，一次左單旋將右側(cè)子樹的高度減小了1，而左側(cè)子樹的高度增加了1。實(shí)現(xiàn)代碼如下：

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

右單旋與左單選類似，以某一節(jié)點(diǎn)B（圖4）做右單旋，首先斷開B與其父節(jié)點(diǎn)A的連接，將B的左子節(jié)點(diǎn)C與A連接，將C的右子節(jié)點(diǎn)F作為B的左子節(jié)點(diǎn)。同樣的，因?yàn)橛蠧>A，B>F>C，因此旋轉(zhuǎn)過后，不會(huì)破壞樹的結(jié)構(gòu)。可以看到，一次右單旋使節(jié)點(diǎn)的左側(cè)子樹高度減小了1，而右側(cè)子樹的高度增加了1。

圖4

實(shí)現(xiàn)代碼如下：

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

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

圖5

因此為了達(dá)到目的，需要先對(duì)旋轉(zhuǎn)節(jié)點(diǎn)的左子節(jié)點(diǎn)做左單旋，再對(duì)旋轉(zhuǎn)節(jié)點(diǎn)做右單旋。如圖6所示，先對(duì)節(jié)點(diǎn)B的左子節(jié)點(diǎn)C做左單旋，可以看到，這個(gè)操作，相當(dāng)于將節(jié)點(diǎn)C的不平衡性從右側(cè)轉(zhuǎn)移到了左側(cè)，從而滿足了上述右單旋的條件；最后再對(duì)B節(jié)點(diǎn)做右單旋操作，最終達(dá)到了平衡的目的。

圖6

實(shí)現(xiàn)代碼如下：

function roateLeftRight(AvlNode) {
        AvlNode.right = roateLeft(AvlNode.right); // 對(duì)右子節(jié)點(diǎn)做左單旋
        return roateRight(AvlNode); // 做右單旋
}

同理，如圖2，對(duì)B進(jìn)行左單旋時(shí)，需要右子樹D的右子樹F的高度大于等于左子樹E的高度，否則需要進(jìn)行雙旋；即先對(duì)B的右子節(jié)點(diǎn)D做右單旋，再對(duì)B做左單旋。實(shí)現(xiàn)代碼如下：

function roateRightLeft(AvlNode) {
        AvlNode.left = roateRight(AvlNode.left); // 對(duì)左子節(jié)點(diǎn)做右單旋
        return roateLeft(AvlNode); // 做左單旋
}

首先實(shí)現(xiàn)獲取樹高度的函數(shù)：

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;
        }
}

實(shí)現(xiàn)平衡樹的函數(shù)：

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)) {
            // 如果左子樹的左子樹高度大于等于左子樹的右子樹高度
            // 直接進(jìn)行右單旋
            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)) {
            // 如果右子樹的右子樹高度大于等于右子樹的左子樹高度
            // 直接進(jìn)行左單旋
            node = roateLeft(node);
        } else {
            // 否則需要左-右雙旋
            node = roateLeftRight(node);
        }
    }
    return node;
}

在二叉搜索樹的基礎(chǔ)上，每次插入節(jié)點(diǎn)，都需要做一次樹的平衡處理：

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

綜上，一顆自平衡AVL樹的原理及實(shí)現(xiàn)就完成了。