什么是二叉查找樹

二叉查找樹(Binary Search Tree):?

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

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

3. 左、右子樹也都是二叉查找樹。

二叉查找樹會維持節(jié)點的有序性，也稱作二叉排序樹(Binary Sort Tree)，無論進行多少次插入、刪除操作，都始終保持有序

二叉查找樹的插入和刪除

二叉查找樹的缺陷

雖然這樣一棵樹也符合二叉查找樹的特性，但是查找節(jié)點的時間復(fù)雜度退化成了O(n)

什么是平衡二叉樹

平衡二叉樹(AVL樹)，它在每次插入、刪除節(jié)點之后，可以進行“自平衡”，也就是通過一系列調(diào)整重新達到平衡狀態(tài)。

對于AVL樹的每一個節(jié)點，平衡因子是它的左子樹高度和右子樹高度的差值。

只有當(dāng)二叉樹所有節(jié)點的平衡因子都是-1, 0, 1這三個值的時候，這棵二叉樹才是一棵合格的AVL樹。

AVL樹提供了兩種特殊的操作：左旋和右旋來恢復(fù)AVL樹的平衡

什么是紅黑樹

紅黑樹復(fù)雜一些，通過紅色和黑色兩種節(jié)點，以及若干規(guī)則來判斷平衡；

紅黑樹的存在目的也是為了維護二叉查找樹的平衡

紅黑樹的規(guī)則如下：

1. 節(jié)點是紅色或黑色。

2. 根節(jié)點是黑色。

3. 每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）。

4. 每個紅色節(jié)點的子節(jié)點都是黑色（即不存在兩個連續(xù)的紅色節(jié)點）。

5. 從任意節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

紅黑樹從根到葉子的最長路徑不會超過最短路徑的2倍

紅黑樹的調(diào)整方法有兩種：

調(diào)整的方法有兩種：變色和旋轉(zhuǎn)

在需要頻繁查找時，選用AVL樹更合適，在需要頻繁插入、刪除時，選用紅黑樹

什么是B樹和B+樹

B樹和B+樹非常適合做數(shù)據(jù)庫和文件系統(tǒng)的索引；

B樹：

B樹單一節(jié)點擁有的最多子節(jié)點數(shù)量，稱為B樹的“階”；

一個m階的B樹，具有如下幾個特征：

1. 根節(jié)點至少有兩個子節(jié)點。

2. 每個中間節(jié)點都包含k-1個元素（也被稱為關(guān)鍵字）和k個孩子，其中m/2 <= k<=m。

3. 每一個葉子節(jié)點都包含k-1個元素，其中m/2 <= k<= m。

4. 所有的葉子節(jié)點都位于同一層。

5. 每個節(jié)點中的元素從小到大排列，節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素的值域分劃。

B樹雖然可以改善數(shù)據(jù)庫查詢的性能，但是卻存在一個不足之處：不方便進行范圍查詢。

一個m階的B+樹具有如下幾個特征：

1. 有k個子樹的中間節(jié)點包含k個元素（B樹中是k-1個元素），每個元素不保存數(shù)

據(jù)，所有數(shù)據(jù)都保存在葉子節(jié)點。

2. 所有的葉子節(jié)點包含了全部元素，依照元素的大小升序排列，葉子節(jié)點之間用雙向

指針相連接。

3. 所有中間節(jié)點的元素都同時存在于子節(jié)點，在子節(jié)點元素中是最大（或最小）元

素。

B+樹用于范圍查詢十分方便。

小結(jié)

二叉查找樹

可以提高節(jié)點查找的效率，并維持節(jié)點的有序性。理想狀態(tài)下，二叉查找樹查找的時間復(fù)雜度是O(logn)，但如果節(jié)點分布失衡，查找的時間復(fù)雜度有可能退化到O(n)

平衡二叉樹

也叫作AVL樹，是一種特殊的二叉查找樹，可以自動調(diào)節(jié)平衡。

AVL樹維持著嚴(yán)格的平衡，任意節(jié)點的兩棵子樹的高度差都不超過1。這樣的優(yōu)點是保證了查詢的效率，缺點是維持平衡的成本比較高，適合查詢較多的場景。

紅黑樹

是另一種可以自動調(diào)整平衡的二叉查找樹。

紅黑樹維持著相對的平衡，要求任何一條路徑的長度不超過其他路徑長度的2倍。

這樣的優(yōu)點是降低了維持平衡的成本，缺點是查詢效率略低，適合頻繁插入、刪除的場景。

B樹

解決了從磁盤海量數(shù)據(jù)中查詢的需求，有效減少了磁盤I/O的頻次。

B+樹

是B樹的升級，葉子節(jié)點包括全量數(shù)據(jù)，并使用雙向指針連接相鄰節(jié)點，為范圍查詢提供了便利。