查找算法概要

順序查找

遍歷數組中的所有數，尋找等於某個值的數
這是一種十分暴力的算法，沒什麼好說的。
時間複雜度 O(n) ，空間複雜度爲 O(1) 。
該查找算法對元素的排列沒有任何要求，不管是不是有序的。
插入、刪除元素的時間複雜度取決於數組的數據結構（順序表還是鏈表）。

二分查找

在有序的序列中，每次和序列的中間元素比較，來確定元素的位置。每次比較，如果中間元素不等於被比較元素，就縮小元素所在的範圍
二分查找首先要求元素序列是有序的。因此如果元素序列亂序，首先要經過排序，這就要消耗至少 O(nlogn) 的時間。
進行每次二分查找，要麼可以返回元素位置，要麼就把元素的所在範圍縮小一半。因此最快的話一次就可以找到元素，最慢需要 log2n 次比較，時間複雜度爲 O(logn) 。
因爲鏈表不能隨機訪問（給出任意的元素索引，不能在 O(1) 時間內訪問該元素），所以二分查找不適用於鏈表而適用於順序表，但是順序表刪除、插入元素會影響到後面的元素（時間複雜度爲 O(n) ）,所以對於不經常插入、刪除的場景下，使用順序表和二分查找是一個不錯的選擇。

二叉查找樹（BST）

一個二叉樹，它中序遍歷輸出的是一個有序的序列
爲了克服二叉查找使用的順序表插入、刪除操作時間複雜度較大的缺點，可使用二叉查找樹。
二叉查找樹是一個有序的二叉樹，把它進行終須遍歷輸出的是有序的序列。因此，對於二叉查找樹的每個節點，左孩子（Left-Children）的值 < 父節點(Parent)的值 < 右孩子的值（Right-Children）或者 左孩子的值 > 父節點的值 > 右孩子的值（先暫時假設數組中所有的元素不相等）。
- 在插入的過程中只要保證小於父節點的元素在左邊，大於父節點的在右邊（大的在左邊小的在右邊也行，保持整個樹有序即可）就行。
- 查找的時候，把要查找的值和父節點比較：等於就返回父節點，小於就在左邊的子樹裏面查找，大於就在右邊的子樹查找。
- 刪除元素：在刪除的同時還要保持二叉樹的有序性。所以可以分一下幾種情況
1. 被刪除的元素是葉子節點：直接刪掉就行了
2. 被刪除的元素是父節點，只有一個孩子：直接用他的孩子節點覆蓋掉這個父節點
3. 被刪除的元素是父節點，有兩個孩子：把該父節點的直接前驅元素（或者直接後繼元素）替換掉這個父節點，同時把前驅元素（或者後繼元素）的子樹（該前驅、後繼元素頂多只有一個子樹，自己想一想爲什麼哈）的根節點放在該前驅元素（或者後繼元素）的位置。這個有點複雜，配合圖來看比較好理解，圖以後再補。

時間複雜度和樹的高度h有關。如果該樹比較飽滿，比較接近於完全二叉樹 ，那麼樹的高度h約爲 log2n ；極端情況下，如果這個樹每個節點只有一個分支，那麼樹的高度h就是元素個數n。
因此，對於高度爲h的二叉查找樹，其查找、插入的時間複雜度都爲 O(h) ，即最好爲 O(log2n) ，最壞爲 O(n) 。刪除元素的時間主要消耗在尋找直接前驅元素（或者直接後繼）上了，移動二叉樹的時間都是常數級的，因此時間複雜度爲 O(h) ，即最好爲 O(log2n) ，最壞爲 O(n) 。
可以看到，二叉查找樹的性能取決於他的樹高h。因此，接下來我們介紹一種新的數據結構，平衡二叉樹，它在減小樹高的方面做了優化。

平衡二叉樹（AVL）

平衡二叉樹是以BST爲基礎，對樹的高度進行了控制。
首先引入一個概念 平衡因子 ：某個節點的左子樹減去右子樹的深度的差。相對於BST，AVL在每個節點增加一個平衡因子的字段，它所有的節點的平衡因子爲0或1或-1（對於平衡二叉樹而言）。
這是一個AVL：

這是一個不平衡的二叉樹：

A的平衡因子爲2（左子樹深度3 - 右子樹深度1 = 2），因此這個樹不平衡。

在講怎麼調整不平衡的二叉樹之前，先引入一個概念最小不平衡子樹 ：某個節點是不平衡的，但是他的左右孩子節點卻是平衡的。則以這個節點爲根的子樹爲最小不平衡子樹。

可以看出，以46爲根節點的子樹就是最小不平衡子樹。

接下來說說怎麼調整AVL：

• 插入節點：假設在插入節點之前樹爲AVL，插入之後破壞了平衡性。對於不同類型的樹，有不同的調整方案。

  1. LL型或RR型：如下圖，中間的樹就是LL型的（RR型樹正好和LL型樹左右對稱）。
     
     首先把B節點轉上去，A節點轉到B的右孩子的位置，然後把D節點放在A節點的左孩子的位置。這樣調整使得插入節點前後，A（插入之後爲B）這個子樹的高度沒有發生變化，因此上層的節點不用調整平衡因子了。RR型的調整方法與LL的類似。

  2. LR型或RL型：如下圖，左邊的樹是LR型的。
     
     首先對於6這個子樹，把6轉下去，7轉上來，變成中間的樹的樣子。這個時候樹就變成了LL型的，利用之前的調整方法就可以了。同樣的，插入前後這個子樹的高度不變化（進行了樹的平衡的話），不用更新上層節點的平衡因子，只需要更新子樹內部的平衡因子。

由上面的方法我們可以看到，插入一個節點，只需要進行常數次的調整，因此對於AVL，插入節點的時間複雜度爲 O(1) 。
如何判斷LR、RL、RR、LL型的一個方法（只適用於插入節點）：從最小不平衡子樹的根節點開始，往插入節點的位置走。如果先走左子樹後走右子樹，那麼就是LR型的。其他類型同理。

• 刪除節點：要調整最小不平衡子樹，同樣的是首先判斷出樹的類型，然後將節點轉來轉去。
  和插入節點不同的是：插入節點如果進行了平衡調整，那麼插入入前後最小不平衡子樹的高度不發生變化。刪除節點之後如果進行了平衡調整，那麼刪除前後最小不平衡子樹的高度可能會發生變化，因此上層祖先節點可能會失衡，需逐層遍歷各祖先，並對不平衡的祖先節點進行調整（利用轉來轉去的方法進行調整）。
  因此，刪除節點的時間複雜度爲 O(logn) 。

• 統一重平衡算法： AVL（也可以說BST）的一個最基本的性質就是 它中序遍歷出來的序列是有序的，因此可以根據最小不平衡子樹的中序遍歷結果，刪除或者插入相關元素，然後根據修改之後的中序遍歷結果來直接生成平衡之後的子樹。可以參考《數據結構》鄧俊輝著，第三版，P200。