心中有“樹”！圖文并茂介紹數(shù)據(jù)結(jié)構(gòu)中常見的樹（三）

在前面兩篇文章中，我們簡要介紹了數(shù)據(jù)結(jié)構(gòu)中的各種【樹】在搜索、數(shù)據(jù)庫等領(lǐng)域的使用場景，希望對大家有所幫助。

本篇內(nèi)容，是我們?《心中有“樹”》?系列的最后一篇，我會在這里繼續(xù)給大家介紹一些樹的結(jié)構(gòu)和應(yīng)用場景，也會跟大家分享一下我個人對這些“雜七雜八”的知識的想法和態(tài)度。

大家好，我是不會寫代碼的純序員——Chunel Feng，很高興又在這里跟各位紳士見面了。上一章內(nèi)容中，我們跟大家介紹了【樹】結(jié)構(gòu)在編碼、緩存、數(shù)據(jù)庫等方面的應(yīng)用例子，包括了哈夫曼樹、最小生成樹、線段樹、伸展樹、B/B+樹、LSM 樹。這一章，我們再繼續(xù)這個話題，聊一聊“樹”在相似搜索、人工智能等領(lǐng)域的一些常見應(yīng)用。

相似搜索領(lǐng)域

相似搜索（ANN，Approximate Nearest Neighbor）技術(shù)又叫做“向量檢索技術(shù)”或“相似最近鄰搜索技術(shù)”，指的是單個向量在海量向量中，通過預(yù)先設(shè)定的索引結(jié)構(gòu)，快速查詢出距離（如：歐氏距離、曼哈頓距離等）相近的 TopK 個向量的方法。該技術(shù)被廣泛應(yīng)用于以圖搜圖，智能問答，搜索推薦系統(tǒng)等領(lǐng)域。

常見的使用場景嘛，比如將海量圖片通過 embedding 技術(shù)，生成對應(yīng)的海量向量集合（Dataset）。然后將查詢圖片通過同樣的方法，得到一個向量（query point），并在 Dataset 中找到距離最近的 n 個向量，就可以粗略認定：這 n 個向量對應(yīng)的圖片，和查詢圖片比較相似。

K 維樹（K-Dimension Tree）

我們之前聊過很多樹，有的節(jié)點中包含一個信息（如：紅黑樹），有的節(jié)點中包含多個信息（如：B 樹）。還有一種情況，樹中的每個節(jié)點中，包含一組信息——一個高維向量。這個概念就迎合了上面提到的向量檢索了。

KD 樹是早期做向量檢索的方案，建樹的時候通過空間內(nèi)點的方差來確定切分方向、進而再確定出切分點和切分平面，并以此方式遞歸的對海量向量數(shù)據(jù)進行切分，直至形成一顆樹形結(jié)構(gòu)。

看上面這張圖，[2,3] [5,4] [4,7] [7,2] [8,1] [9,6]這幾個二維向量，就被以切面（左圖中紅色和藍色的線）分割的形式，放在了右圖的 KD 樹中。查詢的時候，根據(jù) KD 樹的路徑中的切點和切面信息，通過對比尋址和回溯等流程，最終在海量向量數(shù)據(jù)中，在減少比對次數(shù)的基礎(chǔ)上，找到與 query point 鄰近的 TopK 個點，從而達到較少查詢耗時的目的。

Annoy 樹

Annoy（Approximate Nearest Neighbors Oh Yeah）算法是 Spotify 公司開源出來的算法名稱，目的和 KD Tree 一樣，也是為了解決海量高維向量的相似搜索的問題。其中也用到的樹的思路，而且是多棵樹組成的森林。

跟 KD 樹不同的是，它切分的方式是通過對海量向量集合做隨機點開始的二值聚類，然后將聚類的索引信息放到根節(jié)點的左右兩側(cè)（作為“簇”），然后以此方式繼續(xù)遞歸，直到每個簇中的節(jié)點數(shù)量小于特定值為止。這樣下來，除了葉子結(jié)點以外，所有的路徑結(jié)點中實際上存儲的只是切面的信息，而所有的向量信息均存放在葉子結(jié)點中。

這種騷操作是不是有點熟悉，KD 樹和 Annoy 樹的關(guān)系，是不是有點像 B 樹和 B+樹的關(guān)系。需要說明的是，Annoy 算法選擇起點的時候有一定的隨機性，相同的向量集用同樣的方法反復(fù)多次是會產(chǎn)生不同的 Annoy 樹的。這些樹又共同組成了一個描述這批海量向量數(shù)據(jù)集合的森林。這樣做，是為了可以通過多次查詢并合并/去重查詢結(jié)果的方式，提高最終結(jié)果的準確率。

類似的技術(shù)，還有隨機投影樹（Random Projection Tree），不過在做平面切分的時候，跟 Annoy 有所區(qū)別。有興趣的朋友可以深入了解一下，這也是一種通過樹（森林）的方式，解決 Ann 問題的思路。

