二元樹排序對搜尋的影響

Posted By Mr. Thursday

在〈二元樹在排序的應用〉裡面,我們提到了演算法就是完成一件事情的步驟,資料結構則是和演算法搭配,讓步驟有運作的東西,像是刮鬍刀的步驟,會運作在刮鬍刀或是插頭上面。「樹」(tree) 是一種資料結構,有樹根樹枝,看起來像是倒立的一棵樹。二元數則是每個節點只有兩個分支的樹。此外,我們可以用二元樹這個資料結構,完成「排序」(sorting) 的演算法。下面是一段各種排序演算法的影片:

 

除了排序以外,今天要和各位介紹,當我們把資料用一棵樹排序之後,要如何進行搜尋?排序或是沒有排序,對搜尋的效率有甚麼樣子的影響?我們先看看下面這兩張圖,左邊是排序過程,右邊是搜尋過程的動畫:

search

我們可以看到,不管是搜尋過程,還是排序過程,在二元樹上面的步驟都差不多:先比較現在的節點,如果比較小,就往左邊走,比較大,就往右邊走,一直到達樹的底部為止。

search

因此,現在的差別就在於,有排序過的樹,跟一棵沒有排序過的樹,搜尋的效率有哪些差別?一棵沒有排序過的樹,如果我們要在裡面找是否有某個數字,最差的情況下我們必須把整棵樹都走完,才會找到我們要的數字,或是回報沒有這個數字。然而如果我們用了二元樹在輸入每一個新的數字的時候,就按照剛才的演算法排序過,那麼這棵二元樹永遠都會維持的一個關係,就是對每一個節點來說,左邊的節點一定比他小,右邊的節點一定比他大。也因此我們如果要在這一棵樹裡面,尋找是否有某個數字的時候,我們比較目前的節點和我們要找的數字,如果比較小就往左邊,比較大就往右邊走。這樣子保證我們不會漏找,卻同時減少我們需要拜訪的節點

如果我們再認真去分析的話,我們可以發現,我們最差的情況,最多找和樹高 (tree height)一樣多節點就可以了,也就是說如果這棵樹的高 (像是上面那一張動畫裡面的樹) 如果只有三個節點的高度,那麼我們最多只要尋找三次就能找到。然而同樣的一棵樹,沒有經過排序,我們最多需要尋找七個節點。如果再用數學表示的話,一個有n個節點的二元樹,樹高就是 $\latex{log_2(n)}$ 了!

排序、搜尋、與記憶

因此我們可以發現,排序演算法的用處在哪邊了!一堆病歷,或是一堆電話號碼,如果沒有排序過,我們要從裡面找出所要的病歷,所要的電話號碼,最多要把全部的病歷都找一遍。如果我們用二元樹和搭配的演算法,把病歷和電話號碼先排序過,那麼我們尋找病歷或電話號碼的時候,可以節省指數倍的時間!原來最多找7次,排序過後只要找3次!

搜尋某方面,也就像是人類的記憶。行為認知上來說,記憶有兩種情況:(1) 看到同一個東西的時候,能夠回想起我看過。(2) 看到某見東西的重要部份 (key),可以回想起整件事情。上面提到的二元樹搜尋演算法,可以算是第一種情況,如果數字是代表病歷號碼,找到某個節點後,會有一個連結到病歷內容,那麼上面的二元樹搜尋演算法,就是第二種情況,也就是以 key 找資料的情況。

在這邊還要再提的部分,是以 key 找資料的情況。有時候我們稱這個 key 在電腦裡面是一個地址 (adress) ,因此這種尋找方式,可以稱為 adress-based memory,根據東西的地址來找資料,譬如說病歷號碼,可以當成是病歷的地址 (address),我們搜尋病歷,就先搜尋病歷號碼,然後提取該號碼代表的病歷內容。搜尋引擎來說,就是把關鍵字keyword當成地址,每個地址連結到某個網頁。

另外一種搜尋方式,就是用內容為 key的情況,這時候我們稱之為 content-based memory。這種記憶就類似「以文找文」的方式,或是「以圖找圖」的方式,沒有索引,直接用內容來提取我們想要找的內容。人類的記憶我想滿多部分都是 content-based memory,也就是我們大腦神經網絡,會把資料用一種特別方式儲存起來,當我們在頭腦裡面尋找資料的時候,我們是用內容來尋找比較多,比較少像是書本索引一般,用關鍵字當地址來找我們想要找的東西。類神經網路 (artificial neural network) 大部分也都是用 content-based memory比較多。

然而比較困難的地方,我想是在於部分內容當作key的情況,也就是我們以文找文,但是只有一部分的文章內容,要找出原來完整的文章,卻又沒有索引地址。譬如說我們記得某張照片裡面有一座山、一條河流、和一棟房屋,但是我們也沒有在資料庫裡面對每張照片開一個欄位,紀錄每張照片是否有出現山、河流、或房屋,這個時候就是 content-based memory的情況,而且提取的key只有原來內容的一部分,想要找尋完整的一張照片。使用機率為基礎的演算法,或是從生物角度研究大腦記憶的方法,都是想要解決這個問題。

再困難一點,我們可能還有前後文、或稱為情境的問題 (context) 。找圖片的時候,我們可能說照片裡面有一座山,但是文字一般性的敘述,有時候又會讓每個人心中想像的山有所出入,你想的可能是長滿樹木的山,我想的可能是積雪覆蓋的山。又另外一種情況是,我們可能用一張蘋果的照片,來找相似的圖片,但是我們是在「水果」的前後文情境裡面,就不能去找 Apple 產品的圖片了。因此這些問題的難度又加一層了。下回在介紹用樹來表示一個本體論 (Ontology) 的時候,再和各位詳細探討一下相關問題!

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!