- 定義
??在計(jì)算機(jī)科學(xué)中戴尸，AVL樹(shù)是最先發(fā)明的自平衡二叉查找樹(shù)。在AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別為1仙逻，所以它也被稱(chēng)為高度平衡樹(shù)涵但。增加和刪除可能需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。
??在之前的二分搜索樹(shù)中卓鹿，有一個(gè)很大的問(wèn)題菱魔，如果我們添加節(jié)點(diǎn)的順序是有序的留荔，那么樹(shù)將會(huì)退化成鏈表吟孙，導(dǎo)致失去了樹(shù)的優(yōu)勢(shì)澜倦，查詢(xún)的時(shí)間復(fù)雜度變?yōu)榱?O(n)。平衡二叉樹(shù)的出現(xiàn)解決了這種問(wèn)題杰妓，它是一種在添加節(jié)點(diǎn)時(shí)可以自平衡的二叉樹(shù)藻治。
??平衡二叉樹(shù)的高度和節(jié)點(diǎn)數(shù)量之間的關(guān)系是O(logN)的。根據(jù)平衡二叉樹(shù)的性質(zhì)巷挥，左右子樹(shù)的高度差不能超過(guò)一桩卵，所以需要跟蹤每一個(gè)節(jié)點(diǎn)高度，以求出當(dāng)前節(jié)點(diǎn)的平衡因子倍宾，然后通過(guò)旋轉(zhuǎn)重新平衡當(dāng)前樹(shù)雏节，我們可以在二叉搜索樹(shù)的基礎(chǔ)上增加一個(gè)屬性height，如下:
class Node{
E e;
int height;
Node left, right;
}
- 基本使用
??由于AVL樹(shù)和之前的二分搜索樹(shù)類(lèi)似高职，所以我們可以直接使用之前的代碼钩乍，然后將其改造。首先我們添加節(jié)點(diǎn)時(shí)怔锌，我們要更新該節(jié)點(diǎn)和其父節(jié)點(diǎn)的高度寥粹，然后計(jì)算平衡因子（左子樹(shù)高度減去右子樹(shù)高度），如果平衡因子的絕對(duì)值大于一埃元，表示當(dāng)前的樹(shù)已經(jīng)出現(xiàn) "傾斜"涝涤，所以我們必須通過(guò)樹(shù)左旋和右旋完成樹(shù)的重新平衡。
??在添加節(jié)點(diǎn)之后岛杀，如果出現(xiàn)不平衡阔拳，那肯定出現(xiàn)在新節(jié)點(diǎn)的祖先節(jié)點(diǎn)中。所以我們加入節(jié)點(diǎn)之后类嗤，沿著節(jié)點(diǎn)向上維護(hù)平衡性衫生。
（1）LL（右旋轉(zhuǎn)）
??當(dāng)插入的元素在不平衡節(jié)點(diǎn)左側(cè)的左側(cè)時(shí)，可以通過(guò)右旋轉(zhuǎn)來(lái)重新維護(hù)平衡土浸，具體流程如下:
private Node rightRotate(Node root){
Node newRoot = root.left;
root.left = newRoot.right;
newRoot.right = root;
root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
return newRoot;
}
（2）RR（左旋轉(zhuǎn)）
??當(dāng)插入的元素在不平衡節(jié)點(diǎn)右側(cè)的右側(cè)時(shí)罪针，可以通過(guò)右旋轉(zhuǎn)來(lái)重新維護(hù)平衡（和右旋鏡像）。
/*
* 當(dāng)插入的節(jié)點(diǎn)在不平很節(jié)點(diǎn)右側(cè)的右側(cè)黄伊，進(jìn)行左旋轉(zhuǎn)
* y x
* / \ / \
* t4 x y z
* / \ ==> x.left = y; y.right = t3; / \ / \
* t3 z t4 t3 t2 t1
* / \
* t2 t1
* */
private Node leftRotate(Node root){
Node newRoot = root.right;
if(newRoot != null) root.right = newRoot.left;
newRoot.left = root;
root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
return newRoot;
}
（3）LR
??當(dāng)插入的元素在不平衡節(jié)點(diǎn)左側(cè)的右側(cè)時(shí)泪酱，先對(duì)左側(cè)的子節(jié)點(diǎn)進(jìn)行左旋，然后在對(duì)當(dāng)前節(jié)點(diǎn)右旋还最，具體流程如下：
（4）RL
??當(dāng)插入的元素在不平衡節(jié)點(diǎn)的右側(cè)的左側(cè)時(shí)墓阀，先對(duì)右側(cè)的節(jié)點(diǎn)進(jìn)行右旋，然后在對(duì)當(dāng)前的節(jié)點(diǎn)左旋拓轻，具體流程如下:
（5）添加和刪除節(jié)點(diǎn)（詳細(xì)代碼略）
// 左節(jié)點(diǎn)的高度減去右節(jié)點(diǎn)的高度
int balanceFactor = getBanlanceFactor(root);
//當(dāng)插入的節(jié)點(diǎn)在不平衡節(jié)點(diǎn)左側(cè)的左側(cè)斯撮，要進(jìn)行右旋
if(getBanlanceFactor(root) > 1 && getBanlanceFactor(root.left) >= 0){
return rightRotate(root);
}
//當(dāng)插入的節(jié)點(diǎn)在不平衡節(jié)點(diǎn)右側(cè)的右側(cè)，要進(jìn)行左旋
if(getBanlanceFactor(root) < -1 && getBanlanceFactor(root.right) <= 0){
return leftRotate(root);
}
//lr
if(getBanlanceFactor(root) > 1 && getBanlanceFactor(root.left) < 0){
return rightLeftRotate(root);
}
//rl
if(getBanlanceFactor(root) < -1 && getBanlanceFactor(root.right) > 0){
return leftRightRotate(root);
}
