爭(zhēng)論二叉樹(shù)的性能是沒(méi)有意義的-它們不是數(shù)據(jù)結(jié)構(gòu)，而是一系列具有不同性能特征的數(shù)據(jù)結(jié)構(gòu)。盡管不平衡的二叉樹(shù)的確比自平衡的二叉樹(shù)在搜索方面要差得多，但是有很多二叉樹(shù)（例如二叉樹(shù)嘗試）對(duì)它們而言“平衡”毫無(wú)意義。

二叉樹(shù)的應(yīng)用

二進(jìn)制搜索樹(shù) -用于許多不斷輸入/離開(kāi)數(shù)據(jù)的搜索應(yīng)用程序中，例如許多語(yǔ)言庫(kù)中的map和set對(duì)象。

二進(jìn)制空間分區(qū) -幾乎在所有3D視頻游戲中都使用，以確定需要渲染哪些對(duì)象。

二進(jìn)制嘗試 -幾乎在每個(gè)高帶寬路由器中用于存儲(chǔ)路由器表。

散列樹(shù) -用于p2p程序和專用圖像簽名中，在散列樹(shù)中需要驗(yàn)證散列，但整個(gè)文件不可用。

堆 -用于實(shí)現(xiàn)高效的優(yōu)先級(jí)隊(duì)列，這些優(yōu)先級(jí)隊(duì)列又用于調(diào)度許多操作系統(tǒng)中的進(jìn)程，路由器中的服務(wù)質(zhì)量以及A * （用于AI應(yīng)用程序（包括機(jī)器人和視頻游戲）的路徑查找算法）。也用于堆排序。

霍夫曼編碼樹(shù)（Chip Uni）-用于壓縮算法，例如.jpeg和.mp3文件格式所使用的算法。

GGM樹(shù) -在加密應(yīng)用程序中用于生成偽隨機(jī)數(shù)樹(shù)。

語(yǔ)法樹(shù) -由編譯器和（隱式）計(jì)算器構(gòu)造以解析表達(dá)式。

Treap-無(wú)線網(wǎng)絡(luò)和內(nèi)存分配中使用的隨機(jī)數(shù)據(jù)結(jié)構(gòu)。

T樹(shù) -盡管大多數(shù)數(shù)據(jù)庫(kù)使用某種形式的B樹(shù)將數(shù)據(jù)存儲(chǔ)在驅(qū)動(dòng)器上，但是將所有（大部分）數(shù)據(jù)存儲(chǔ)在內(nèi)存中的數(shù)據(jù)庫(kù)經(jīng)常使用T樹(shù)來(lái)這樣做。

二元樹(shù)比n元樹(shù)更常用于搜索的原因是n元樹(shù)更復(fù)雜，但通常沒(méi)有實(shí)際的速度優(yōu)勢(shì)。

在帶有m節(jié)點(diǎn)的（平衡）二叉樹(shù)中，從一個(gè)級(jí)別移至下一個(gè)級(jí)別需要一個(gè)比較，并且存在多個(gè)log_2(m)級(jí)別，以進(jìn)行總計(jì)log_2(m)比較。

相比之下，n元樹(shù)將需要log_2(n)比較（使用二進(jìn)制搜索）才能進(jìn)入下一個(gè)級(jí)別。由于存在log_n(m)總計(jì)級(jí)別，因此搜索將需要log_2(n)*log_n(m)= log_2(m)比較總計(jì)。因此，盡管n元樹(shù)比較復(fù)雜，但是在進(jìn)行必要的總比較方面它們沒(méi)有任何優(yōu)勢(shì)。

（但是，n元樹(shù)在小生境中仍然有用。立即想到的例子是四叉樹(shù)和其他空間劃分樹(shù)，其中每級(jí)僅使用兩個(gè)節(jié)點(diǎn)劃分空間將使邏輯不必要地復(fù)雜；以及許多數(shù)據(jù)庫(kù)中使用的B樹(shù)，其局限性不是每個(gè)級(jí)別進(jìn)行多少比較，而是一次可以從硬盤(pán)驅(qū)動(dòng)器加載多少個(gè)節(jié)點(diǎn)）

當(dāng)大多數(shù)人談?wù)摱鏄?shù)，他們不是沒(méi)有想過(guò)二進(jìn)制更多的時(shí)候是搜索樹(shù)，所以我會(huì)先覆蓋。

實(shí)際上，不平衡的二進(jìn)制搜索樹(shù)僅對(duì)教育學(xué)生有關(guān)數(shù)據(jù)結(jié)構(gòu)的作用有用。這是因?yàn)?，除非該?shù)據(jù)是在一個(gè)相對(duì)隨機(jī)的順序來(lái)了，樹(shù)可以輕松地淪為其最壞情況下的形式，這是一個(gè)鏈表，因?yàn)楹?jiǎn)單的二進(jìn)制樹(shù)不均衡。

一個(gè)很好的例子：我曾經(jīng)不得不修復(fù)一些將其數(shù)據(jù)加載到二叉樹(shù)中進(jìn)行操作和搜索的軟件。它以排序形式寫(xiě)出數(shù)據(jù)：

Alice

Bob

Chloe

David

Edwina

Frank

這樣，當(dāng)讀回它時(shí)，最終得到以下樹(shù)：

  Alice

 /     \

=       Bob

       /   \

      =     Chloe

           /     \

          =       David

                 /     \

                =       Edwina

                       /      \

                      =        Frank

                              /     \

                             =       =

這是簡(jiǎn)并形式。如果要在那棵樹(shù)中尋找Frank，則必須先搜索所有六個(gè)節(jié)點(diǎn)，然后才能找到他。