注：目前在相似搜索領(lǐng)域，基于圖的算法無論在召回率還是查詢耗時層面，都有一定的優(yōu)勢，因此也相對更為主流。但是森林結(jié)構(gòu)有天然的并行屬性（因為有多棵不同的樹嘛），這是單純的圖結(jié)構(gòu)所不具備的。因而個人認為這個細分領(lǐng)域，今后可能往【圖+樹】的方向發(fā)展。

人工智能領(lǐng)域

決策樹 (Decision Tree)

決策樹是一種基于樹型結(jié)構(gòu)的、可解釋的、有監(jiān)督的機器學習的方法，而非單純的指一種結(jié)構(gòu)。決策樹中的每個非葉子節(jié)點均表示一個屬性上的判斷，而每個葉子結(jié)點表示一種分類結(jié)果。整體上描述的是算法為了達到特定目標，根據(jù)一定的條件而進行選擇的過程，被用于機器學習中的分類任務(wù)。

看上面這張圖，描述的就是：根據(jù)【是否擁有房產(chǎn)】【是否已婚】【年收入是否超過 80（元，嘿嘿，我過了）】這三個（在非葉子節(jié)點中）條件來判斷借貸人是否有償還能力（結(jié)果在葉子節(jié)點中）的一顆決策樹。比如，一個沒有房產(chǎn)、未婚、年薪低于 80 的人，會如圖中藍色箭頭所示，被判定為無償還能力。

至于這幾個條件中，哪個條件應(yīng)該被先判斷（在樹相對頂部的位置），大家可以自行了解一下 ID3、C4.5、熵減、信息增益啥的。決策樹有著天然的可解釋性，在推薦系統(tǒng)中有著廣泛應(yīng)用，有興趣的朋友還可以了解一下 GBDT（Gradient Boosting Decision Tree，漸進殘差決策樹），這也屬于森林的概念了。

蒙特卡洛樹（Monte Carlo Tree）

蒙特卡洛是摩納哥一個著名賭城的名字，蒙特卡洛樹和游戲、賭（和諧）博等領(lǐng)域能扯上一些關(guān)系，常被用于博弈游戲中推測勝出的概率。前陣子大火的 AlphaGo，其中就用到的了蒙特卡洛樹。

它主要描述的是，通過在設(shè)定范圍（比如：游戲規(guī)則、單步計算耗時等）內(nèi)，大量反復(fù)執(zhí)行?選擇（Selection）、擴展 (expansion)、模擬（Simulation）、回溯（Backpropagation)?這四個流程，逐步的構(gòu)造出包含了各種可能執(zhí)行路徑，及其對應(yīng)節(jié)點勝出概率的樹型結(jié)構(gòu)。

蒙特卡洛樹的路徑中的每個節(jié)點，都表示從當前狀態(tài)繼續(xù)進行，可能勝出的概率。而任意節(jié)點的子節(jié)點，就表示從當前狀態(tài)出發(fā)，至少有幾種可選的方案（拿象棋來說吧，就表示，此時可以“把炮向前走三步”、或者“把卒向前走一步”等）。對應(yīng)到上面的圖，可以理解為，經(jīng)過一系列騷操作后，根節(jié)點出發(fā)（針對象棋，就理解是當頭炮吧），勝出的概率由 12/21 變化為 12/22，從而變的更接近實際情況了。

我們剛才聊到了曼哈頓距離、蒙特卡洛樹，這些都是以外國城市命名的知識點。于是，我就去搜索了一下有沒有什么內(nèi)容是以中國的城市命名的。最后，我學到了一些地產(chǎn)和航空航天方面的知識，比如：蚌埠住了，蕪湖起飛。

再簡單介紹幾種其他領(lǐng)域中常用到的樹吧。

默克爾樹（Merkle Tree）

默克爾樹又叫做 哈希樹（Hash Tree），它是將整體內(nèi)容分成多個區(qū)塊，然后逐層合并計算哈希值，并且放入樹的父節(jié)點上的結(jié)構(gòu)。相比于將對分塊的哈希值，統(tǒng)一記錄到一個 Hash Table 的做法，默克爾樹的主要優(yōu)勢，是它可以分部分進行校驗，常用與區(qū)塊鏈，密碼學等領(lǐng)域。

看上面這張圖吧，我們可以認為 L1(假想為是一個大文件的一個分塊)對應(yīng)的哈希值[Hash 0-0]，L2 對應(yīng)的哈希值是[Hash 0-1]，而[Hash 0]是對上述兩個哈希值（不是分塊）再進行哈希后得到的值。這樣，在下載文件的時候，如果我想確認前半部分有沒有下載完畢，我直接判斷已下載部分的[Hash 0]值，跟預(yù)期是否一致即可。

當然了，真實的使用場景可能比這復(fù)雜了很多。以上說法也是站在一個區(qū)塊鏈技術(shù)門外漢的角度的進行描述。如果我真的很懂的話，也許我買的幣也不會虧那么多了，嗚嗚。

矩形樹（Rectangle Tree）

