目錄

二叉樹

二叉搜索樹的查找方式：

AVL樹

AVL樹節(jié)點的實現(xiàn)

AVL樹節(jié)點的插入操作

AVL樹的旋轉(zhuǎn)操作

右旋轉(zhuǎn)：

左旋轉(zhuǎn)：

左右雙旋：

右左雙旋：

AVL樹的不足和下期預(yù)告（紅黑樹）

---

二叉樹

了解AVL樹之前，需要先了解一下二叉搜索樹的概念，二叉搜索樹具有以下性質(zhì)：

1，如果左子樹不為空，則左子樹上所有節(jié)點的值都小于跟節(jié)點的值。

2，如果右子樹不為空，則右子樹的所有節(jié)點的值都大于跟節(jié)點的值。

3，根節(jié)點的左右子樹也是一顆二叉搜索樹。

如果使用二叉樹的中序遍歷方法來遍歷一顆二叉樹，則可以得到一個有序的序列。

二叉搜索樹的查找方式：

根據(jù)上圖可以對二叉樹進行查找從而得到我們想要的節(jié)點。

一個完全二叉樹的查找效率可以達(dá)到??級別，但如果我們插入的數(shù)值都是大于根節(jié)點的數(shù)值，并且是嚴(yán)格遞增的，那么此時整個二叉樹就會退化成一個鏈表的結(jié)構(gòu)，那么此時查找的效率也會退化成。因此我們就需要考慮一個問題，無論何時進行插入，都可以讓二叉樹，保持左右子樹的相對平衡，隨時更改根節(jié)點，這樣就可以讓查找的時間復(fù)雜度一直保持在,所以研究者引入了AVL樹的概念。

AVL樹

在計算機科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。AVL樹得名于它的發(fā)明者G. M. Adelson-Velsky和E. M. Landis，他們在1962年的論文《An algorithm for the organization of information》中發(fā)表了它。

AVL樹它本質(zhì)上其實還是一個二叉樹，它的特點符合二叉樹的所有特點，在此之外，AVL樹還具有平衡的性質(zhì)，也就是說，它的左子樹和右子樹的高度差的絕對值不會大于1，因此這樣也就保證了AVL樹的查找效率。

AVL樹節(jié)點的實現(xiàn)

為了實現(xiàn)AVL樹，我們需要先定義樹的節(jié)點，和普通的二叉樹不同，在定義節(jié)點的時候，我們也需要在其中定義一個平衡因子，我們使用bf（balance factor）來表示：AVL樹的節(jié)點定義如下：

class TreeNode{//定義樹的左右節(jié)點索引和父親索引public TreeNode left = null;public TreeNode right = null;public TreeNode parent = null;public int val;public int bf;//定義構(gòu)造函數(shù)public TreeNode (int val){this.val = val;}
}

我們定義當(dāng)前節(jié)點的平衡因子 = 右樹的高度 - 左樹的高度。如果當(dāng)前節(jié)點的bf<0，那么左樹就高，bf>0右樹就高。bf = 0,那么兩邊一樣高。當(dāng)然這只是其中的一種實現(xiàn)方式而已（本文是這么定義的）。

AVL樹節(jié)點的插入操作

首先，我們將其分為兩步

1，按照二叉樹的插入方式進行插入。

2，對不滿足條件的節(jié)點進行旋轉(zhuǎn)，使樹達(dá)到平衡。

此時可以看下接下來這幾幅圖：