當(dāng)平衡它們時(shí)，二叉樹(shù)對(duì)于搜索真正有用。這涉及通過(guò)子樹(shù)的根節(jié)點(diǎn)旋轉(zhuǎn)子樹(shù)，以使任意兩個(gè)子樹(shù)之間的高度差小于或等于1。將這些名字一次以上添加到平衡樹(shù)中將得到以下序列：

1.   Alice

    /     \

   =       =

2.   Alice

    /     \

   =       Bob

          /   \

         =     =

3.        Bob

        _/   \_

   Alice       Chloe

  /     \     /     \

 =       =   =       =

4.        Bob

        _/   \_

   Alice       Chloe

  /     \     /     \

 =       =   =       David

                    /     \

                   =       =

5.           Bob

        ____/   \____

   Alice             David

  /     \           /     \

 =       =     Chloe       Edwina

              /     \     /      \

             =       =   =        =

6.              Chloe

            ___/     \___

         Bob             Edwina

        /   \           /      \

   Alice     =      David        Frank

  /     \          /     \      /     \

 =       =        =       =    =       =

實(shí)際上，隨著條目的添加，您實(shí)際上可以看到整個(gè)子樹(shù)向左旋轉(zhuǎn)（在第3步和第6步中），這將為您提供平衡的二叉樹(shù)，其中最壞情況的查找O(log N)而不是O(N簡(jiǎn)并形式給出的。最高的NULL（=）與最低的NULL絕沒(méi)有任何不同。并且，在上述最后的樹(shù)，你可以只看著三個(gè)節(jié)點(diǎn)找到弗蘭克（Chloe，Edwina，最后Frank）。

當(dāng)然，當(dāng)您使它們平衡多向樹(shù)而不是二叉樹(shù)時(shí)，它們會(huì)變得更加有用。這意味著每個(gè)節(jié)點(diǎn)擁有一個(gè)以上的項(xiàng)目（從技術(shù)上講，它們包含N個(gè)項(xiàng)目和N + 1個(gè)指針，二叉樹(shù)是具有1個(gè)項(xiàng)目和2個(gè)指針的1向多路樹(shù)的特例）。

使用三向樹(shù)，您最終得到：

  Alice Bob Chloe

 /     |   |     \

=      =   =      David Edwina Frank

                 /     |      |     \

                =      =      =      =

通常用于維護(hù)項(xiàng)索引的鍵。我編寫(xiě)了針對(duì)硬件進(jìn)行了優(yōu)化的數(shù)據(jù)庫(kù)軟件，其中節(jié)點(diǎn)的大小恰好等于磁盤(pán)塊的大?。ɡ?12字節(jié)），并且您將盡可能多的鍵放入單個(gè)節(jié)點(diǎn)中。該指針在這種情況下，實(shí)際上是創(chuàng)紀(jì)錄的數(shù)字成固定長(zhǎng)度的記錄直接訪問(wèn)文件的索引文件分開(kāi)（這樣的記錄號(hào)X可以通過(guò)只求被發(fā)現(xiàn)X * record_length）。

例如，如果指針為4個(gè)字節(jié)，并且密鑰大小為10，則512字節(jié)節(jié)點(diǎn)中的密鑰數(shù)為36。即36個(gè)密鑰（360字節(jié)）和37個(gè)指針（148字節(jié)），總共508字節(jié)，每個(gè)節(jié)點(diǎn)浪費(fèi)4個(gè)字節(jié)。

多向鍵的使用引入了兩階段搜索的復(fù)雜性（多路搜索以找到正確的節(jié)點(diǎn)，再加上小的順序（或線性二進(jìn)制）搜索以在節(jié)點(diǎn)中找到正確的鍵），但其優(yōu)勢(shì)在于減少磁盤(pán)I / O可以彌補(bǔ)這一點(diǎn)。

我認(rèn)為沒(méi)有理由在內(nèi)存結(jié)構(gòu)中執(zhí)行此操作，最好還是堅(jiān)持使用平衡的二叉樹(shù)并保持代碼簡(jiǎn)單。

還請(qǐng)記住，當(dāng)數(shù)據(jù)集較小時(shí)，O(log N)over 的優(yōu)點(diǎn)O(N)并沒(méi)有真正顯現(xiàn)出來(lái)。如果您使用多向樹(shù)將15個(gè)人存儲(chǔ)在通訊錄中，則可能是過(guò)大了。當(dāng)您存儲(chǔ)過(guò)去十年來(lái)來(lái)自十萬(wàn)個(gè)客戶的每個(gè)訂單之類(lèi)的東西時(shí)，優(yōu)勢(shì)就來(lái)了。

big-O表示法的全部要點(diǎn)是指出N接近無(wú)限時(shí)會(huì)發(fā)生什么。某些人可能會(huì)不同意，但是如果您確定數(shù)據(jù)集將保持在一定大小以下，并且只要沒(méi)有其他可用的可用方法，則使用冒泡排序甚至可以，:-)

至于二叉樹(shù)的其他用途，有很多，例如：

二進(jìn)制堆，其中較高的鍵高于或等于較低的鍵，而不是位于（或低于或等于并等于）左邊；

哈希樹(shù)，類(lèi)似于哈希表；

用于編譯計(jì)算機(jī)語(yǔ)言的抽象語(yǔ)法樹(shù)；

霍夫曼樹(shù)，用于壓縮數(shù)據(jù)；

網(wǎng)絡(luò)流量的路由樹(shù)。

鑒于我為搜索樹(shù)生成了多少解釋，我不愿透露其他詳細(xì)信息，但是您可以根據(jù)需要對(duì)它們進(jìn)行足夠的研究。

摩爾斯電碼的組織是一個(gè)二叉樹(shù)。