R 樹也被叫做空間索引樹，可以簡單理解為是 B/B+樹的高階版本。它的核心思想是通過最小外接矩形的形式，逐層聚合（空間）距離相近的節(jié)點。主要應(yīng)用于地理位置查詢等領(lǐng)域，比如在地圖上找餐廳這類問題，也被用于數(shù)據(jù)庫領(lǐng)域。

上圖是一個二維的 R 樹。圖中有 10 個小分塊（可以理解成是餐廳、酒店、娛樂場所等），分別是 A~J。它們在 R 樹上根據(jù)所在位置，被用綠色的矩形分成了 4 個部分——分別為 P1/P2/P3/P4。如果需要查詢紅色實心方框附近的娛樂場所，通過在 R 樹上的映射可知，僅搜索 P3 和 P4 對應(yīng)的分塊即可，從而減少了查詢范圍。

相關(guān)的內(nèi)容還有 R*樹、R+樹、Hilbert R 樹等。有興趣的朋友可以繼續(xù)深入研究。

本章小節(jié)

這篇文章是樹系列的最后一篇，很高興能在您的陪伴下，一直走到這里。在這幾篇文章中，我把我所了解的 Tree 相關(guān)的內(nèi)容都羅列了一遍，也介紹了這些結(jié)構(gòu)的使用場景和解決的問題。其實，我個人在日常工作中，用到的這方面的知識也不多，像“默克爾樹”這種，我也都是最近剛了解的——但，這在某些特定細分領(lǐng)域中，是最最基本的知識。

這個系列的內(nèi)容，每一個小節(jié)都比較短，也比較淺，希望大家都能看懂并有所收獲。今后，如果在特定行業(yè)用到了其中某些部分，還需要大家深入了解該結(jié)構(gòu)和其周邊的相關(guān)知識。畢竟對細分領(lǐng)域知識點了解的深度，才是區(qū)別【新手】和【專家】的評判標準。如果，各位專家發(fā)現(xiàn)我的表述中，有什么錯誤、或者不合理、不清楚的地方，也希望不吝賜教。

又想到幾年前，我為了找工作，猛刷過一陣子 Leetcode。其中很喜歡寫的就是樹相關(guān)的題目——因為簡單啊，代碼量一般不多，有思路的時候?qū)懫饋砗茼樖值摹＿@幾年，因為工作原因吧，很久不練，偶爾想寫兩題的時候，都發(fā)現(xiàn)已經(jīng)很生疏了。

但也是隨著工作經(jīng)驗的增長，相比于之前單純的為了快速寫出某個題目的雙優(yōu)解法，我會更愿意去關(guān)注和思考一些題目對應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法知識點的背后所隱射的內(nèi)容，比如：

?它常被用于什么場景？?它能解決我當前的什么痛點？?它能給我接下來的工作，帶來怎樣的變化？?它還和哪些知識點有關(guān)，互相對比有何優(yōu)劣。能否結(jié)合使用，或取長補短？?結(jié)合手頭的任務(wù)，我還可以如何去定向的改造和優(yōu)化它？

誠然，數(shù)據(jù)結(jié)構(gòu)和算法的思路，對任何一個程序員來說，都至關(guān)重要。但大家也不用僅僅為了應(yīng)付一些公司面試，成為“小鎮(zhèn)做題家”吧。必須承認，當前行業(yè)環(huán)境下，很多人的日常工作中，是基本是用不到這些知識的。如果真的用到了，那落地的過程一定比題目中描述的情況，復(fù)雜百倍。雙優(yōu)的題解和答案，總是可以很簡單的在網(wǎng)上找到，但“學有所思”、“學以致用”的能力，更應(yīng)該是我們在工作和成長的過程中，一點點積攢和沉淀的財富。

我是 Chunel Feng——是一個不會寫代碼的純序員。感謝您的關(guān)注，歡迎添加我的個人微信，隨時指教和交流。

GitHub：https://github.com/ChunelFeng

個人博客：http://www.chunel.cn

最后也歡迎大家關(guān)注 Doocs 公眾號，加入 Doocs 開源社區(qū)，這是一個優(yōu)質(zhì)的以交流分享算法和后端知識為主的技術(shù)型開源社區(qū)。在其中，你可以結(jié)識很多大佬，學到很多新知識，增長見識；也可以做出自己的貢獻，去幫助需要的朋友。希望我們能一起，用自己的所見、所學和所感，讓世界變得更美好——哪怕只有一點點點點點點！

推薦閱讀

?心中有“樹”！圖文并茂介紹數(shù)據(jù)結(jié)構(gòu)中常見的樹（一）?心中有“樹”！圖文并茂介紹數(shù)據(jù)結(jié)構(gòu)中常見的樹（二）?手擼一款簡單高效的線程池（一）?手擼一款簡單高效的線程池（二）?手擼一款簡單高效的線程池（三）—— 性能優(yōu)化！?手擼一款簡單高效的線程池（四）?手擼一款簡單高效的線程池（五）

長按識別下圖二維碼，關(guān)注公眾號「Doocs 開源社區(qū)」，第一時間跟你們分享好玩、實用的技術(shù)文章與業(yè)內(nèi)最新資訊。