解決查詢速度慢的方案除了哈希表外，還可以使用二叉排序樹。我們知道，查詢慢主要是因?yàn)椴恢涝氐奈恢茫褂胔ash函數(shù)映射雖然解決了問題，但其并不穩(wěn)定，當(dāng)出現(xiàn)大量的哈希碰撞后其表現(xiàn)更像一個(gè)鏈表，查詢速度大大降低。

二叉排序樹的方案則是使元素有序，這樣便可以使用二分法進(jìn)行查找了，雖然效率相比hash函數(shù)低一些，但可以通過AVL樹、紅黑樹等增加穩(wěn)定性。

HashMap在JDK1.8的實(shí)現(xiàn)中，就結(jié)合了哈希表的高效和紅黑樹的穩(wěn)定，我們之后會(huì)詳細(xì)分析其實(shí)現(xiàn)。

定義

二叉排序樹(Binary Sort Tree)，又稱為二叉查找樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

如下就是一棵簡(jiǎn)單的二叉排序樹：

二叉排序樹示意圖

當(dāng)對(duì)這棵樹進(jìn)行中序遍歷時(shí)，其結(jié)果將按照從小到大排序。

查詢操作

二叉排序樹的查找時(shí)間復(fù)雜度為O(lg n)，查找使用二分法。要在上圖中找到元素37，只需要四次操作即可。

首先，找到根元素22，37比22大，所以淘汰左子樹，再找到35，淘汰左子樹，再找到41，進(jìn)入左子樹，得到37?？梢钥吹狡渌俣缺劝€(gè)對(duì)比高了很多。

二叉排序樹的插入操作和查詢類似，也需要通過二分法進(jìn)行查找，找到合適的位置再插入元素，所以其插入速度相比鏈表較慢。

從二叉排序樹中刪除一個(gè)元素主要分為三種情況。

例如要從下面這個(gè)二叉排序樹中刪除一個(gè)元素：

二叉排序樹

刪除的元素是葉結(jié)點(diǎn)，這時(shí)可以直接刪除它。比如要?jiǎng)h除值為1的元素，刪除它對(duì)樹沒有任何影響。
刪除的元素僅有左孩子或者僅有右孩子時(shí)，直接讓其孩子頂替它即可。比如要?jiǎng)h除元素35，只需要用41頂替它即可。
刪除的元素既有左孩子又有右孩子，這時(shí)刪除它相對(duì)復(fù)雜。一種好的方式是找到它的前驅(qū)或者后繼來代替它。比如要?jiǎng)h除元素9，就用6或者13代替它即可。

一棵普通的二叉排序樹也會(huì)出現(xiàn)不平衡問題，如果插入的數(shù)據(jù)都在樹的一側(cè)，就會(huì)使得樹的深度迅速增大，每次二分查找可以排除的數(shù)據(jù)很少，從而查詢速度嚴(yán)重下降，比如下方這棵樹：

不平衡的排序樹

要查找值為2的元素，使用二分法和使用鏈表速度差不多。

為了解決這種問題，就需要在元素插入時(shí)即進(jìn)行修正，后續(xù)介紹的AVL樹和紅黑樹就是兩種不同的解決方案。

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長(zhǎng)。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。