二叉搜索樹

定義

一種在有序數組中查找某一特定元素的搜索算法，稱之為二叉查找或者二分查找法。

在樹結構中類似，從中間元素開始查找，對比大小，縮小搜索范圍。

而二叉（分）查找（搜索）樹，

每個節(jié)點的key值大于左子節(jié)點，小于右子節(jié)點，不一定是二叉樹。

借助這個性質，二叉搜索樹不僅可以用來搜索查找數據，還可以高效地插入、刪除數據。

遍歷

二叉樹的前序遍歷、中序遍歷、后序遍歷

添加

遵循插入元素大于中間元素向右支走，小于中間元素左支走，不斷迭代循環(huán)。

刪除

分為三類：

1. 沒有子類，直接刪除
2. 有一個子類，目標節(jié)點被刪除，將子節(jié)點移動到已刪除節(jié)點的位置
3. 有兩個子類，目標節(jié)點被刪除，從刪除節(jié)點的左子樹中找到最大的節(jié)點，將其移到到刪除的節(jié)點的位置

局限

二分搜索樹一旦退化成單鏈表，查找搜索效率和插入刪除效率降低。

平衡二叉樹（AVL樹）

Wiki

在計算機科學中，AVL樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中，任一節(jié)點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間復雜度都是 O(logn）。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉，以實現樹的重新平衡。AVL 樹得名于它的發(fā)明者 G. M. Adelson-Velsky 和 Evgenii Landis。

優(yōu)勢

針對于二叉搜索樹查找效率取決于樹的高度，只要保證樹的高度就可以保證搜索效率。經過研究，當節(jié)點數目一定，保持樹的左右兩端平衡，就是平衡二叉樹。

即要求，任意左右子樹的高度差只能是-1、0、1三個數值，這被稱之為平衡二叉樹。

另外，上面所謂樹的高度差和深度差都可以表述成平衡二叉樹的平衡因子。平衡因子只能取-1、0、1。

AVL樹插入后最小失衡樹與左右旋調整

最小失衡樹：在新插入的節(jié)點向上查找，以第一個平衡因子的絕對值超過 1 的節(jié)點為根的子樹稱為最小不平衡子樹。

失衡調整方法：通過旋轉最小失衡子樹來實現的

失衡調整方法.jpeg

AVL樹刪除節(jié)點

需要重新檢查平衡性并且修正，通過左右旋就能得到。

小結

平衡二叉樹的優(yōu)勢在于當二叉樹退化成單鏈表失衡，固定了樹的高度，保證了查找搜索效率。

但是為了保證平衡性，損失了在動態(tài)插入和刪除的效率

因此需要其他靈活性修改，例如紅黑樹（不是真正的平衡二叉樹，借鑒了思想，理論基礎2-3-4樹等。）