植樹節,程序猿種的那些樹

大數據2019-03-19 18:10:49


導讀:3 月 12 日是一年一度的植樹節。旨在宣傳保護森林,並動員羣眾參加植樹造林活動。説到樹,程序猿們肯定不陌生,趁着這個植樹節到來之時普及一下程序猿們經常遇見的樹。


來源:五分鐘學算法(ID:CXYxiaowu)

本文由程序猿小吳和小夥伴 進擊的Hello_World 共同整理完成。




01 二叉搜索樹


1. 定義


二叉搜索樹又稱二叉查找樹,亦稱為二叉排序樹。設 x 為二叉查找樹中的一個節點,x 節點包含關鍵字 key,節點x 的 key 值記為 key[x] 。如果 y 是 x 的左子樹中的一個節點,則 key[y] <= key[x] ;如果 y 是 x 的右子樹的一個節點,則 key[y] >= key[x] 。


2. 查找性能


當數據數目為 N,樹高度保持 logN 附近。則平均查找長度與 logN 成正比,查找平均時間複雜度為 O(logN) 。 當先後插入的關鍵字有序時,二叉搜索樹退化成單支樹結構。此時樹高 N 。平均查找長度為 (N+1)/2 ,查找的平均時間複雜度為 O(N) 。


3. 插入性能


插入效率與查找效率一致。
  

4. 刪除性能


刪除節點時,若節點為葉子節點,或者節點只有單一子樹,則時間複雜度為 O(1) 。若節點既有左子樹又有右子樹,則需要執行遞歸過程,對應時間複雜度為 O(logN) 。


5. 應用場景


二叉排序樹就既有鏈表的好處,也有數組的好處,因此在處理大批量的動態的數據是比較有用。


6. 種樹




02 平衡二叉樹


1. 定義


平衡二叉樹是一種特殊的二叉搜索樹。平衡二叉樹保證節點平衡因子的絕對值不超過1,保證了樹的平衡。


2. 查找性能


平衡二叉樹是嚴格平衡的,那麼查找過程與二叉搜索樹一樣,只是平衡二叉樹不會出現最差的單支樹情形。因此查找效率最好,最壞情況時間複雜度為 O(logN) 。


3. 插入性能


插入數據之前需要進行查找操作,查找到插入位置。插入數據後需要進行旋轉操作,旋轉操作複雜度為常量級。因此插入數據的時間複雜度與查找相同為 O(logN)。


4. 刪除性能


刪除數據同樣需要查找數據,在刪除數據後需要進行調整。一次刪除最多需要需要O(logN)次旋轉,因此刪除數據的時間複雜度為O(logN)+O(logN)=O(2logN)。


5. 應用場景


SGI/STL的 set/map 底層都是用紅黑樹(平衡二叉樹的一種)實現的。


6. 種樹




03 紅黑樹


1. 定義


平衡二叉樹的嚴格平衡策略以犧牲建立查找結構(插入,刪除操作)的代價,換來了穩定的O(logN) 的查找時間複雜度。紅黑樹採用了折中策略,即不犧牲太大的建立查找結構的代價,同時又能保證穩定高效的查找效率。


2. 查找性能


由於紅黑樹的性質(最長路徑長度不超過最短路徑長度的 2 倍),可以説明紅黑樹雖然不像平衡二叉樹一樣是嚴格平衡的,但平衡性能還是要比二叉搜索樹要好。其查找代價基本維持在 O(logN) 左右,但在最差情況下(最長路徑是最短路徑的 2 倍少 1),比平衡二叉樹效率低一些。


3. 插入性能


紅黑樹插入結點時,需要旋轉操作和變色操作。但由於只需要保證紅黑樹基本平衡就可以了。因此插入結點最多隻需要2次旋轉,這一點和平衡二叉樹的插入操作一樣,但是變色操作的時間複雜度為O(logN)。


4. 刪除性能


紅黑樹的刪除操作代價要比平衡二叉樹要好的多,刪除一個結點最多隻需要 3 次旋轉操作,保證了刪除時間複雜度維持在常量級。


5. 應用場景


應用場景有很多。


  • Java 中的 TreeSet ,TreeMap,HashMap

  • C++ 的 STL中的 map 和 set 都是用紅黑樹實現的

  • epoll 在內核中的實現,用紅黑樹管理事件塊

  • nginx 中,用紅黑樹管理 timer 等

  • linux 進程調度 Completely Fair Schedule r,用紅黑樹管理進程控制塊


5. 種樹




04 B 樹


1. 定義


