python算法与数据结构-数据结构中常用树的介绍(45)
閱讀目錄
- 一、樹的定義
- 二、二叉樹介紹
- 三、完全二叉樹介紹
- 四、滿二叉樹介紹?
- 五、平衡二叉樹(AVL樹)介紹
- 六、紅黑樹介紹
- 七、霍夫曼樹
- 八、B樹介紹
- 九、B+樹介紹
- 十、B*樹介紹
- ?十一、Trie樹
一、樹的定義
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),是由n(n >=0)個結(jié)點組成的有限集合。
如果n==0,樹為空樹。
如果n>0,
樹有一個特定的結(jié)點,根結(jié)點
根結(jié)點只有直接后繼,沒有直接前驅(qū)。
除根結(jié)點以外的其他結(jié)點劃分為m(m>=0)個互不相交的有限集合,T0,T1,T2,...,Tm-1,每個結(jié)合是一棵樹,稱為根結(jié)點的子樹。
- 樹(tree):是以邊(edge)相連的結(jié)點(node)的集合,每個結(jié)點存儲對應的值(value/data),當存在子結(jié)點時與之相連。?
- 根節(jié)點(root):是樹的首個結(jié)點,在相連兩結(jié)點中更接近根結(jié)點的成為父結(jié)點(parent node),相應的另一個結(jié)點稱為子結(jié)點(parent node)。
- 邊(edge):所有結(jié)點都由邊相連,用于標識結(jié)點間的關(guān)系。邊是樹中很重要的一個概念,因為我們用它來確定節(jié)點之間的關(guān)系。
- 葉子節(jié)點(Leaves):是樹的末端結(jié)點,他們沒有子結(jié)點,就像真實的樹那樣 ,由根開始,伸展枝干,到葉為止。
- 樹高(height):是由根結(jié)點出發(fā),到子結(jié)點的最長路徑長度。?
- 節(jié)點深度(depth):是指對應結(jié)點到根結(jié)點路徑長度。?
?
二、二叉樹介紹
二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)
二叉樹的性質(zhì)(特性)
性質(zhì)1: ?在二叉樹的第i層上至多有2^(i-1)個結(jié)點(i>0)
性質(zhì)2: 深度為k的二叉樹至多有2^k - 1個結(jié)點(k>0)
性質(zhì)3: 對于任意一棵二叉樹,如果其葉結(jié)點數(shù)為N0,而度數(shù)為2的結(jié)點總數(shù)為N2,則N0=N2+1;
性質(zhì)4: 具有n個結(jié)點的完全二叉樹的深度必為 log2(n+1)
性質(zhì)5:對完全二叉樹,若從上至下、從左至右編號,則編號為i 的結(jié)點,其左孩子編號必為2i,其右孩子編號必為2i+1;其雙親的編號必為i/2(i=1 時為根,除外)
三、完全二叉樹介紹
完全二叉樹——若設二叉樹的高度為h,除第 h 層外,其它各層 (1~h-1) 的結(jié)點數(shù)都達到最大個數(shù),第h層有葉子結(jié)點,并且葉子結(jié)點都是從左到右依次排布,這就是完全二叉樹。
?
四、滿二叉樹介紹?
? 滿二叉樹——除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。滿二叉樹:每一層都掛滿了節(jié)點
?
五、平衡二叉樹(AVL樹)介紹
AVL樹本質(zhì)上是一顆二叉查找樹,但是它又具有以下特點:它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,并且左右兩個子樹都是一棵平衡二叉樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為一,所以它也被稱為平衡二叉樹。?
?
六、紅黑樹介紹
紅黑樹是一種平衡二叉樹,在平衡二叉樹的基礎(chǔ)上每個節(jié)點又增加了一個顏色的屬性,節(jié)點的顏色只能是紅色或黑色,其每個結(jié)點滿足以下條件:
?
?
七、霍夫曼樹
霍夫曼樹是二叉樹的一種特殊形式,又稱為最優(yōu)二叉樹,其主要作用在于數(shù)據(jù)壓縮和編碼長度的優(yōu)化。
7.1、路徑和路徑長度
在一棵樹中,從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路,稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1,則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。
?
7.2結(jié)點的權(quán)及帶權(quán)路徑長度
若將樹中結(jié)點賦給一個有著某種含義的數(shù)值,則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為:從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。
?
7.3樹的帶權(quán)路徑長度
所謂樹的帶權(quán)路徑長度,就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度。樹的帶權(quán)路徑長度記為WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)。上圖中的WPL = 6*2+3*2+8*2 = 34
7.4霍夫曼樹的構(gòu)造
給定n個權(quán)值作為n個葉子結(jié)點,構(gòu)造一棵二叉樹,若帶權(quán)路徑長度達到最小,稱這樣的二叉樹為最優(yōu)二叉樹,也稱為霍夫曼樹(Huffman Tree)。例如:給定3課二叉樹,都有4個葉子節(jié)點,A,B,C,D,分別帶權(quán)7,5,2,4,求他們的帶全路徑長度。
WPL1 = 7*2+5*2+2*2+4*2 =?36
WPL2 = 7*3+5*3+2*1+4*2 =?46
WPL3 = 7*1+5*2+2*3+4*3 =?35?
八、B樹介紹
B樹也是一種用于查找的平衡樹,但是它不是二叉樹。
B樹的定義:B樹(B-tree)是一種樹狀數(shù)據(jù)結(jié)構(gòu),能夠用來存儲排序后的數(shù)據(jù)。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、循序存取、插入數(shù)據(jù)及刪除的動作,都在對數(shù)時間內(nèi)完成。B樹,概括來說是一個一般化的二叉查找樹,可以擁有多于2個子節(jié)點。與自平衡二叉查找樹不同,B-樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程,從而加快存取速度。這種數(shù)據(jù)結(jié)構(gòu)常被應用在數(shù)據(jù)庫和文件系統(tǒng)的實作上。
在B樹中查找給定關(guān)鍵字的方法是,首先把根結(jié)點取來,在根結(jié)點所包含的關(guān)鍵字K1,…,Kn查找給定的關(guān)鍵字(可用順序查找或二分查找法),若找到等于給定值的關(guān)鍵字,則查找成功;否則,一定可以確定要查找的關(guān)鍵字在Ki與Ki+1之間,Pi為指向子樹根節(jié)點的指針,此時取指針Pi所指的結(jié)點繼續(xù)查找,直至找到,或指針Pi為空時查找失敗。
? B樹作為一種多路搜索樹(并不是二叉的):
1) 定義任意非葉子結(jié)點最多只有M個兒子;且M>2;
2)?根結(jié)點的兒子數(shù)為[2, M];
3)?除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M];
4)?每個結(jié)點存放至少M/2-1(取上整)和至多M-1個關(guān)鍵字;(至少2個關(guān)鍵字)
5)?非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1;
6)?非葉子結(jié)點的關(guān)鍵字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
7)?非葉子結(jié)點的指針:P[1], P[2], …, P[M];其中P[1]指向關(guān)鍵字小于K[1]的子樹,P[M]指向關(guān)鍵字大于K[M-1]的子樹,其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹;
8)?所有葉子結(jié)點位于同一層;
???????如下圖為一個M=3的B樹示例:
B樹也是一種用于查找的平衡樹,但是它不是二叉樹。
B樹的定義:B樹(B-tree)是一種樹狀數(shù)據(jù)結(jié)構(gòu),能夠用來存儲排序后的數(shù)據(jù)。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、循序存取、插入數(shù)據(jù)及刪除的動作,都在對數(shù)時間內(nèi)完成。B樹,概括來說是一個一般化的二叉查找樹,可以擁有多于2個子節(jié)點。與自平衡二叉查找樹不同,B-樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程,從而加快存取速度。這種數(shù)據(jù)結(jié)構(gòu)常被應用在數(shù)據(jù)庫和文件系統(tǒng)的實作上。
在B樹中查找給定關(guān)鍵字的方法是,首先把根結(jié)點取來,在根結(jié)點所包含的關(guān)鍵字K1,…,Kn查找給定的關(guān)鍵字(可用順序查找或二分查找法),若找到等于給定值的關(guān)鍵字,則查找成功;否則,一定可以確定要查找的關(guān)鍵字在Ki與Ki+1之間,Pi為指向子樹根節(jié)點的指針,此時取指針Pi所指的結(jié)點繼續(xù)查找,直至找到,或指針Pi為空時查找失敗。
B樹作為一種多路搜索樹(并不是二叉的):
1) 定義任意非葉子結(jié)點最多只有M個兒子;且M>2;
2)?根結(jié)點的兒子數(shù)為[2, M];
3)?除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M];
4)?每個結(jié)點存放至少M/2-1(取上整)和至多M-1個關(guān)鍵字;(至少2個關(guān)鍵字)
5)?非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1;
6)?非葉子結(jié)點的關(guān)鍵字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
7)?非葉子結(jié)點的指針:P[1], P[2], …, P[M];其中P[1]指向關(guān)鍵字小于K[1]的子樹,P[M]指向關(guān)鍵字大于K[M-1]的子樹,其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹;
8)?所有葉子結(jié)點位于同一層;
???????如下圖為一個M=3的B樹示例:
?
九、B+樹介紹
B+樹是B樹的變體,也是一種多路搜索樹:
1) 其定義基本與B-樹相同,除了:
2) 非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同;
3) 非葉子結(jié)點的子樹指針P[i],指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(B-樹是開區(qū)間);
4) 為所有葉子結(jié)點增加一個鏈指針;
5) 所有關(guān)鍵字都在葉子結(jié)點出現(xiàn);
下圖為M=3的B+樹的示意圖:
?
B+樹的搜索與B樹也基本相同,區(qū)別是B+樹只有達到葉子結(jié)點才命中(B樹可以在非葉子結(jié)點命中),其性能也等價于在關(guān)鍵字全集做一次二分查找;
B+的性質(zhì):
1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中(稠密索引),且鏈表中的關(guān)鍵字恰好是有序的;
2.不可能在非葉子結(jié)點命中;
3.非葉子結(jié)點相當于是葉子結(jié)點的索引(稀疏索引),葉子結(jié)點相當于是存儲(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層;
4.更適合文件索引系統(tǒng)。
十、B*樹介紹
B*樹是B+樹的變體,在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針,將結(jié)點的最低利用率從1/2提高到2/3。
B*樹如下圖所示:?
?
B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)*M,即塊的最低使用率為2/3(代替B+樹的1/2);
B+樹的分裂:當一個結(jié)點滿時,分配一個新的結(jié)點,并將原結(jié)點中1/2的數(shù)據(jù)復制到新結(jié)點,最后在父結(jié)點中增加新結(jié)點的指針;B+樹的分裂只影響原結(jié)點和父結(jié)點,而不會影響兄弟結(jié)點,所以它不需要指向兄弟的指針;
B*樹的分裂:當一個結(jié)點滿時,如果它的下一個兄弟結(jié)點未滿,那么將一部分數(shù)據(jù)移到兄弟結(jié)點中,再在原結(jié)點插入關(guān)鍵字,最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字(因為兄弟結(jié)點的關(guān)鍵字范圍改變了);如果兄弟也滿了,則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點,并各復制1/3的數(shù)據(jù)到新結(jié)點,最后在父結(jié)點增加新結(jié)點的指針;
所以,B*樹分配新結(jié)點的概率比B+樹要低,空間使用率更高。
?十一、Trie樹
Tire樹稱為字典樹,又稱單詞查找樹,Trie樹,是一種樹形結(jié)構(gòu),是一種哈希樹的變種。典型應用是用于統(tǒng)計,排序和保存大量的字符串(但不僅限于字符串),所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是:利用字符串的公共前綴來減少查詢時間,最大限度地減少無謂的字符串比較,查詢效率比哈希樹高?!?/p>
Tire樹的三個基本性質(zhì):
1)?根節(jié)點不包含字符,除根節(jié)點外每一個節(jié)點都只包含一個字符;
2) 從根節(jié)點到某一節(jié)點,路徑上經(jīng)過的字符連接起來,為該節(jié)點對應的字符串;
3) 每個節(jié)點的所有子節(jié)點包含的字符都不相同。
Tire樹的應用:
1)?串的快速檢索
給出N個單詞組成的熟詞表,以及一篇全用小寫英文書寫的文章,請你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。
在這道題中,我們可以用數(shù)組枚舉,用哈希,用字典樹,先把熟詞建一棵樹,然后讀入文章進行比較,這種方法效率是比較高的。
2)?“串”排序
給定N個互不相同的僅由一個單詞構(gòu)成的英文名,讓你將他們按字典序從小到大輸出。用字典樹進行排序,采用數(shù)組的方式創(chuàng)建字典樹,這棵樹的每個結(jié)點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。
3) 最長公共前綴
對所有串建立字典樹,對于兩個串的最長公共前綴的長度即他們所在的結(jié)點的公共祖先個數(shù),于是,問題就轉(zhuǎn)化為求公共祖先的問題。
?
侯哥語錄:我曾經(jīng)是一個職業(yè)教育者,現(xiàn)在是一個自由開發(fā)者。我希望我的分享可以和更多人一起進步。分享一段我喜歡的話給大家:"我所理解的自由不是想干什么就干什么,而是想不干什么就不干什么。當你還沒有能力說不得時候,就努力讓自己變得強大,擁有說不得權(quán)利。"
來源:https://www.cnblogs.com/Se7eN-HOU/p/11132082.html
總結(jié)
以上是生活随笔為你收集整理的python算法与数据结构-数据结构中常用树的介绍(45)的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 微业贷申请失败什么原因 这三点你需要注意
- 下一篇: 股票z值偏低是什么意思