“不平衡”出現(xiàn)的時(shí)機(jī)
在上一篇 AVL樹基礎(chǔ) 文章中我們最后說到“平衡因子”概念。
在插入新元素后，就可能出現(xiàn)“不平衡”，所以我們就需要去維護(hù)平衡。首先我們圖解分析“不平衡”出現(xiàn)的時(shí)機(jī)。
本文首發(fā)于心安-XinAnzzZ 的個(gè)人博客，轉(zhuǎn)載請(qǐng)注明出處~
可以看到，在插入新的節(jié)點(diǎn)之后，導(dǎo)致了父節(jié)點(diǎn)的高度值變化，從而導(dǎo)致父節(jié)點(diǎn)或者祖先節(jié)點(diǎn)（父節(jié)點(diǎn)的父節(jié)點(diǎn)）的左右子樹的高度差變化，也就出現(xiàn)了“不平衡”的狀態(tài)。
所以，我們就應(yīng)該每次插入新節(jié)點(diǎn)的時(shí)候通過平衡因子的變化來判斷是否導(dǎo)致了父節(jié)點(diǎn)或者祖先節(jié)點(diǎn)“不平衡”，從而來維護(hù)平衡因子，使得這棵樹繼續(xù)平衡。
由于我們的插入的代碼邏輯是遞歸完成的，所以我們維護(hù)了父節(jié)點(diǎn)的平衡，也就遞歸的維護(hù)了祖先節(jié)點(diǎn)的平衡。
在上一篇文章中，我們寫了兩個(gè)輔助函數(shù)，其中一個(gè)就是獲取節(jié)點(diǎn)的平衡因子，這里我們就可以用上了。
在我們遞歸的插入元素的時(shí)候，遞歸的判斷每一個(gè)節(jié)點(diǎn)的平衡因子，遞歸的維護(hù)平衡，從而使整棵樹始終保持平衡。下面我們使用圖形和代碼來講解一下如何通過左旋與右旋使得節(jié)點(diǎn)保持平衡。
圖片演示左旋與右旋
右旋
如上圖所示，插入一個(gè)新節(jié)點(diǎn)之后出現(xiàn)了“不平衡”，我們可以簡(jiǎn)單的將上圖抽象為下圖：
如上圖，T1、T2、T3、T4分別為x、y、z節(jié)點(diǎn)的子樹，根據(jù)二分搜索樹的性質(zhì)，它們之間的大小關(guān)系應(yīng)該是
T1 < z < T2 < x < T3 < y < T4
右旋轉(zhuǎn)就是將x節(jié)點(diǎn)的右子樹先拿掉，然后讓x節(jié)點(diǎn)的有孩子等于y節(jié)點(diǎn)，最后y節(jié)點(diǎn)的左孩子等于剛剛拿掉的x節(jié)點(diǎn)的右孩子。
這里無論T1、T2、T3、T4都是可以為空的，并不影響結(jié)果。右旋如下圖：
可以看到，經(jīng)過右旋之后，二叉樹重新恢復(fù)平衡，并且上面的大小關(guān)系也沒有發(fā)生改變，仍然滿足二分搜索樹的性質(zhì)。
由于添加節(jié)點(diǎn)是遞歸過程，所以右旋之后的子樹的父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)也會(huì)進(jìn)行相應(yīng)的右旋或者左旋使其自身達(dá)到平衡狀態(tài)。
根據(jù)上圖，我們可以編寫我們的右旋轉(zhuǎn)代碼，如下：
/**
* LL
*
* / 對(duì)節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)操作，返回右旋轉(zhuǎn)之后新的根節(jié)點(diǎn)
* / y x
* / / \ / \
* / x T4 向右旋轉(zhuǎn)(y) z y
* / / \ --------------> / \ / \
* / z T3 T1 T2 T3 T4
* / / \
* / T1 T2
*/
private Node rightRotate(Node y) {
Node x = y.left;
// 保存x節(jié)點(diǎn)的右子樹，即使右子樹為空，也沒關(guān)系
Node t3 = x.right;
// 右旋
x.right = y;
// 將原本x的右子樹放在y的左子樹的位置
y.left = t3;
// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
左旋
上圖演示的只是其中一種情況，就是插入的新元素是在第一個(gè)不平衡的節(jié)點(diǎn)的左側(cè)的左側(cè)，所以可以使用右旋轉(zhuǎn)來解決。
另外一種情況就是新插入的元素在第一個(gè)不平衡的節(jié)點(diǎn)的右側(cè)的右側(cè)，這里筆者偷個(gè)懶，不再畫圖。
因?yàn)檫@個(gè)其實(shí)和上面的是對(duì)稱的，筆者可以自己在紙上畫一下，對(duì)比下面的代碼方便理解。
/**
* RR
* <p>
* / 對(duì)節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)操作，返回左旋轉(zhuǎn)之后新的根節(jié)點(diǎn)
* / y x
* / / \ / \
* / T1 x 向右旋轉(zhuǎn)(y) y z
* / / \ --------------> / \ / \
* / T2 z T1 T2 T3 T4
* / / \
* / T3 T4
*/
private Node leftRotate(Node y) {
Node x = y.right;
Node t2 = x.left;
// 右旋
x.left = y;
y.right = t2;
//更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
可以看到，這里的代碼和上面的大同小異，也不需要過多的介紹，下面我們看一下最后兩種情況。
LR
上面兩種情況分別是插入的元素在不平衡節(jié)點(diǎn)的左側(cè)的左側(cè)（LL）、插入的元素在不平衡節(jié)點(diǎn)的右側(cè)的右側(cè)（RR）。
那么還有兩種情況就分別是插入的元素在不平衡節(jié)點(diǎn)的左側(cè)的右側(cè)（LR）、插入的元素在不平衡節(jié)點(diǎn)的右側(cè)的左側(cè)（RL）
對(duì)于插入的元素在不平衡節(jié)點(diǎn)的左側(cè)的右側(cè)（LR），我們可以先進(jìn)行左旋轉(zhuǎn)，使得其轉(zhuǎn)化為插入的元素在不平衡節(jié)點(diǎn)的左側(cè)的左側(cè)（LL），再進(jìn)行右旋轉(zhuǎn)即可。
圖解：
對(duì)x節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)之后就轉(zhuǎn)化為了LL的情況，按照第一種情況進(jìn)行右旋處理即可。
RL
同樣的，和上面想對(duì)稱的就是RL的情況，對(duì)稱處理即可。這里筆者也不再贅述。
直接看一下實(shí)際的代碼。上面我們已經(jīng)寫好了左旋與右旋的代碼，四種情況其實(shí)用到的都是左旋和右旋，所以使用這兩個(gè)函數(shù)即可。
插入一個(gè)元素的代碼：
public void put(K key, V value) {
Node newNode = new Node(key, value);
root = put(root, newNode);
}
/*** 遞歸算法：插入一個(gè)元素，返回插入新節(jié)點(diǎn)后樹的根 */
private Node put(Node node, Node newNode) {
if (node == null) {
size++;
return newNode;
}
if (newNode.key.compareTo(node.key) < 0) {
node.left = put(node.left, newNode);
} else if (newNode.key.compareTo(node.key) > 0) {
node.right = put(node.right, newNode);
} else {
node.value = newNode.value;
}
// 更新高度
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
// 維護(hù)平衡
int balanceFactor = getBalanceFactor(node);
// LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
// 右旋轉(zhuǎn)
return rightRotate(node);
}
// LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
// 先對(duì)當(dāng)前節(jié)點(diǎn)的左孩子進(jìn)行左旋轉(zhuǎn)轉(zhuǎn)變?yōu)長(zhǎng)L，然后在進(jìn)行右旋轉(zhuǎn)
node.left = leftRotate(node.left);
// 右旋轉(zhuǎn)
return rightRotate(node);
}
// RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
// 左旋轉(zhuǎn)
return leftRotate(node);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
// 先對(duì)當(dāng)前節(jié)點(diǎn)的右孩子進(jìn)行右旋轉(zhuǎn)轉(zhuǎn)變?yōu)镽R，然后在進(jìn)行左旋轉(zhuǎn)
node.right = rightRotate(node.right);
// 左旋轉(zhuǎn)
return leftRotate(node);
}
return node;
}
上面的代碼注釋寫的都比較清楚了，讀者只要認(rèn)真思考一下，自己畫一下各種樹的結(jié)構(gòu)，都是可以理解代碼的思想的。
總結(jié)
筆者認(rèn)為AVL樹的維持平衡的思想理解起來相對(duì)來說還是有點(diǎn)難度的，所以這里做一下總結(jié)，希望能幫助到讀者。
首先，AVL樹基于二分搜索樹，不同的是它要求每一個(gè)節(jié)點(diǎn)保持平衡。
那么在插入新元素的時(shí)候就可能會(huì)破壞原本的平衡性（當(dāng)然刪除元素也會(huì)，刪除和添加是逆向操作，如果明白了本章內(nèi)容，刪除操作也是非常簡(jiǎn)單的，這一部分內(nèi)容下一章再進(jìn)行補(bǔ)充），所以就需要我們使用左旋或者右旋進(jìn)行維護(hù)它的平衡。
那么不平衡的情況一共是四種，如下圖：
針對(duì)不同的情況，做不同的旋轉(zhuǎn)即可。再次強(qiáng)調(diào)，由于是遞歸算法，所以其父節(jié)點(diǎn)及祖先節(jié)點(diǎn)都會(huì)相應(yīng)的做出改變來維護(hù)平衡。
本文到這里就結(jié)束了，后面筆者還會(huì)補(bǔ)充一下刪除元素的代碼。感謝閱讀，有任何問題你都可以在評(píng)論區(qū)進(jìn)行評(píng)論，筆者會(huì)在第一時(shí)間給你回復(fù)。
也歡迎加入筆者的qq群交流技術(shù)問題。
