概念：

滿足 “以任意節(jié)點(diǎn)為根的一顆子樹左右高度差≤1” 這個(gè)條件的二叉樹叫做平衡二叉樹

AVL 插入操作:

在講述插入操作之前，需要知道這幾件事:

1. 因?yàn)樵诿看尾迦牍?jié)點(diǎn)之后都會調(diào)整整顆樹為平衡樹,所以在插入節(jié)點(diǎn)之前一定是一棵平衡樹

2. 平衡破壞時(shí)，只需要調(diào)整最小失衡子樹即可

3. 最小失衡子樹在插入節(jié)點(diǎn)之前高度差一定為1，因?yàn)樾虏迦氲墓?jié)點(diǎn)才導(dǎo)致高度差變?yōu)?gt;1

4. 在插入的過程中遇到的最后一個(gè)高度差為1的節(jié)點(diǎn),以這個(gè)節(jié)點(diǎn)為根的子樹的平衡狀態(tài)可能會被破壞.

5. 從被破壞的位置向插入位置的路徑中,所有子樹高度差都為1,而且是由于插入新節(jié)點(diǎn)導(dǎo)致的,在插入之前這條路徑上的所有子樹高度差一定為0.(因?yàn)?)

6. 倒著看,從插入節(jié)點(diǎn)向上查找最小失衡子樹的過程中,若遇到一個(gè)左右子樹高度差為0的節(jié)點(diǎn),那么整棵樹仍是平衡狀態(tài)(高度沒變)

插入操作:

記錄到最后一個(gè)左右子樹高度差不為0的節(jié)點(diǎn)A，因?yàn)橹挥羞@棵子樹才可能成為最小失衡子樹。

判斷左插還是右插.

1. 插入后仍然平衡，最后一個(gè)左右子樹高度差不為0 的子樹此時(shí)高度差變?yōu)?

2. 插入后不平衡，從插入位置往上到最后A路徑上所有子樹高度差此時(shí)變?yōu)?，(之前是0)

1. 往A左孩子的左子樹插。左孩子的左右子樹高度差之前是0，現(xiàn)在變成了1 (右旋操作)

2. 往A左孩子的右子樹插。左孩子的左右子樹高度差之前是0，現(xiàn)在變成了1.(先左旋，后右旋)

3. 往A右孩子的左子樹插…..

4. 往A右孩子的右子樹插…..

   (只有這四種情況.)

a. LL情況

由于A是最后一個(gè)高度差為1的節(jié)點(diǎn)，然后在A左孩子的左子樹上插入，它只能是這種情況(未插入):

B的左右子樹高度一定相同. (因?yàn)锳是最后一個(gè)高度差為一的節(jié)點(diǎn)) ,在插入之后導(dǎo)致了這顆子樹不平衡:

(其中兩個(gè)紅色任意一個(gè)都可以是新插入的節(jié)點(diǎn))

一次右旋即可調(diào)整為平衡樹：

注意觀察，在插入之前這個(gè)子樹的高度是H + 2，此時(shí)整顆樹是平衡二叉樹。

在插入并重新調(diào)整之后，這顆子樹的高度仍然是H + 2，所以并不會影響整顆樹的平衡狀態(tài)，此時(shí)整棵樹仍然是平衡二叉樹。

b.LR情況

這個(gè)就是a情況中往b的右子樹上插入，只不過這里我們還需要考慮一下B的右孩子的情況(插入之前):

還是同樣的原因，由于A是最后一個(gè)左右子樹高度差為1的節(jié)點(diǎn)，所以B的左右子樹高度相同，C的左右子樹高度相同。在插入一個(gè)新的節(jié)點(diǎn)之后變成了這樣:

(圖中新插入的節(jié)點(diǎn)為兩個(gè)紅色節(jié)點(diǎn)中的任意一個(gè))。此時(shí)需要先左旋，轉(zhuǎn)換為1 中的情況:

接著右旋：

此時(shí)這顆子樹就被調(diào)整為了平衡二叉樹，且它的高度是H+2，與插入之前這顆子樹的高度一樣。所以在插入之前整棵樹是平衡狀態(tài)，在插入并且調(diào)整之后整棵樹仍然是平衡狀態(tài)。

RL與RR情況與上面兩種情況類似，這里就不詳細(xì)說明了。

為什么只需要調(diào)整最小失衡子樹就行？

在a,與b兩種情況中應(yīng)該容易看出，我們調(diào)整的都是最小的那顆失去平衡的樹。在插入之前與調(diào)整之后這顆子樹的高度不變，不會影響整顆樹的平衡狀態(tài)。

刪除操作:

如果要?jiǎng)h除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，我們找一個(gè)葉子節(jié)點(diǎn)與要?jiǎng)h除的節(jié)點(diǎn)交換位置。

現(xiàn)在我們只需要考慮刪除葉子節(jié)點(diǎn)即可。

刪除葉子節(jié)點(diǎn)可能會導(dǎo)致某一棵子樹平衡狀態(tài)破壞，注意如果某棵子樹的平衡狀態(tài)破壞，那么調(diào)整之后，這顆子樹的高度會減1，那么之后還可能會破壞其他子樹的平衡狀態(tài)。所以需要調(diào)整以 ”從葉子到根路徑上所有節(jié)點(diǎn)為根“ 的子樹的平衡狀態(tài)。但是即使破壞了平衡狀態(tài)，高度差最大不會超過2。

插入操作的一種實(shí)現(xiàn)方式：