我想知道二叉樹的特殊應用是什么。你能舉一些真實的例子嗎？
3 回答
富國滬深
TA貢獻1790條經驗 獲得超9個贊
爭論二叉樹的性能是沒有意義的-它們不是數據結構，而是一系列具有不同性能特征的數據結構。盡管不平衡的二叉樹的確比自平衡的二叉樹在搜索方面要差得多，但是有很多二叉樹（例如二叉樹嘗試）對它們而言“平衡”毫無意義。
二叉樹的應用
二進制搜索樹 -用于許多不斷輸入/離開數據的搜索應用程序中，例如許多語言庫中的map和set對象。
二進制空間分區 -幾乎在所有3D視頻游戲中都使用，以確定需要渲染哪些對象。
二進制嘗試 -幾乎在每個高帶寬路由器中用于存儲路由器表。
散列樹 -用于p2p程序和專用圖像簽名中，在散列樹中需要驗證散列，但整個文件不可用。
堆 -用于實現高效的優先級隊列，這些優先級隊列又用于調度許多操作系統中的進程，路由器中的服務質量以及A * （用于AI應用程序（包括機器人和視頻游戲）的路徑查找算法）。也用于堆排序。
霍夫曼編碼樹（Chip Uni）-用于壓縮算法，例如.jpeg和.mp3文件格式所使用的算法。
GGM樹 -在加密應用程序中用于生成偽隨機數樹。
語法樹 -由編譯器和（隱式）計算器構造以解析表達式。
Treap-無線網絡和內存分配中使用的隨機數據結構。
T樹 -盡管大多數數據庫使用某種形式的B樹將數據存儲在驅動器上，但是將所有（大部分）數據存儲在內存中的數據庫經常使用T樹來這樣做。
二元樹比n元樹更常用于搜索的原因是n元樹更復雜，但通常沒有實際的速度優勢。
在帶有m節點的（平衡）二叉樹中，從一個級別移至下一個級別需要一個比較，并且存在多個log_2(m)級別，以進行總計log_2(m)比較。
相比之下，n元樹將需要log_2(n)比較（使用二進制搜索）才能進入下一個級別。由于存在log_n(m)總計級別，因此搜索將需要log_2(n)*log_n(m)= log_2(m)比較總計。因此，盡管n元樹比較復雜，但是在進行必要的總比較方面它們沒有任何優勢。
（但是，n元樹在小生境中仍然有用。立即想到的例子是四叉樹和其他空間劃分樹，其中每級僅使用兩個節點劃分空間將使邏輯不必要地復雜；以及許多數據庫中使用的B樹，其局限性不是每個級別進行多少比較，而是一次可以從硬盤驅動器加載多少個節點）
Cats萌萌
TA貢獻1805條經驗 獲得超9個贊
當大多數人談論二叉樹，他們不是沒有想過二進制更多的時候是搜索樹，所以我會先覆蓋。
實際上，不平衡的二進制搜索樹僅對教育學生有關數據結構的作用有用。這是因為，除非該數據是在一個相對隨機的順序來了，樹可以輕松地淪為其最壞情況下的形式，這是一個鏈表，因為簡單的二進制樹不均衡。
一個很好的例子：我曾經不得不修復一些將其數據加載到二叉樹中進行操作和搜索的軟件。它以排序形式寫出數據：
Alice
Bob
Chloe
David
Edwina
Frank
這樣，當讀回它時，最終得到以下樹：
Alice
/ \
= Bob
/ \
= Chloe
/ \
= David
/ \
= Edwina
/ \
= Frank
/ \
= =
這是簡并形式。如果要在那棵樹中尋找Frank，則必須先搜索所有六個節點，然后才能找到他。
當平衡它們時，二叉樹對于搜索真正有用。這涉及通過子樹的根節點旋轉子樹，以使任意兩個子樹之間的高度差小于或等于1。將這些名字一次以上添加到平衡樹中將得到以下序列：
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
/ \ / \ / \
= = = = = =
實際上，隨著條目的添加，您實際上可以看到整個子樹向左旋轉（在第3步和第6步中），這將為您提供平衡的二叉樹，其中最壞情況的查找O(log N)而不是O(N簡并形式給出的。最高的NULL（=）與最低的NULL絕沒有任何不同。并且，在上述最后的樹，你可以只看著三個節點找到弗蘭克（Chloe，Edwina，最后Frank）。
當然，當您使它們平衡多向樹而不是二叉樹時，它們會變得更加有用。這意味著每個節點擁有一個以上的項目（從技術上講，它們包含N個項目和N + 1個指針，二叉樹是具有1個項目和2個指針的1向多路樹的特例）。
使用三向樹，您最終得到：
Alice Bob Chloe
/ | | \
= = = David Edwina Frank
/ | | \
= = = =
通常用于維護項索引的鍵。我編寫了針對硬件進行了優化的數據庫軟件，其中節點的大小恰好等于磁盤塊的大?。ɡ?12字節），并且您將盡可能多的鍵放入單個節點中。該指針在這種情況下，實際上是創紀錄的數字成固定長度的記錄直接訪問文件的索引文件分開（這樣的記錄號X可以通過只求被發現X * record_length）。
例如，如果指針為4個字節，并且密鑰大小為10，則512字節節點中的密鑰數為36。即36個密鑰（360字節）和37個指針（148字節），總共508字節，每個節點浪費4個字節。
多向鍵的使用引入了兩階段搜索的復雜性（多路搜索以找到正確的節點，再加上小的順序（或線性二進制）搜索以在節點中找到正確的鍵），但其優勢在于減少磁盤I / O可以彌補這一點。
我認為沒有理由在內存結構中執行此操作，最好還是堅持使用平衡的二叉樹并保持代碼簡單。
還請記住，當數據集較小時，O(log N)over 的優點O(N)并沒有真正顯現出來。如果您使用多向樹將15個人存儲在通訊錄中，則可能是過大了。當您存儲過去十年來來自十萬個客戶的每個訂單之類的東西時，優勢就來了。
big-O表示法的全部要點是指出N接近無限時會發生什么。某些人可能會不同意，但是如果您確定數據集將保持在一定大小以下，并且只要沒有其他可用的可用方法，則使用冒泡排序甚至可以，:-)
至于二叉樹的其他用途，有很多，例如：
二進制堆，其中較高的鍵高于或等于較低的鍵，而不是位于（或低于或等于并等于）左邊；
哈希樹，類似于哈希表；
用于編譯計算機語言的抽象語法樹；
霍夫曼樹，用于壓縮數據；
網絡流量的路由樹。
鑒于我為搜索樹生成了多少解釋，我不愿透露其他詳細信息，但是您可以根據需要對它們進行足夠的研究。
添加回答
舉報
0/150
提交
取消