所謂的AVL樹也叫做高度平衡的二叉搜索樹。
啥是高度平衡的二叉搜索樹？
高度平衡的二叉搜索樹：意味著左右子樹的高度最大不超過一。
我們先來回顧一下二叉搜索樹的概念：
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:
- 若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值
- 若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值
- 它的左右子樹也分別為二叉搜索樹
它或許是個完全二叉樹：
在極端情況下又是個單分支的樹：
一個二叉搜索樹的時間復(fù)雜度為：O(N),?極端情況下，例如上圖（左右單支）的情況，樹的高度很高，那么就會導(dǎo)致搜索的效率很低，如果此時有N個樹，樹的高度就為N。
所以我們需要一顆更高效的樹，這就是高度平衡的二叉搜索樹，這也就是為什么需要高度平衡的原因。
AVL樹的概念
二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年 發(fā)明了一種解決上述問題的方法：當向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：
- 它的左右子樹都是AVL樹
- 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
如圖：
?每個結(jié)點旁的數(shù)字代表著其平衡高度，左子樹存在一個為 -1，右子樹存在一個即為1，不存在則為0。
其中，3 結(jié)點上，左子樹的高度為2，所以左子樹的平衡因子應(yīng)該為 -2，右子樹的高度為1，所以右子樹的平衡因子為1，二者相結(jié)合的平衡因子應(yīng)該為：-1。
如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結(jié)點，其高度可保持在? ? ? ? ? ? ? O( logN)，搜索時間復(fù)雜度O( logN)。
實現(xiàn)AVL樹的相關(guān)代碼
AVL樹節(jié)點的定義
AVL樹結(jié)點的定義其實很簡單：
static class TreeNode {
public TreeNode left; // 節(jié)點的左孩子
public TreeNode right; // 節(jié)點的右孩子
public TreeNode parent ; // 節(jié)點的雙親
public int val = 0;
public int bf = 0; // 當前節(jié)點的平衡因子=右子樹高度-左子樹的高度
public TreeNode(int val) {
this.val = val;
}
}
注意：
當前節(jié)點的平衡因子=右子樹高度-左子樹的高度。但是，不是每棵樹，都必須有平衡因子，這只是其中的一種實現(xiàn)方式。
AVL樹的插入
AVL樹就是在二叉搜索樹的基礎(chǔ)上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹。那么AVL樹的插入過程可以分為兩步：
- 按照二叉搜索樹的方式插入新結(jié)點
- 調(diào)節(jié)結(jié)點的平衡因子
這里我們畫圖一步步來講解。
我們先來隨便畫棵樹：
現(xiàn)在我們有這樣一棵AVL樹，我們給它插入一個 5 的結(jié)點。
還是和二叉搜索樹一樣去尋找，從根節(jié)點開始，大于根結(jié)點的值向右走，小于根節(jié)點的向左走，以此類推。
此時，我們需要重新調(diào)節(jié)平衡因子：
此時就需要對整棵樹進行一個旋轉(zhuǎn)。
樹的旋轉(zhuǎn)
右單旋
?既然它不平衡，那就需要想辦法讓他平衡。
??這里只是其中一種旋轉(zhuǎn)，我們再來看看其他情況：
左單旋
我們現(xiàn)在有這樣一棵樹：
?我們新插入一個50：
此時，25 的結(jié)點就不平衡了，我們也需要旋轉(zhuǎn)：
旋轉(zhuǎn)過后：
?由上述的兩種旋轉(zhuǎn)我們看到一個細節(jié)：
?
??
- 不平衡時，該不平衡的結(jié)點和其子節(jié)點的平衡因子必然同號，此時我們只需要單旋即可。
- 并且，平衡因子為負數(shù)需要發(fā)送右旋，平衡因子為正數(shù)需要發(fā)生左旋
- 如若，異號則需要發(fā)生雙旋
左右雙旋
我們還是以發(fā)生右單旋的圖為基礎(chǔ)，我們現(xiàn)在不插入5，而是插入 28 ；
如圖：
?我們可以看出來：30 這個節(jié)點上的平衡因子和 20 這個節(jié)點上的平衡因子異號了。
無論是左單旋還是右單旋都無濟于事。不信可以自己去畫畫圖；
最終結(jié)果如圖所示：
?右左雙旋
?我們在左單旋的基礎(chǔ)上，插入一個值為 26 的結(jié)點，如下圖：
同樣的，無法用單旋來解決問題。
我們需要先右單旋在左單旋；如下圖：
ok，上面只是介紹了單旋是怎么旋轉(zhuǎn)的，接下來要開始講解代碼了。
代碼實現(xiàn)
插入方法代碼
首先，我們要將這個方法設(shè)置為布爾值類型，因為這個方法是有可能無法執(zhí)行的。
AVL樹是基于二叉搜索樹衍生的，二叉搜索樹中是無法實現(xiàn)插入相同的值。
所以這里的插入方法可以參考參考二叉搜索樹。
第一步，需要判斷根節(jié)點是否為空，為空那么這個需要插入的 val 就直接為根結(jié)點就行了。
第二步，開始遍歷，設(shè)置 一個 cur ，一個 parent ，兩個TreeNode ，去找目標 val 應(yīng)該要插入的位置。
ok，目前為止與二叉搜索樹沒有太大差別，我們到這里已經(jīng)找到了目標 val 應(yīng)該插入的為止，還需要解決 平衡因子和轉(zhuǎn)換后各個結(jié)點的關(guān)系。
此時的 node 已經(jīng)是葉子節(jié)點了
為啥這里的循環(huán)條件是parent !=?null，我們來看張旋轉(zhuǎn)圖：
我們圖中，30 是個根節(jié)點嗎？
它也可以是某個結(jié)點的子節(jié)點（故此，我們還需要向上平衡）；直到調(diào)節(jié)到根結(jié)點才算調(diào)整完畢。?
?
兩兩對比，就能總結(jié)出規(guī)律了。?
public boolean insert(int val) {
TreeNode node = new TreeNode(val);
// 根節(jié)點為空
if (root == null) {
root = node;
return true;
}
TreeNode parent = null;
TreeNode cur = root;
while (cur != null) {
if (cur.val < val){
parent = cur;
cur = cur.right;
} else if (cur.val == val) {
return false;
} else {
parent = cur;
cur = cur.left;
}
}
// cur == null
if (parent.val < val) {
parent.right = node;
} else {
parent.left = node;
}
// 當前只是解決了 left 和 right ，還沒有處理 node 的 parent
node.parent = parent;
cur = node;
// 調(diào)節(jié)平衡因子
while (parent != null) {
// 先看 cur 是 parent 的左還是右；此時決定了平衡因子是 ++ 還是 --
if (cur == parent.right) {
parent.bf++;
} else{
parent.bf--;
}
//檢查當前平衡因子是否絕對值 <= 1
if (parent.bf == 0) {
// 記住一個結(jié)論: cur 的 parent 的平衡因子為 0 ，
// 那么它插入一個結(jié)點一定平衡，此時無論插入右子樹還是右子樹都無所謂，就不用往上繼續(xù)調(diào)節(jié)
// 此時已經(jīng)平衡了
break;
} else if (parent.bf == 1 || parent.bf == -1) {
// 此時插入一個結(jié)點，其父節(jié)點未必平衡，需要繼續(xù)向上調(diào)節(jié)
cur = parent;
parent = parent.parent;
} else {
if (parent.bf == 2) {
// 此時說明右樹高，需要先左旋，再右旋
if (cur.bf == 1) {
rotateLeft(parent);
} else {
// cur.bf == -1
rotateRL(parent);
}
} else {
// cur.bf == -2 ;左樹高，需要降低左樹的高度
// 同樣也分平衡因子為 1 和 -1 兩種情況
if (cur.bf == -1) {
// 右旋
rotateRight(parent);
} else {
// cur.bf == 1
rotateLR(parent);
}
}
break;
}
}
return true;
}右單旋
還是需要借助上述的案例來進行講解：
/**
* 右單旋
* @param parent
*/
private void rotateLeft(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
// 旋轉(zhuǎn)關(guān)系 (需要畫圖)
parent.right = subRL;
subR.left = parent;
if (subRL != null) { // subRL 可能為空
subRL.parent = parent;
}
// 與左單旋一樣，需要判斷parent 所在的位置是根節(jié)點還是某個子樹
TreeNode pParent = parent.parent;
parent.parent = subR;
// 為根節(jié)點的情況
if (root == parent) {
root = subR;
root.parent = null;
} else {
// 不為根節(jié)點的情況
if (pParent.left == parent) {
pParent.left = subR;
} else {
pParent.right = subR;
}
subR.parent = pParent;
}
// 調(diào)節(jié)平衡因子
subR.bf = parent.bf = 0;
}這里的parent 是需要插入的葉子結(jié)點的父節(jié)點。
我們首先需要保存一下需要調(diào)整位置的幾個結(jié)點：
第一步：先斷開parent 和 subR 之間的關(guān)系，建立subRL 和 parent 之間的關(guān)系：
?
第二步：斷開subR 和 subRL 之間的關(guān)系，建立subR 和 parent 之間的關(guān)系：
?
當然啦，subRL并非一定存在，它也可以不存在啊，不存在的情況需要特殊處理一下：
?
當然，我們目前只確定了彼此之間的left 和 right ，別忘了我們TreeNode 還定義了 parent，所以目前我們還需要處理一下父節(jié)點的問題。
?
如上圖，我們需要確定parent 這個結(jié)點的位置是否為 根節(jié)點，如果是根結(jié)點那么 subR 的父節(jié)點就是null，如果不是則需要確定具體是 pParent?哪邊：
ok，這里就是右單旋的代碼，接下來看看左單旋；
左單旋
具體代碼：
/**
* 左單旋
* @param parent
*/
private void rotateRight(TreeNode parent) {
// 處理旋轉(zhuǎn)之后幾個節(jié)點的關(guān)系
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
parent.left = subLR;
subL.right = parent;
// subLR 是可能為空的，為空還進行就會報錯！
if (subLR != null) {
subLR.parent = parent;
}
// 必須先記錄父節(jié)點的父節(jié)點（這一段畫圖理解）
TreeNode pParent = parent.parent;
parent.parent = subL;
// 判斷 parent 是否為 根節(jié)點
if(parent == root) {
root = subL;
root.parent = null;
} else {
// 不是根結(jié)點，就判斷這棵樹是左子樹還是右子樹
if (pParent.left == parent) {
pParent.left = subL;
} else {
pParent.right = subL;
}
}
// 全部調(diào)整完畢，還需要調(diào)節(jié) 平衡因子
subL.bf = 0;
parent.bf = 0;
}同樣的，我們得先保存幾個需要調(diào)整位置的結(jié)點，如下圖：
??我們先調(diào)整 幾個結(jié)點之間的left 和 right 的關(guān)系；
第一步，斷開parent 和 subL 之間的關(guān)系，連接 parent 和 subLR 的關(guān)系：
?第二步：斷開subL 和 subLR 的關(guān)系，連接 subL 和 parent 的關(guān)系：
同樣的，subLR并非一定存在，它也可以不存在啊，不存在的情況需要特殊處理一下：
?
?
接下來的操作都一樣：
?
?
右左雙旋
確實雙旋比單旋難不了多少，雙旋是建立在單旋的基礎(chǔ)上的，只需要單旋兩次即可。
先看示意圖：
?
/**
* 右左雙旋
* @param parent
*/
private void rotateLR(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
int bf = subLR.bf;
rotateLeft(parent.left);
rotateRight(parent);
if (bf == -1) {
subL.bf = 0;
subLR.bf = 0;
parent.bf = 1;
} else {
// bf == 1
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}
}
?我們來看看這兩種情況：
于是就變成了這樣：
?
此時的subLR 的平衡因子就是 -1 了，所以需要保留一下sunLR的平衡因子；
旋轉(zhuǎn)還是一樣的旋轉(zhuǎn)，只是旋轉(zhuǎn)以后需要改變不同的平衡因子：
?
同樣的，?左右雙旋也是同理。
這里就不單獨介紹左右雙旋，可以自己畫個圖，然后參考上面右左雙旋的做法。
此外還有一個刪除沒有了解，過后我在此處補齊。
完整代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-529145.html
AVLTree/src/AVLTree.java · wjm的碼云/Projects - 碼云 - 開源中國 (gitee.com)文章來源地址http://www.zghlxwxcb.cn/news/detail-529145.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)進階（一）：AVL樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]-AVL樹](https://imgs.yssmx.com/Uploads/2024/02/758787-1.png)
