公歷 3 月 12 日是一年一度的植樹節(jié)。旨在宣傳保護(hù)森林,并動(dòng)員群眾參加植樹造林活動(dòng)。說到樹,程序猿們肯定不陌生,趁著這個(gè)植樹節(jié),普及一下程序猿們經(jīng)常遇見的樹。
二叉搜索樹
定義
二叉搜索樹又稱二叉查找樹,亦稱為二叉排序樹。設(shè) x 為二叉查找樹中的一個(gè)節(jié)點(diǎn),x 節(jié)點(diǎn)包含關(guān)鍵字 key,節(jié)點(diǎn)x 的 key 值記為 key[x] 。如果 y 是 x 的左子樹中的一個(gè)節(jié)點(diǎn),則 key[y] <= key[x] ;如果 y 是 x 的右子樹的一個(gè)節(jié)點(diǎn),則 key[y] >= key[x] 。
查找性能
當(dāng)數(shù)據(jù)數(shù)目為 N,樹高度保持 logN 附近。則平均查找長(zhǎng)度與 logN 成正比,查找平均時(shí)間復(fù)雜度為 O(logN) 。 當(dāng)先后插入的關(guān)鍵字有序時(shí),二叉搜索樹退化成單支樹結(jié)構(gòu)。此時(shí)樹高 N 。平均查找長(zhǎng)度為 (N+1)/2 ,查找的平均時(shí)間復(fù)雜度為 O(N) 。
插入性能
插入效率與查找效率一致。??
刪除性能
刪除節(jié)點(diǎn)時(shí),若節(jié)點(diǎn)為葉子節(jié)點(diǎn),或者節(jié)點(diǎn)只有單一子樹,則時(shí)間復(fù)雜度為 O(1) 。若節(jié)點(diǎn)既有左子樹又有右子樹,則需要執(zhí)行遞歸過程,對(duì)應(yīng)時(shí)間復(fù)雜度為 O(logN) 。
應(yīng)用場(chǎng)景
二叉排序樹就既有鏈表的好處,也有數(shù)組的好處,因此在處理大批量的動(dòng)態(tài)的數(shù)據(jù)是比較有用。
種樹
平衡二叉樹
定義
平衡二叉樹是一種特殊的二叉搜索樹。平衡二叉樹保證節(jié)點(diǎn)平衡因子的絕對(duì)值不超過1,保證了樹的平衡。
查找性能
平衡二叉樹是嚴(yán)格平衡的,那么查找過程與二叉搜索樹一樣,只是平衡二叉樹不會(huì)出現(xiàn)最差的單支樹情形。因此查找效率最好,最壞情況時(shí)間復(fù)雜度為 O(logN) 。
插入性能
插入數(shù)據(jù)之前需要進(jìn)行查找操作,查找到插入位置。插入數(shù)據(jù)后需要進(jìn)行旋轉(zhuǎn)操作,旋轉(zhuǎn)操作復(fù)雜度為常量級(jí)。因此插入數(shù)據(jù)的時(shí)間復(fù)雜度與查找相同為 O(logN)。
刪除性能
刪除數(shù)據(jù)同樣需要查找數(shù)據(jù),在刪除數(shù)據(jù)后需要進(jìn)行調(diào)整。一次刪除最多需要需要O(logN)次旋轉(zhuǎn),因此刪除數(shù)據(jù)的時(shí)間復(fù)雜度為O(logN)+O(logN)=O(2logN)。
應(yīng)用場(chǎng)景
SGI/STL的 set/map 底層都是用紅黑樹(平衡二叉樹的一種)實(shí)現(xiàn)的。
種樹
紅黑樹
定義
平衡二叉樹的嚴(yán)格平衡策略以犧牲建立查找結(jié)構(gòu)(插入,刪除操作)的代價(jià),換來了穩(wěn)定的O(logN) 的查找時(shí)間復(fù)雜度。紅黑樹采用了折中策略,即不犧牲太大的建立查找結(jié)構(gòu)的代價(jià),同時(shí)又能保證穩(wěn)定高效的查找效率。
查找性能
由于紅黑樹的性質(zhì)(最長(zhǎng)路徑長(zhǎng)度不超過最短路徑長(zhǎng)度的 2 倍),可以說明紅黑樹雖然不像平衡二叉樹一樣是嚴(yán)格平衡的,但平衡性能還是要比二叉搜索樹要好。其查找代價(jià)基本維持在 O(logN) 左右,但在最差情況下(最長(zhǎng)路徑是最短路徑的 2 倍少 1),比平衡二叉樹效率低一些。
插入性能
紅黑樹插入結(jié)點(diǎn)時(shí),需要旋轉(zhuǎn)操作和變色操作。但由于只需要保證紅黑樹基本平衡就可以了。因此插入結(jié)點(diǎn)最多只需要2次旋轉(zhuǎn),這一點(diǎn)和平衡二叉樹的插入操作一樣,但是變色操作的時(shí)間復(fù)雜度為O(logN)。
刪除性能
紅黑樹的刪除操作代價(jià)要比平衡二叉樹要好的多,刪除一個(gè)結(jié)點(diǎn)最多只需要 3 次旋轉(zhuǎn)操作,保證了刪除時(shí)間復(fù)雜度維持在常量級(jí)。
應(yīng)用場(chǎng)景
應(yīng)用場(chǎng)景有很多。
Java 中的 TreeSet ,TreeMap,HashMap
C++ 的 STL中的 map 和 set 都是用紅黑樹實(shí)現(xiàn)的
epoll 在內(nèi)核中的實(shí)現(xiàn),用紅黑樹管理事件塊
nginx 中,用紅黑樹管理 timer 等
linux 進(jìn)程調(diào)度 Completely Fair Schedule r,用紅黑樹管理進(jìn)程控制塊
種樹
B 樹
定義
B樹是一種多路平衡查找樹,在相同數(shù)據(jù)數(shù)目情形下,B樹的高度更小,這樣就減少了磁盤的IO次數(shù),在文件系統(tǒng)以及數(shù)據(jù)庫(kù)索引等場(chǎng)景下提升了查找效率。
查找性能
B樹的查找分成兩種:一種是從一個(gè)結(jié)點(diǎn)查找另一結(jié)點(diǎn)的地址的時(shí)候,需要定位磁盤地址(查找地址),查找代價(jià)極高。另一種是將結(jié)點(diǎn)中的有序關(guān)鍵字序列放入內(nèi)存,進(jìn)行優(yōu)化查找(可以用折半),相比查找代價(jià)極低。而B樹的高度很小,因此在這一背景下,B樹比任何二叉結(jié)構(gòu)查找樹的效率都要高很多。
插入性能
B樹的插入會(huì)發(fā)生結(jié)點(diǎn)的分裂操作。當(dāng)插入操作引起了 s 個(gè)節(jié)點(diǎn)的分裂時(shí),磁盤訪問的次數(shù)為 h (讀取搜索路徑上的節(jié)點(diǎn)) +2s (回寫兩個(gè)分裂出的新節(jié)點(diǎn)) +1(回寫新的根節(jié)點(diǎn)或插入后沒有導(dǎo)致分裂的節(jié)點(diǎn))。因此,所需要的磁盤訪問次數(shù)是 h+2s+1,最多可達(dá)到 3h+1。因此插入的代價(jià)較大。
刪除性能
B樹的刪除會(huì)發(fā)生結(jié)點(diǎn)合并操作。最壞情況下磁盤訪問次數(shù)是 3h=(找到包含被刪除元素需要h次讀訪問)+(獲取第2至h層的最相鄰兄弟需要h-1次讀訪問)+(在第3至h層的合并需要h-2次寫訪問)+(對(duì)修改過的根節(jié)點(diǎn)和第2層的兩個(gè)節(jié)點(diǎn)進(jìn)行3次寫訪問)。
應(yīng)用場(chǎng)景
B樹/B+樹主要用于磁盤文件組織 數(shù)據(jù)索引和數(shù)據(jù)庫(kù)索引等場(chǎng)景。
種樹
B+ 樹
定義
B+樹是B-樹的一種變體,B+樹相比B-樹的特點(diǎn):
(1)索引節(jié)點(diǎn)的key值均會(huì)出現(xiàn)在葉子節(jié)點(diǎn)中。(2)索引節(jié)點(diǎn)中的key值在葉子節(jié)點(diǎn)中或者為最大值或者為最小值。(3)葉子節(jié)點(diǎn)使用單鏈表的形式鏈接起來。
查找性能
(1)在相同數(shù)量的待查數(shù)據(jù)下,B+樹查找過程中需要調(diào)用的磁盤IO操作要少于普通B-樹。由于B+樹所在的磁盤存儲(chǔ)背景下,因此B+樹的查找性能要好于B-樹。
(2)B+樹的查找效率更加穩(wěn)定,因?yàn)樗腥~子結(jié)點(diǎn)都處于同一層中,而且查找所有關(guān)鍵字都必須走完從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的全部歷程。因此同一顆B+樹中,任何關(guān)鍵字的查找比較次數(shù)都是一樣的。而B樹的查找是不穩(wěn)定的。
插入性能
B+樹的插入過程與B樹類似,性能也基本一致。
刪除性能
刪除性能與B樹也基本一致。
應(yīng)用場(chǎng)景
B樹/B+樹主要用于磁盤文件組織 數(shù)據(jù)索引和數(shù)據(jù)庫(kù)索引等場(chǎng)景。
種樹
霍夫曼樹
定義
給定 n 個(gè)權(quán)值作為 n 個(gè)葉子結(jié)點(diǎn),構(gòu)造一棵二叉樹,若該樹的帶權(quán)路徑長(zhǎng)度達(dá)到最小,稱這樣的二叉樹為最優(yōu)二叉樹,也稱為霍夫曼樹(Huffman Tree)。
霍夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹,權(quán)值較大的結(jié)點(diǎn)離根較近。
應(yīng)用場(chǎng)景
霍夫曼樹主要用于霍夫曼編碼,進(jìn)行數(shù)據(jù)壓縮領(lǐng)域。
霍夫曼編碼
-
磁盤
+關(guān)注
關(guān)注
1文章
356瀏覽量
25138 -
C++
+關(guān)注
關(guān)注
21文章
2090瀏覽量
73406 -
二叉樹
+關(guān)注
關(guān)注
0文章
74瀏覽量
12296
原文標(biāo)題:植樹節(jié),程序員要爬哪些“樹”?
文章出處:【微信號(hào):rgznai100,微信公眾號(hào):rgznai100】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論