假設(shè)我要在二叉樹種插入一個值為100，那么此時我應(yīng)該找到100應(yīng)該插入到哪個位置，每一次尋找定義cur為要插入的位置，定義parent為cur的父親節(jié)點，那么遍歷下來就可以找到插入的位置，此時代碼如下：

    public TreeNode root ;public void insert(int val){//1,首先先進行節(jié)點的插入操作;TreeNode node = new TreeNode(val);if(this.root == null){//如果樹為空，那么node就是新的rootthis.root = node;}else{TreeNode parent = null;TreeNode cur = this.root;// 1.1 先判斷要插入的位置，然后再進行插入while(cur != null){if(cur.val < val){parent = cur;cur = cur.right;} else if (cur.val == val) {return;}else{parent = cur;cur = cur.left;}}//此時找到了要插入的位置，對node進行插入，插入的位置為parent所指向的節(jié)點//判斷往左邊插入還是右邊插入，然后再讓node指回去。if(parent.val < val){parent.right = node;}else{parent.left = node;}node.parent = parent;cur = node;}}

一定要讓node指向指回去，否則子節(jié)點會丟失父節(jié)點的索引。

AVL樹的旋轉(zhuǎn)操作

基于以上的插入，我們可以發(fā)現(xiàn)一個問題，就是說，如果每次都插入比上一次大的值，那么勢必會讓這個樹退化成一個鏈表，那么此時樹的存儲結(jié)構(gòu)優(yōu)勢將會丟掉，所以AVL樹引入了旋轉(zhuǎn)操作來對樹進行操作。從而使得這棵樹不會退化成鏈表。

cur插入后，parent的平衡因子一定需要調(diào)整，

在插入之前，parent的平衡因子分為三種情況：-1，0, 1

插入時分以下兩種情況： ?

1. 如果cur插入到parent的左側(cè)，只需給parent的平衡因子 -1 即可 ?

2. 如果cur插入到parent的右側(cè)，只需給parent的平衡因子 +1 即可 ?

此時：parent的平衡因子可能有三種情況：0，正負(fù)1， 正負(fù)2 ?

1. 如果parent的平衡因子為0，說明插入之前parent的平衡因子為正負(fù)1，插入后被調(diào)整成0，此時滿足AVL樹的性質(zhì)，插入成功

2. 如果parent的平衡因子為正負(fù)1，說明插入前parent的平衡因子為0，插入后被更新成正負(fù)1，此時以parent為根的樹的高度增加，需要繼續(xù)向上更新 ?

3. 如果parent的平衡因子為正負(fù)2，則parent的平衡因子違反平衡樹的性質(zhì)，需要對其進行旋轉(zhuǎn)處理

此時更新操作就如下：

            while(){//更新parent的平衡因子if(cur == parent.right){parent.bf++;}else{parent.bf--;}//更新后的平衡因子為0，說明插入后的結(jié)果是平衡的，此時無需后續(xù)操作if(parent.bf == 0){return;}if(parent.bf != 1 && parent.bf != -1){//此時需要繼續(xù)向上更新if(parent.bf == 2){if(cur.bf == 1){// parent.bf == 2 cur.bf == 1}else{// parent.bf == 2 cur.bf == -1}}else{if(cur.bf == 1){// parent.bf == -2 cur.bf == 1}else{// parent.bf == -2 cur.bf == -1}}}}

那么基于以上操作，我們的更新平衡因子的模板已經(jīng)搭好了，但是在什么情況下需要進行旋轉(zhuǎn)呢？

右旋轉(zhuǎn)：

假設(shè)有上面這種情況，原來的cur.bf == 0 ， 但是parent.bf == -1 ,此時在左樹的最左邊插入一個節(jié)點，那么此時的節(jié)點情況就變成了cur.bf == -1 , parent.bf == -2 。那么此時就需要對parent節(jié)點進行右旋轉(zhuǎn)，從而調(diào)整樹的結(jié)構(gòu)。

此時需要注意以下幾點：

?1.? 30 節(jié)點的右孩子可能存在，也可能不存在。

?2.? 60 可能是根節(jié)點，也可能是子樹。如果是根節(jié)點，旋轉(zhuǎn)完成后，要更新根節(jié)點 ? ? 如果是子樹，可能是某個節(jié)點的左子樹，也可能是右子樹。

在上圖中可以看出，當(dāng)我們想進行右轉(zhuǎn)操作時，需要將parent.left 標(biāo)記為 subL，將subL.right標(biāo)記為subLR.

從2圖轉(zhuǎn)換為3圖可以如上圖表示：

1. 修改parent.left = subLR;

2. 修改subL.right = parent;

3. 修改 subLR.parent = parent （此時需要判斷subLR是否為空）

4. 保存parent的父親節(jié)點（祖父節(jié)點）

5. 修改parent的父親節(jié)點指向subL；

6. 修改祖父節(jié)點指向subL（需要確認(rèn)祖父節(jié)點是否存在，如果不存在則parent是根節(jié)點）

7. 修改subL.parent屬性為祖父節(jié)點；

8. 判斷完了之后還要修改平衡因子。

代碼如下：

private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;subL.right = parent;if(subLR != null){subLR.parent = parent;}TreeNode pParent = parent.parent;parent.parent = subL;if(parent == this.root){this.root = subL;this.root.parent = null;}else{if(pParent.left == parent){pParent.left = subL;}else{pParent.right = subL;}subL.parent = pParent;}subL.bf = 0;parent.bf = 0;}

左旋轉(zhuǎn)：

左旋轉(zhuǎn)和右旋轉(zhuǎn)的邏輯是一樣的，不過是對稱的操作。以下是左旋轉(zhuǎn)的代碼演示：

此時最初的parent的bf值為1，進行添加節(jié)點之后，則是會變成parent.bf 會變成2，此時的cur.bf

會變成1（因為給cur的右樹增加了一層）。此時就需要用到左旋轉(zhuǎn)的方法來進行旋轉(zhuǎn)，從而降低AVL樹的高度了。具體代碼如下：和右旋轉(zhuǎn)是對稱的

 private void rotateLeft(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;parent.right = subRL;subR.left = parent;if(subRL != null){subRL.parent = parent;}TreeNode pParent = parent.parent;parent.parent = subR;if(parent == this.root){this.root = subR;this.root.parent = null;}else{if(pParent.left == parent){pParent.left = subR;}else{pParent.right =subR;}subR.parent = pParent;}subR.bf = parent.bf = 0;}

左右雙旋：

?講完了上述兩種比較簡單的情況，其實還有兩種比較復(fù)雜的情況，比如說，

假如說是上面這種情況呢，此時我要插入的值為40，但是60節(jié)點bf更新為-2，此時的30這個節(jié)點的bf值為1，50節(jié)點bf值為-1，這時候單純的旋轉(zhuǎn)已經(jīng)無法解決這些問題了。因此

此時先對30進行左旋轉(zhuǎn)：可以得到50節(jié)點bf為-2，60節(jié)點 bf 為-2，30節(jié)點 bf 為 0

此時再對60節(jié)點進行右旋轉(zhuǎn)：此時的50節(jié)點 bf 為 0 ，60節(jié)點bf為 1 此時的 AVL樹已經(jīng)達(dá)到了平衡。

private void rotateLR(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;int bf = subLR.bf;this.rotateRight(parent.left);this.rotateLeft(parent);if (bf == -1) {parent.bf = 1;subL.bf = 0;subLR.bf = 0;} else if (bf == 1) {subL.bf = -1;subLR.bf = 0;parent.bf = 0;}
}

右左雙旋：

和左右雙旋是對稱的概念，此處便不再贅述了。

直接貼代碼：

 private void rotateRL(TreeNode parent) {TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;this.rotateRight(parent.right);this.rotateLeft(parent);if(bf == 1){parent.bf = -1;subR.bf = 0;subRL.bf = 0;} else if (bf == -1) {parent.bf = 0;subR.bf = 1;subRL.bf =0;}}

總之AVL樹，就是為了讓整個樹不退化成鏈表，才引入的旋轉(zhuǎn)機制。

AVL樹的不足和下期預(yù)告（紅黑樹）

但是AVL樹雖然保證了查詢的效率，但是還是有一些機制上的問題，比如說，旋轉(zhuǎn)非常消耗時間，比如我們在單旋的時候已經(jīng)進行了8步操作，這只是其中的一次插入，當(dāng)數(shù)據(jù)大量插入的時候AVL樹顯然是不夠用的，因此科學(xué)家們又引入了紅黑樹的機制。下一次我會繼續(xù)寫關(guān)于紅黑樹的博客，希望大家能夠多多點贊。