對于二叉搜索樹 ， 平衡二叉樹 ， 以及紅黑樹 ， 目前只需要了解背后的原理 ， 不做代碼實現的要求 ， 重要的就是了解各種操作的時間復雜度即可 ， 為set 與 map 做鋪墊

?

一、二叉搜索樹

1.1 基本概念

構造一棵二叉搜索樹的目的? ， 并不是為了排序，而是為了提高查找和輸入刪除關鍵字的速度。

1.2 查找操作

二叉搜索樹的查找是從根結點開始 ，沿某個分支逐層向下比較的過程，若二叉搜索樹非空，先將給定值與根結點的關鍵字比較，若相等，則查找成功；若不等，如果小于根結點的關鍵字，則在根結點的左子樹上查找，否則在根結點的右子樹上查找。二這也是?個遞歸的過程。

根據BST的特性（左 < 根 < 右 )

從根結點開始一路向下找

最壞情況下會從根節點開始，查找到葉子結點。因此時間復雜度是和樹的高度有關的，而樹高最差會 變成一條單鏈表，因此時間復雜度為 O(N)

1.3 插入操作

根據BST的特性（左 < 根 < 右 )

從根結點開始一路向下找，找到合適的位置，就直接插入

插入與查找的過程一致，因此時間復雜度為 O(N)?

1.4 構造 BST 樹

二叉搜索樹的構建就是不斷向原來的樹中插入新的結點即可。

在極端條件下 ， 時間復雜度為 O(N)? --->?oh my god ! 驟增了！！！??

在上面兩個構造二叉排序樹的過程中 ， 雖然結點的值都相同 ， 不同的構造順序會有不同的二叉搜索樹 ， 會影響查找和插入的效率 。 并且 ， 構造序列越有序 ， 二叉搜索樹的查找效率就越低 。

1.5 刪除操作

對于第三個刪除結點的情況 ， 我們一般是把它變成情況一或二

1）若被刪除結點是葉子結點，則直接刪除? ?

----> 此時依舊會保持二叉搜索樹的性質

2）若被刪除結點只有左子樹或者右子樹，讓左子樹或者右子樹替代

??----> 此時依舊會保持二叉搜索樹的性質

3）若被刪除結點有左子樹和右子樹

刪除10這個結點：

注意：我們創建二叉搜索樹其實并不是為了排序 ， 而是為了快速插入、刪除 以及查找元素。因為BST不是那么極端的話 ， 樹高維持在? logN 的范圍 ， 上述的各種操作其實是很快的 。 但是二叉搜索樹的特性并不杜絕極端情況的出現 ！！！

二、平衡二叉樹

在介紹二叉搜索樹的時候 ，?在某些特定的情況下 ， 二叉搜索樹是會退化成單鏈表 ， 并且各種操作的效率也會明顯下降 。因此我們需要一些特別的手段保證這個二叉搜素樹的“平衡”，進而保證各種操作的效率 。

2.1 基本概念

平衡二叉樹 ， 也稱AVL樹 ， 它是具有以下性質的二叉搜索樹：

1 ） 左右子樹的高度差的絕對值不超過1

2 ） 左右子樹分別也是平衡二叉樹

如下圖所示 ， 結點上方的數字表示平衡因子 。 左圖是一棵平衡二叉樹，右圖不是！

2.2 查找操作

平衡二叉樹的查找 、 插入 以及 刪除操 作基本上與二叉搜索樹一致?， 但是需要處理操作之后的“失衡” 。

重點需要掌握兩種處理失衡的操作：

1） 左旋

2） 右旋

由于平衡二叉樹會限制樹的高度不會過高? ，趨近于 log n 級別 ， 因此時間復雜度為 O(logN）

左旋（結點1）的時候遇到（結點2）?“擋著了” ，?

1 ） 結點1?成為右孩子的左子樹

2 ） 右孩子原本的左子樹（結點2）成為該結點（結點1）的右子樹

右旋（結點1）的時候遇到（結點2）?“擋著了” ，?

1 ） 結點1?成為左孩子的右子樹

2 ） 左孩子原本的右子樹（結點2）成為該結點（結點1）的左子樹

2.3 插入操作

最小不平衡子樹：

在?叉搜索樹中插入新結點之后，插入路徑的點中，可能存在很多平衡因子的絕對值大于 1 的，此時找到 距離插入結點最近的不平衡的點 ，以這個點為根的 子樹 就是 最小不平衡子樹 。

2.3.1 LL型 - 右單旋

LL 表示： 新結點由于插入在 T 結點的左孩子(L)的左子樹(LL)中 ，從而導致失衡。如下圖所示：

T失衡了： ---> 讓失衡點右旋

案例：?

2.3.2 RR型 - 左單旋

RR 表示：新結點由于插入在 T 結點的右孩子(R)的右子樹(RR)中，從而導致失衡。如下圖所示：

?T失衡了---> 讓失衡點左旋?

案例：

2.3.3 LR型 - 左右雙旋

LR 表示：新結點由于插入在 T 結點的左孩子(L)的右子樹(LR)中，從而導致失衡。如下圖所示：

?T失衡了： -->

1） 失衡點左孩子左旋

2） 失衡點右旋?

案例：?

2.3.4 RL型 - 右左雙旋

RL 表示：新結點由于插入在 T 結點的右孩子(R)的左子樹(RL)中，從而導致失衡。如下圖所示：

?T失衡了： -->

1） 失衡點的右孩子右旋

2） 失衡點左旋?

案例：?

2.4 構造ALV樹

平衡二叉樹的構造 ， 就是不斷向數中插入新的結點：

2.5 刪除操作

與插入操作的思想類似，都是先按照二叉搜索樹的形式操作，然后想辦法使其平衡。具體步驟：

刪除結點的時候 ， 調整可能不止一次 ， 因為插入的時候，我們是從根結點開始查找合適的插入位置 ， 是符合BST的特性 ， 但是刪除操作的時候 ， 是隨機的 。

?例一：刪除 30

??例二：刪除 10?

第?次調整：從 10 向上找，第?個不平衡子樹是以 49 為根的子樹，高度最高的兒子是 59，高度最高的孫子是 69，呈現右孩子右孩子，因此僅需對 59 左旋?次。

沒有第二次調整了，因為所有都已經平衡了?

??例三：刪除 57?

?

?

?

調整結束，因為已經到了根結點，并且根節點是平衡的。?