二叉查詢樹的基礎——插入和查詢
上一篇文章我們講了如何通過二分查詢進行搜尋,今天這篇文章,我們介紹二分查詢的高階版,即二叉查詢樹。二叉查詢樹主要解決的問題是查詢表,查詢表的概念和我們瞭解的字典結構非常像,簡單說就是根據一個key值,然後查詢該key值對應的value值。類似這種資料結構,在計算機的演算法中非常常見,有著非常廣泛的應用。今天我們主要介紹二叉查詢樹的三個主題:
一是如何構建一棵二叉查詢樹;
二是在二叉查詢樹中如何進行查詢;
三是檢驗二叉查詢樹的搜尋效率是不是真的高。
好,下面我們進入主題。
構建二叉查詢樹
二叉查詢樹的性質如下:首先它就是一棵普通的二叉樹,但是滿足左子樹中節點的key值都小於根節點的key值,右子樹中節點的key值都大於根節點的key值,同時當把左右子樹分別當做一棵二叉樹的時候,繼續滿足上述條件。二叉查詢樹就是有這麼一個非常好的遞迴性質,其餘的它既不是滿二叉樹,也不是完全二叉樹。
那根據上面的性質,構建二叉樹的過程是什麼樣的呢?請看下圖:
二叉查詢樹的構建過程
對於一棵二叉查詢數,當插入一個節點的時候,主要過程如下:
1)和當前節點的key值進行比較;
2)如果當前節點為NULL,則將該節點插入該位置;
3)如果和當前節點相等(如果是key-value形式,一般是更新value值),則返回;
4)如果比當前節點小,則和該節點的左孩子節點中的key值進行比較,即跳回1);
5)如果比當前節點大,則和該節點的右孩子節點中的key值進行比較,即跳回1);
這是一個非常好的遞迴性質,下面我們就以C++語言為基礎,來看看如何實現一個二叉查詢樹。
二叉查詢樹的基礎
如上面程式碼所示,我們定義了一個二叉查詢樹類。在該類中,首先定義了一個節點STRUCT。在該Node中,有相應的key和value值,同時還有左節點和右節點的指標。這基本上就包括了一棵二叉樹的基本構造。其次,在二叉查詢樹中還有一個根節點,該根節點一直指向二叉查詢樹的根。最後,還有一個計數器用於儲存該二叉查詢樹中節點的個數。
好,基本構造介紹完,下面我們就看如何插入一個節點:
二叉查詢樹的插入
插入函式是一個非常經典的遞迴實現。對於遞迴實現,實現邏輯和上面的語言描述是一致的,希望你也能寫這麼一段程式碼。其實遞迴演算法,你只要找好結束條件,那實現起來就非常簡單。
二叉查詢樹的查詢
既然叫二叉查詢樹,那最關鍵的邏輯肯定是如何進行查詢(其實不是最難的)。查詢的過程其實和插入的過程基本上是一致,但查詢只是一個遍歷的過程,能夠找到則返回key對應的value值,如果不能找到,則返回定義好的錯誤狀態(這個錯誤狀態怎麼定義很關鍵,後面我們會細說)。首先我們看一個示意圖:
二叉查詢樹的查詢過程
根據上面的示意圖,我們可以這麼定義演算法:
1)和當前節點的key值進行比較;
2)如果當前節點為NULL,則返回不存在key值的錯誤狀態;
3)如果和當前節點相等(如果是key-value形式,一般是更新value值),則返回value值;
4)如果比當前節點小,則和該節點的左孩子節點中的key值進行比較,即跳回1);
5)如果比當前節點大,則和該節點的右孩子節點中的key值進行比較,即跳回1);
那在2)中當比較的節點為NULL時,我們該怎麼返回key值不存在的錯誤狀態呢,這就要從原始碼的實現來說起了。首先,我們還是先看一下具體的原始碼實現:
二叉查詢樹的查詢原始碼
從原始碼中可以看出來,我實現了兩個函式,一個是包含函式,即contain;一個是真正的查詢函式,即search。一般情況這兩個函式是配合使用,先使用contain查詢一下key值是否存在,如果存在則再呼叫search函式返回該key值對應的value值。C++和Java的很多類庫確實是這麼實現的,但是總是有很多菜鳥程式員不按照套路出牌,沒有呼叫contain就呼叫search函式查詢key值對應的value值。這個時候search函式就有可能存在key值無法找到情況,那search函式的返回值設定就比較關鍵了(這就是我們前面說的如何定義查詢失敗時的錯誤狀態)。
我們原始碼的返回值是Value型別的指標。其實還有兩種情況也可以考慮,但都沒有返回Value型別的指標靠譜:
1)返回Node型別的指標。因為Node型別使我們在二叉查詢樹中定義的私有類,所以返回這種型別的指標,顯然破壞了類的封裝性;
2)返回Value型別。這種返回型別最大的問題就是當key值不存在時,value返回什麼值都不合理。
所以,結合目前來看,返回Value型別的指標,基本是最合適的解決方案。
二叉查詢樹的效率
說了這麼多二叉查詢樹的實現演算法,那二叉查詢樹的查詢效率究竟如何呢,下面我們就用一個實驗來驗證一下。這個實驗的目的是:統計《聖經》全文中god這個單詞出現的詞頻。具體的實驗過程是這樣的:
1)首先以單詞作為key,詞頻作為value構造一個節點資料型別;
2)統計《聖經》中的所有單詞,然後將各個單詞所在的Node插入的兩種資料結構中;
3)一種資料結構是二叉查詢樹,另一種資料結構是順序表;
4)分別在這兩個資料結構中,尋找god這個單詞的詞頻,看看哪個資料結構的效率更高。
所謂的順序表,就是將統計好詞頻的Node節點按照順序插入到該表中。也就是說順序表的查詢過程就是簡單粗暴的從頭查到尾。那這兩個資料結構的查詢效率是怎麼樣的呢,請看下圖:
二叉查詢樹的效率
從上面的結果可以看出來,《聖經》中一共有43萬多個單詞,而god這個單詞一共出現了2301次。而查詢的效率可以說是天壤之別。二叉查詢樹的查詢時間是1秒多一點,而順序表則是用了接近100秒,相差了兩個數量級。可見,如此簡單的一個演算法,不同的資料結構效率卻差如此之多。而且說實話《聖經》中單詞的資料量可不算大,如果資料量再大一些,相差的效率只會更大。
另外,對於順序表以及整個比較過程的實現原始碼,希望你能夠自己實現一下(實現過程有一定難度,但沒有你想的那麼難)。我是徐建航, 這是我寫的第71篇文章,歡迎你加入007社群,七天寫一篇,一起寫七年,七年之後一起去南極。