樹(shù)(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-14 18:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-14 18:30:01 來(lái)源：信息時(shí)代

    樹(shù) : 在計(jì)算機(jī)科學(xué)技術(shù)中有廣泛的應(yīng)用的一種特殊的圖。
1.無(wú)向樹(shù)
連通無(wú)回路(這里指初級(jí)和簡(jiǎn)單回路)的無(wú)向圖稱為無(wú)向樹(shù),常用T表示樹(shù)。若G無(wú)回路且至少有兩個(gè)連通分支,則稱G為森林。在無(wú)向樹(shù)T中,1度頂點(diǎn)稱為樹(shù)葉,度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)。
2.無(wú)向樹(shù)的重要性質(zhì):
(1)n階樹(shù)的邊數(shù)m=n-1。
(2)若T是非平凡的無(wú)向樹(shù),則T至少有兩片樹(shù)葉。
(3)在非平凡的無(wú)向樹(shù)的任何兩個(gè)不同的頂點(diǎn)之間加一條新邊,所得圖中有一條唯一含此邊的回路。
3.生成樹(shù)
若連通無(wú)向圖G的生成子圖(參見(jiàn)圖論)T是樹(shù),則稱T為G的生成樹(shù)。T中的邊也稱為樹(shù)枝,G的不在T中的邊稱為T的弦。
例如,在圖1中由實(shí)線邊e₁、e₂、e₃、e₆構(gòu)成的子圖T是該圖的一棵生成樹(shù),虛線邊e₄、e₅為T的弦。

圖1 生成樹(shù)

4. 最小生成樹(shù)
對(duì)圖中的每一條邊e關(guān)聯(lián)一個(gè)實(shí)數(shù)W(e),把它稱作帶權(quán)圖。設(shè)T是無(wú)向連通帶權(quán)圖G的一棵生成樹(shù),它的所有邊的權(quán)之和稱作T的權(quán)。無(wú)向連通帶權(quán)圖G的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱作G的最小生成樹(shù)。例如,圖2中實(shí)線邊所示的生成樹(shù)T為該圖的最小生成樹(shù),其權(quán)W(T)=14。有多種求最小生成樹(shù)的算法,如避圈法(Kruskal法)、破圈法、逐步短接法、斷集法等。

圖2 最小生成樹(shù)

5. 根樹(shù)
基圖為樹(shù)的有向圖稱作有向樹(shù)。在有向樹(shù)中,主要研究根樹(shù)。只有一個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度全為1的有向樹(shù)稱為根樹(shù)。在根樹(shù)中,入度為0的頂點(diǎn)稱為樹(shù)根;入度為1,出度為0的頂點(diǎn)稱為樹(shù)葉;入度為1,出度不為0的頂點(diǎn)稱為內(nèi)點(diǎn); 內(nèi)點(diǎn)和樹(shù)根統(tǒng)稱為分支點(diǎn)。從樹(shù)根到頂點(diǎn)v的路徑長(zhǎng)度稱為v的層數(shù),樹(shù)中頂點(diǎn)層數(shù)的最大值稱為樹(shù)高。在畫(huà)根樹(shù)時(shí),通常將樹(shù)根放在最上方,所有有向邊的方向向下并略去邊上的箭頭。例如,圖3給出一棵根樹(shù),a為樹(shù)根,d、g、h、i為樹(shù)葉,b、c、e、f為內(nèi)點(diǎn),a、b、c、e、f為分支點(diǎn)。

圖3 根樹(shù)

設(shè)T為根樹(shù), ∀u,v∈V(T), 若u到v有通路,則稱u是v的祖先,v是u的后代;若<u,v>∈E(T),則稱u是v的父親,v是u的兒子;若兩個(gè)頂點(diǎn)有共同的父親,則稱它們是兄弟。按照這樣的叫法,也把根樹(shù)叫作家族樹(shù)。在根樹(shù)T中,規(guī)定同層頂點(diǎn)的排成順序,這時(shí)稱T為有序樹(shù)。若根樹(shù)T的每個(gè)分支點(diǎn)至少有r個(gè)兒子,則稱T為r叉樹(shù); 若T的每個(gè)分支點(diǎn)都恰好有r個(gè)兒子,則稱T為r叉正則樹(shù);所有樹(shù)葉的層數(shù)相同(都等于樹(shù)高)的r叉正則樹(shù)稱為r叉完全正則樹(shù)。最常用的是2叉樹(shù)和2叉有序樹(shù)。
6.最優(yōu)2叉樹(shù)
設(shè)2叉樹(shù)T有t片樹(shù)葉,每一片樹(shù)葉v_i的權(quán)為w_i(i=1,2,…,t),用l(v_i)表示頂點(diǎn)v_i的層數(shù),稱

為T的權(quán)。給定w₁,w₂,…,w_t,在所有t片樹(shù)葉的權(quán)為w₁,w₂,…,w_t的2叉樹(shù)中,權(quán)最小的2叉樹(shù)稱為最優(yōu)2叉樹(shù),簡(jiǎn)稱最優(yōu)樹(shù)。例如,圖4給出權(quán)為2、2、3、3、5的最優(yōu)樹(shù),其權(quán)W(T)=34?？捎肏uffman算法求最優(yōu)樹(shù)。利用最優(yōu)樹(shù)可以產(chǎn)生最佳前綴碼,這在信息傳輸中非常有用。

圖4 最優(yōu)樹(shù)