B樹是一種多路平衡查找樹,在相同數據數目情形下,B樹的高度更小,這樣就減少了磁盤的IO次數,在文件系統以及數據庫索引等場景下提升了查找效率。


2. 查找性能


B樹的查找分成兩種:一種是從一個結點查找另一結點的地址的時候,需要定位磁盤地址(查找地址),查找代價極高。另一種是將結點中的有序關鍵字序列放入內存,進行優化查找(可以用折半),相比查找代價極低。而B樹的高度很小,因此在這一背景下,B樹比任何二叉結構查找樹的效率都要高很多。


3. 插入性能


B樹的插入會發生結點的分裂操作。當插入操作引起了 s 個節點的分裂時,磁盤訪問的次數為 h (讀取搜索路徑上的節點) +2s (回寫兩個分裂出的新節點) +1(回寫新的根節點或插入後沒有導致分裂的節點)。因此,所需要的磁盤訪問次數是 h+2s+1,最多可達到 3h+1。因此插入的代價較大。


4. 刪除性能


B樹的刪除會發生結點合併操作。最壞情況下磁盤訪問次數是 3h=(找到包含被刪除元素需要h次讀訪問)+(獲取第2至h層的最相鄰兄弟需要h-1次讀訪問)+(在第3至h層的合併需要h-2次寫訪問)+(對修改過的根節點和第2層的兩個節點進行3次寫訪問)。


5. 應用場景


B樹/B+樹主要用於磁盤文件組織 數據索引和數據庫索引等場景。


6. 種樹




05 B+ 樹


1. 定義


B+樹是B-樹的一種變體,B+樹相比B-樹的特點:


(1)索引節點的key值均會出現在葉子節點中。
(2)索引節點中的key值在葉子節點中或者為最大值或者為最小值。
(3)葉子節點使用單鏈表的形式鏈接起來。


2. 查找性能


(1)在相同數量的待查數據下,B+樹查找過程中需要調用的磁盤IO操作要少於普通B-樹。由於B+樹所在的磁盤存儲背景下,因此B+樹的查找性能要好於B-樹。 


(2)B+樹的查找效率更加穩定,因為所有葉子結點都處於同一層中,而且查找所有關鍵字都必須走完從根結點到葉子結點的全部歷程。因此同一顆B+樹中,任何關鍵字的查找比較次數都是一樣的。而B樹的查找是不穩定的。


3. 插入性能


B+樹的插入過程與B樹類似,性能也基本一致。


4. 刪除性能


刪除性能與B樹也基本一致。


5. 應用場景


B樹/B+樹主要用於磁盤文件組織 數據索引和數據庫索引等場景。


6. 種樹




06 霍夫曼樹


1. 定義


給定 n 個權值作為 n 個葉子結點,構造一棵二叉樹,若該樹的帶權路徑長度達到最小,稱這樣的二叉樹為最優二叉樹,也稱為霍夫曼樹(Huffman Tree)。


霍夫曼樹是帶權路徑長度最短的樹,權值較大的結點離根較近。


2. 應用場景


霍夫曼樹主要用於霍夫曼編碼,進行數據壓縮領域。


▲霍夫曼編碼



上面這六種樹中,你爬過哪幾種樹?不管爬樹還是種樹,你都要先搞定算法。下面這本書會給你幫助。



推薦語:通過閲讀本書,你將可以:


  • 解決新的編碼問題,提升現有解決方案的性能。

  • 快速確定與問題相關的算法,並挑選最佳算法。

  • 獲取帶有實現技巧的算法解決方案(採用C、C++、Java和Python實現)。

  • 瞭解算法的預期性能和最佳性能所需要的條件。

  • 使用高級數據結構提升算法效率。



據統計,99%的大咖都完成了這個神操作



更多精彩


在公眾號後台對話框輸入以下關鍵詞

查看更多優質內容!


PPT | 報告 | 讀書 | 書單 | 乾貨 

大數據 | 揭祕 | Python | 可視化

人工智能 | 機器學習 | 深度學習 | 神經網絡

AI | 1024 | 段子 | 區塊鏈 | 數學


猜你想看


  • 被兩會代表頻繁“點名”,2019的第一波風口要來了?

  • 女神節,來聊聊這幾位神一般的“程序媛”

  • 馬化騰提議加強基礎科學研究,中國“芯痛”能解決嗎?

  • 數據又多又散,“孤島困境”怎樣破局?



Q: 你都爬過哪些樹?

歡迎留言與大家分享

覺得不錯,請把這篇文章分享給你的朋友

轉載 / 投稿請聯繫:[email protected]

更多精彩,請在後台點擊“歷史文章”查看

https://hk.wxwenku.com/d/110021259