湘潭大學(xué) 數(shù)據(jù)結(jié)構(gòu) Ch04 Trees

1、編輯編輯pptppt第四章 樹編輯編輯pptppt1 預(yù)備知識預(yù)備知識 客觀世界中許多事物存在層次關(guān)系客觀世界中許多事物存在層次關(guān)系 人類社會家譜人類社會家譜 社會組織結(jié)構(gòu)社會組織結(jié)構(gòu) 圖書信息管理圖書信息管理編輯編輯pptppt哲學(xué)宗教哲學(xué)宗教文學(xué)文學(xué)醫(yī)藥衛(wèi)生醫(yī)藥衛(wèi)生農(nóng)業(yè)科學(xué)農(nóng)業(yè)科學(xué)工業(yè)技術(shù)工業(yè)技術(shù)哲學(xué)理論哲學(xué)理論世界哲學(xué)世界哲學(xué)歐洲哲學(xué)歐洲哲學(xué)宗教宗教宗教分析研究宗教分析研究宗教理論與概況宗教理論與概況佛教佛教宗教與社會政治宗教與社會政治宗教與科學(xué)宗教與科學(xué)破除迷信破除迷信綜合綜合電工技術(shù)電工技術(shù)計(jì)算機(jī)計(jì)算機(jī)建筑科學(xué)建筑科學(xué)水利工程水利工程一般性技術(shù)一般性技術(shù)計(jì)算機(jī)軟件計(jì)算機(jī)軟件電子模擬計(jì)

2、算機(jī)電子模擬計(jì)算機(jī)微型計(jì)算機(jī)微型計(jì)算機(jī)計(jì)算機(jī)的應(yīng)用計(jì)算機(jī)的應(yīng)用圖書圖書軟件工程軟件工程程序語言程序語言編譯程序編譯程序操作系統(tǒng)操作系統(tǒng)編輯編輯pptppt1 預(yù)備知識預(yù)備知識【定義定義】樹是一些節(jié)點(diǎn)的集合。這個(gè)集合可以是空集；若非樹是一些節(jié)點(diǎn)的集合。這個(gè)集合可以是空集；若非空，則樹包含：空，則樹包含： (1) 一個(gè)被稱為一個(gè)被稱為根根的特殊節(jié)點(diǎn)的特殊節(jié)點(diǎn) r; (2) 以及以及0個(gè)或多個(gè)非空個(gè)或多個(gè)非空（子）樹（子）樹 T1, , Tk，每一棵子樹的根，每一棵子樹的根都被來自根都被來自根 r 的一條有向邊的一條有向邊（ edge）所連接。所連接。Note: 子樹是不相交的。因此樹中的每一個(gè)節(jié)點(diǎn)

3、都是一棵子子樹是不相交的。因此樹中的每一個(gè)節(jié)點(diǎn)都是一棵子樹的根。樹的根。 一棵有一棵有N個(gè)節(jié)點(diǎn)的樹中有個(gè)節(jié)點(diǎn)的樹中有 條邊。條邊。 根節(jié)點(diǎn)通常畫在上方。根節(jié)點(diǎn)通常畫在上方。N 1編輯編輯pptpptACBDGFEHIJMLK 節(jié)點(diǎn)的度（節(jié)點(diǎn)的度（Degree）:= 節(jié)點(diǎn)的子樹個(gè)數(shù)。節(jié)點(diǎn)的子樹個(gè)數(shù)。 例如例如, degree(A) = 3, degree(F) = 0. 樹的度樹的度:= 例如例如, degree of this tree = 3. )node(degreemaxtreenode 葉節(jié)點(diǎn)葉節(jié)點(diǎn)（leaf）:= 度為度為0的節(jié)點(diǎn)的節(jié)點(diǎn) (沒有孩子沒有孩子)。 父節(jié)點(diǎn)（父節(jié)點(diǎn)（Par

4、ent） := 有子樹的節(jié)點(diǎn)是有子樹的節(jié)點(diǎn)是其子樹根節(jié)點(diǎn)的父節(jié)點(diǎn)。其子樹根節(jié)點(diǎn)的父節(jié)點(diǎn)。 子節(jié)點(diǎn)（子節(jié)點(diǎn)（Child） := 若若A節(jié)點(diǎn)是節(jié)點(diǎn)是B節(jié)點(diǎn)的父節(jié)點(diǎn)，則節(jié)點(diǎn)的父節(jié)點(diǎn)，則B節(jié)點(diǎn)是節(jié)點(diǎn)是A節(jié)點(diǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)，也叫的子節(jié)點(diǎn)，也叫孩子節(jié)點(diǎn)孩子節(jié)點(diǎn)。 兄弟節(jié)點(diǎn)兄弟節(jié)點(diǎn)（sibling） := 具有同一父節(jié)點(diǎn)的各節(jié)點(diǎn)彼此是兄弟節(jié)點(diǎn)。具有同一父節(jié)點(diǎn)的各節(jié)點(diǎn)彼此是兄弟節(jié)點(diǎn)。1 預(yù)備知識預(yù)備知識1. 術(shù)語術(shù)語編輯編輯pptppt1 預(yù)備知識預(yù)備知識ACBDGFEHIJMLK 祖先結(jié)點(diǎn)祖先結(jié)點(diǎn)(Ancestor) :=沿沿樹根到某一結(jié)點(diǎn)路徑樹根到某一結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是上的所有結(jié)點(diǎn)都是這個(gè)結(jié)點(diǎn)的祖先結(jié)

5、點(diǎn)。這個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)。 子孫結(jié)點(diǎn)子孫結(jié)點(diǎn)(Descendant) :=某一結(jié)點(diǎn)的某一結(jié)點(diǎn)的子樹中的所有結(jié)點(diǎn)子樹中的所有結(jié)點(diǎn)是這個(gè)是這個(gè)結(jié)點(diǎn)的子孫。結(jié)點(diǎn)的子孫。 ni的深度的深度:= 從根到從根到ni 唯一的路徑的長度。唯一的路徑的長度。 Depth(root) = 0. ni的高度的高度:= 從從ni 到一片葉子的最長路徑的長度。到一片葉子的最長路徑的長度。Height(leaf) = 0, height(D) = 2. 樹的高度（深度）樹的高度（深度）:= height(root) = depth(deepest leaf). 從從n1 到到 nk 的路徑的路徑 :=從結(jié)點(diǎn)從結(jié)點(diǎn)n1到到n

6、k的路徑被定的路徑被定義為一個(gè)結(jié)點(diǎn)序列義為一個(gè)結(jié)點(diǎn)序列n1 , n2 , , nk ，對于，對于1 i k, ni是是 ni+1的父結(jié)點(diǎn)。的父結(jié)點(diǎn)。 路徑長度路徑長度:=一條路徑的長度為這條路徑所一條路徑的長度為這條路徑所包含的邊包含的邊（分支）的個(gè)數(shù)（分支）的個(gè)數(shù)。編輯編輯pptppt2. 樹的實(shí)現(xiàn)樹的實(shí)現(xiàn) 鏈表表示法鏈表表示法ACBDGFEHIJMLKABCDEFGHIJKLM因此，每個(gè)節(jié)點(diǎn)的大小取決于因此，每個(gè)節(jié)點(diǎn)的大小取決于子樹數(shù)目。噢，這樣并不太好！子樹數(shù)目。噢，這樣并不太好！1 預(yù)備知識預(yù)備知識編輯編輯pptppt 兒子兒子-兄弟表示法兄弟表示法FirstChild NextSib

7、lingElementACBDGFEHIJMLKNACBNDENKN NFN NGHNIN NJN NLN NMNote: 這種表示法這種表示法并非唯一并非唯一的，因?yàn)闃涞墓?jié)點(diǎn)的孩子順序的，因?yàn)闃涞墓?jié)點(diǎn)的孩子順序是不固定的。是不固定的。1 預(yù)備知識預(yù)備知識編輯編輯pptppt 樹的遍歷樹的遍歷 訪問每個(gè)節(jié)點(diǎn)恰好一次訪問每個(gè)節(jié)點(diǎn)恰好一次 前序前序遍歷遍歷void preorder ( tree_ptr tree ) if ( tree ) visit ( tree ); for (each child C of tree ) preorder ( C ); 編輯編輯pptppt例例1 列出分級文

8、件系統(tǒng)中的目錄。列出分級文件系統(tǒng)中的目錄。輸出格式輸出格式: 深度深度為為 di 的文件的名字將被的文件的名字將被 di 次跳格次跳格(tab)縮進(jìn)后打印出縮進(jìn)后打印出來。來。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97 sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnix directory編輯編輯pptppt/usr mark bookCh1.cCh2.cCh3.c coursecop3530

9、 fall96syl.r spr97syl.r sum97syl.r hw.c alex hw.c bill work coursecop3212 fall96gradesp1.rp2.r fall97p2.rp1.rgradesstatic void ListDir ( DirOrFile D, int Depth ) if ( D is a legitimate entry ) PrintName (D, Depth ); if ( D is a directory ) for (each child C of D ) ListDir ( C, Depth + 1 ); Note: 深度深

10、度(Depth)是一個(gè)內(nèi)部簿記變量，是一個(gè)內(nèi)部簿記變量，而不是主調(diào)例程能夠期望知道的那種參而不是主調(diào)例程能夠期望知道的那種參數(shù)，因此，驅(qū)動例程數(shù)，因此，驅(qū)動例程ListDirectory用于用于將遞歸例程和外界連接起來。將遞歸例程和外界連接起來。void ListDirectory ( DirOrFile D )ListDir( D, 0 ); T ( N ) = O( N )編輯編輯pptppt 后序后序遍歷遍歷void postorder ( tree_ptr tree ) if ( tree ) for (each child C of tree ) postorder ( C ); v

11、isit ( tree ); 編輯編輯pptppt例例2 計(jì)算一個(gè)目錄的大小。計(jì)算一個(gè)目錄的大小。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnix directory with 11111111111111132468152341279static int SizeDir ( DirOrFile D ) int TotalSize; TotalSiz

12、e = 0; if ( D is a legitimate entry ) TotalSize = ( D ); if ( D is a directory ) for (each child C of D ) TotalSize += SizeDir(C); /* end if D is legal */ return TotalSize;T ( N ) = O( N )編輯編輯pptppt 層序?qū)有虮闅v遍歷void levelorder ( tree_ptr tree ) enqueue ( tree ); while (queue is not empty) visit ( T = de

13、queue ( ) ); for (each child C of T ) enqueue ( C ); 2453671112 324 536 745 6 7編輯編輯pptppt2 二叉樹二叉樹【定義定義】一棵二叉樹一棵二叉樹T是一個(gè)有窮的結(jié)點(diǎn)集合。這個(gè)集合是一個(gè)有窮的結(jié)點(diǎn)集合。這個(gè)集合可以為可以為空空，若不為空，則它是由，若不為空，則它是由根結(jié)點(diǎn)根結(jié)點(diǎn)和稱為其和稱為其左子樹左子樹TL和和右子樹右子樹TR的的兩個(gè)不相交的二叉樹組成?？梢妰蓚€(gè)不相交的二叉樹組成?？梢娮笞訕浜陀易訕溥€是二叉樹左子樹和右子樹還是二叉樹。 二叉樹具體五種基本形態(tài)二叉樹具體五種基本形態(tài)（1）空空二叉樹；二叉樹；（2）只有

14、根只有根結(jié)點(diǎn)的二叉樹；結(jié)點(diǎn)的二叉樹；（3）只有）只有根結(jié)點(diǎn)和左子樹根結(jié)點(diǎn)和左子樹TL的二叉樹；的二叉樹；（4）只有）只有根結(jié)點(diǎn)和右子樹根結(jié)點(diǎn)和右子樹TR的二叉樹；的二叉樹；（5）具有）具有根結(jié)點(diǎn)、左子樹根結(jié)點(diǎn)、左子樹TL和右子樹和右子樹TR的二叉樹。的二叉樹。TLTRTLTR (a) (b) (c) (d) (e)遞歸的定義形式遞歸的定義形式 二叉樹二叉樹與樹不同，除了每個(gè)結(jié)點(diǎn)至多有兩棵子樹外，與樹不同，除了每個(gè)結(jié)點(diǎn)至多有兩棵子樹外，子子樹樹有左右順序之分有左右順序之分。 例如，例如，下面下面兩個(gè)樹按一般樹的定義它們是兩個(gè)樹按一般樹的定義它們是同一個(gè)樹同一個(gè)樹；而對而對于二叉樹來講，它們是于二

15、叉樹來講，它們是不同的兩個(gè)樹不同的兩個(gè)樹。編輯編輯pptppt1616 特殊特殊二叉樹二叉樹 二叉樹的深度小于結(jié)點(diǎn)數(shù)二叉樹的深度小于結(jié)點(diǎn)數(shù)N，可以證明平均深度是，可以證明平均深度是)NO( “完美二叉樹完美二叉樹(Perfect Binary Tree)”。（也稱為。（也稱為滿二叉樹滿二叉樹）。）。BACBCDEHIJFG 一棵深度為一棵深度為k的有的有n個(gè)結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、個(gè)結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為從左到右的順序進(jìn)行編號，如果編號為i（1 i n）的結(jié)點(diǎn)與滿二）的結(jié)點(diǎn)與滿二叉樹中編號為叉樹中編號為

16、i 的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為“完全二叉樹完全二叉樹(Complete Binary Tree)”。1211KL151413MNO “斜二叉樹斜二叉樹(Skewed Binary Tree)”（也稱為退化二叉樹）；（也稱為退化二叉樹）BCDEHKJFG2 二叉樹二叉樹編輯編輯pptppt1717 二叉樹二叉樹的幾個(gè)的幾個(gè)重要的性質(zhì)重要的性質(zhì) 一個(gè)二叉樹第一個(gè)二叉樹第 i 層的最大結(jié)點(diǎn)數(shù)為：層的最大結(jié)點(diǎn)數(shù)為：2 i-1，i 1。 對任何非空的二叉樹對任何非空的二叉樹 T，若，若n0表示葉結(jié)點(diǎn)的個(gè)數(shù)、表示葉結(jié)點(diǎn)

17、的個(gè)數(shù)、n2是度為是度為2的非葉結(jié)點(diǎn)個(gè)數(shù)，那么兩者滿足關(guān)系的非葉結(jié)點(diǎn)個(gè)數(shù)，那么兩者滿足關(guān)系n0 = n2 +1。 深度為深度為k的二叉樹有最大結(jié)點(diǎn)總數(shù)為：的二叉樹有最大結(jié)點(diǎn)總數(shù)為：2 k-1，k 1。ABCDEKJFH n0 = 4，n1 = 2 n2 = 3 n0 = n2 +1證明證明: 設(shè)設(shè) n1 是度為是度為1結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù), n 是總的結(jié)點(diǎn)數(shù)是總的結(jié)點(diǎn)數(shù). 那么那么 n = 210nnn 設(shè)設(shè) B 是全部分枝數(shù)是全部分枝數(shù). 則則 n B?n = B + 1.因?yàn)樗蟹种Χ紒碜远葹橐驗(yàn)樗蟹种Χ紒碜远葹?或或2的結(jié)點(diǎn)的結(jié)點(diǎn), 所以所以 B n1 & n2 ?B = n1 + 2

18、 n2. 123 n0 = n2 + 1 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k 為為 ：2 二叉樹二叉樹編輯編輯pptppt1818 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)1. 順序順序存儲結(jié)構(gòu)存儲結(jié)構(gòu) 完全二叉樹完全二叉樹最適合這種存儲結(jié)構(gòu)。最適合這種存儲結(jié)構(gòu)。 n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的完全二叉樹的完全二叉樹的結(jié)點(diǎn)父子關(guān)系結(jié)點(diǎn)父子關(guān)系，簡單地由，簡單地由序列號序列號決定：決定：(b) 完全完全二叉樹二叉樹(a)相應(yīng)的相應(yīng)的順序順序存儲結(jié)構(gòu)存儲結(jié)構(gòu)1、非根結(jié)點(diǎn)（序號、非根結(jié)點(diǎn)（序號 i 1）的）的父結(jié)點(diǎn)父結(jié)點(diǎn)的序號是的序號是 i / 2 ;2、結(jié)點(diǎn)（序號為、結(jié)點(diǎn)（序號為 i ）的）的左

19、孩子左孩子結(jié)點(diǎn)的序號是結(jié)點(diǎn)的序號是 2i， （若（若2 i = n，否則沒有左孩子），否則沒有左孩子）;3、結(jié)點(diǎn)（序號為、結(jié)點(diǎn)（序號為 i ）的）的右孩子右孩子結(jié)點(diǎn)的序號是結(jié)點(diǎn)的序號是 2i+1， （若（若2 i +1Left ); visit ( tree-Element ); inorder ( tree-Right ); 中序中序遍歷遍歷Iterative Programvoid iter_inorder ( tree_ptr tree ) Stack S = CreateStack( MAX_SIZE ); for ( ; ; ) for ( ; tree; tree = tree-L

20、eft ) Push ( tree, S ) ; tree = Top ( S ); Pop( S ); if ( ! tree ) break; visit ( tree-Element ); tree = tree-Right; 二叉樹的遍歷二叉樹的遍歷編輯編輯pptppt編輯編輯pptpptvoid preorder ( tree_ptr tree ) if ( tree ) visit ( tree-Element ); preorder ( tree-Left ); preorder ( tree-Right ); 先序先序遍歷遍歷void postorder ( tree_ptr

21、tree ) if ( tree ) postorder ( tree-Left ); postorder ( tree-Right ); visit ( tree-Element ); 后序后序遍歷遍歷編輯編輯pptppt例例 對表達(dá)式樹進(jìn)行遍歷對表達(dá)式樹進(jìn)行遍歷: A + B C D+A DBC 中序中序遍歷遍歷 A + B C D 后序后序遍歷遍歷 A B C D + 先序先序遍歷遍歷 + A B C D編輯編輯pptppt3 查找樹查找樹ADT 二叉查找樹二叉查找樹【定義定義】二叉查找樹二叉查找樹是一棵二叉樹。可能為空，若非空，則滿足以是一棵二叉樹?？赡転榭?，若非空，則滿足以下性質(zhì)：下

22、性質(zhì)：每個(gè)結(jié)點(diǎn)有一個(gè)每個(gè)結(jié)點(diǎn)有一個(gè)整數(shù)關(guān)鍵字，整數(shù)關(guān)鍵字，且關(guān)鍵字且關(guān)鍵字互異?；ギ?。非空非空左左子樹上的結(jié)點(diǎn)關(guān)鍵字的值必須子樹上的結(jié)點(diǎn)關(guān)鍵字的值必須小于小于子樹的根結(jié)點(diǎn)的關(guān)鍵字子樹的根結(jié)點(diǎn)的關(guān)鍵字值。值。非空非空右右子樹上的結(jié)點(diǎn)關(guān)鍵字的值必須子樹上的結(jié)點(diǎn)關(guān)鍵字的值必須大于大于子樹的根結(jié)點(diǎn)的關(guān)鍵字子樹的根結(jié)點(diǎn)的關(guān)鍵字值。值。(1) 左右子樹也是二叉查找樹。左右子樹也是二叉查找樹。305240201512251022607080651. 定義定義編輯編輯pptppt3 二叉查找樹二叉查找樹2. ADT數(shù)據(jù)元素集數(shù)據(jù)元素集: 一個(gè)有一個(gè)有0個(gè)或多個(gè)元素的有窮結(jié)點(diǎn)集合。個(gè)或多個(gè)元素的有窮結(jié)點(diǎn)集合。操

23、作集操作集: SearchTree MakeEmpty( SearchTree T ); Position Find( ElementType X, SearchTree T ); Position FindMin( SearchTree T ); Position FindMax( SearchTree T ); SearchTree Insert( ElementType X, SearchTree T ); SearchTree Delete( ElementType X, SearchTree T ); ElementType Retrieve( Position P ); 編輯編輯p

24、ptppt3 二叉查找樹二叉查找樹3. 實(shí)現(xiàn)實(shí)現(xiàn) FindPosition Find( ElementType X, SearchTree T ) if ( T = NULL ) return NULL; /* not found in an empty tree */ if ( X Element ) /* if smaller than root */ return Find( X, T-Left ); /* search left subtree */ else if ( X T-Element ) /* if larger than root */ return Find( X, T-

25、Right ); /* search right subtree */ else /* if X = root */ return T; /* found */ T( N ) = S ( N ) = O( d ) d 是是X的深度的深度這個(gè)測試必須首先進(jìn)行嗎這個(gè)測試必須首先進(jìn)行嗎?它們是尾遞歸。它們是尾遞歸。如何消除？如何消除？編輯編輯pptppt3 二叉查找樹二叉查找樹Position Iter_Find( ElementType X, SearchTree T ) /* iterative version of Find */ while ( T ) if ( X = T-Element

26、) return T ; /* found */ if ( X Element ) T = T-Left ; /*move down along left path */ else T = T- Right ; /* move down along right path */ /* end while-loop */ return NULL ; /* not found */ 編輯編輯pptppt 查找最大和最小元素查找最大和最小元素 最大元素最大元素一定是在一定是在樹的樹的最右分枝的端結(jié)點(diǎn)最右分枝的端結(jié)點(diǎn)上上 最小元素最小元素一定是在樹的一定是在樹的最左分枝的端結(jié)點(diǎn)最左分枝的端結(jié)點(diǎn)上上181

27、015207229最左端點(diǎn)最左端點(diǎn)最右端點(diǎn)最右端點(diǎn)3 二叉查找樹二叉查找樹編輯編輯pptppt3 二叉查找樹二叉查找樹 FindMinPosition FindMin( SearchTree T ) if ( T = NULL ) return NULL; /* not found in an empty tree */ else if ( T-Left = NULL ) return T; /* found left most */ else return FindMin( T-Left ); /* keep moving to left */ FindMaxPosition FindMax

28、( SearchTree T ) if ( T != NULL ) while ( T-Right != NULL ) T = T-Right; /* keep moving to find right most */ return T; /* return NULL or the right most */ T( N ) = O ( d ) T( N ) = O ( d ) 編輯編輯pptppt3 二叉查找樹二叉查找樹 Insert305240算法梗概算法梗概:Insert 80 檢查檢查 80 是否已在樹中；是否已在樹中； 80 40, 所以它必定是所以它必定是40的右孩子。的右孩子。80

29、Insert 35 檢查檢查 35 是否在樹中；是否在樹中； 35 5, 所以它必定是所以它必定是5的右孩子。的右孩子。25這是我們搜索關(guān)鍵值時(shí)這是我們搜索關(guān)鍵值時(shí)遇到的最后一個(gè)結(jié)點(diǎn)。遇到的最后一個(gè)結(jié)點(diǎn)。它必定是這個(gè)新結(jié)點(diǎn)的父結(jié)點(diǎn)。它必定是這個(gè)新結(jié)點(diǎn)的父結(jié)點(diǎn)。分析分析將元素將元素X插入二叉搜索樹中，關(guān)鍵是要找到元素應(yīng)該插入插入二叉搜索樹中，關(guān)鍵是要找到元素應(yīng)該插入的的位置位置。位置的確定可以利用與查找函數(shù)。位置的確定可以利用與查找函數(shù)Find類似的方法，如果在類似的方法，如果在樹樹中找到中找到X，說明要插入的元素已存在，可放棄插入操作。如果，說明要插入的元素已存在，可放棄插入操作。如果沒沒找到

30、找到X，查找終止的位置就是，查找終止的位置就是X應(yīng)插入的位置。應(yīng)插入的位置。編輯編輯pptppt3 二叉查找樹二叉查找樹SearchTree Insert( ElementType X, SearchTree T ) if ( T = NULL ) /* Create and return a one-node tree */ T = malloc( sizeof( struct TreeNode ) ); if ( T = NULL ) FatalError( Out of space! ); else T-Element = X; T-Left = T-Right = NULL; /* E

31、nd creating a one-node tree */ else /* If there is a tree */ if ( X Element ) T-Left = Insert( X, T-Left ); else if ( X T-Element ) T-Right = Insert( X, T-Right ); /* Else X is in the tree already; well do nothing */ return T; /* Do not forget this line! */ 怎么處理重復(fù)值怎么處理重復(fù)值?T( N ) = O ( d ) 編輯編輯pptppt

32、3 二叉查找樹二叉查找樹 Delete 二叉搜索樹的刪除操作比其它操作更為復(fù)雜，有二叉搜索樹的刪除操作比其它操作更為復(fù)雜，有三種情況三種情況需要考慮：需要考慮： 要刪除的是要刪除的是葉結(jié)點(diǎn)葉結(jié)點(diǎn)可以直接刪除，然后再修改其父結(jié)點(diǎn)的指針?？梢灾苯觿h除，然后再修改其父結(jié)點(diǎn)的指針。圖圖1 二叉搜索樹葉結(jié)點(diǎn)的二叉搜索樹葉結(jié)點(diǎn)的刪除刪除301541335035要刪除結(jié)點(diǎn)要刪除結(jié)點(diǎn)例例1：刪除：刪除 35編輯編輯pptppt3636圖圖2 具有一個(gè)子樹的結(jié)點(diǎn)刪除具有一個(gè)子樹的結(jié)點(diǎn)刪除 要刪除的結(jié)點(diǎn)要刪除的結(jié)點(diǎn)只有一個(gè)孩子只有一個(gè)孩子結(jié)點(diǎn)結(jié)點(diǎn)刪除之前需要改變其刪除之前需要改變其父結(jié)點(diǎn)父結(jié)點(diǎn)的的指針，指針，指向

33、指向要刪除結(jié)點(diǎn)的要刪除結(jié)點(diǎn)的孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)。要刪除結(jié)點(diǎn)要刪除結(jié)點(diǎn)（只有一個(gè)孩子）（只有一個(gè)孩子）3015415035333015415035例例2：刪除：刪除 333 二叉查找樹二叉查找樹編輯編輯pptppt3737圖圖3 具有兩個(gè)子樹的結(jié)點(diǎn)刪除具有兩個(gè)子樹的結(jié)點(diǎn)刪除 要刪除的結(jié)點(diǎn)要刪除的結(jié)點(diǎn)有左、右兩棵子樹有左、右兩棵子樹為了保持二叉搜索樹的有序性，為了保持二叉搜索樹的有序性，替代被刪除的元素的位置可以有兩種選擇：一種是取其替代被刪除的元素的位置可以有兩種選擇：一種是取其右子樹中的最右子樹中的最小元素小元素；另一個(gè)是取其；另一個(gè)是取其左子樹中的最大元素左子樹中的最大元素。415030153

34、33534例例3：刪除：刪除 41(a) 取取右子樹右子樹中的中的最小最小元素替代元素替代41353450301533(b) 取取左子樹左子樹中的中的最大最大元素替代元素替代編輯編輯pptppt3 二叉查找樹二叉查找樹SearchTree Delete( ElementType X, SearchTree T ) Position TmpCell; if ( T = NULL ) Error( Element not found ); else if ( X Element ) /* Go left */ T-Left = Delete( X, T-Left ); else if ( X T-

35、Element ) /* Go right */ T-Right = Delete( X, T-Right ); else /* Found element to be deleted */ if ( T-Left & T-Right ) /* Two children */ /* Replace with smallest in right subtree */ TmpCell = FindMin( T-Right ); T-Element = TmpCell-Element; T-Right = Delete( T-Element, T-Right ); /* End if */

36、else /* One or zero child */ TmpCell = T; if ( T-Left = NULL ) /* Also handles 0 child */ T = T-Right; else if ( T-Right = NULL ) T = T-Left; free( TmpCell ); /* End else 1 or 0 child */ return T; T( N ) = O ( h ) h 是樹的高度。是樹的高度。編輯編輯pptppt3 二叉查找樹二叉查找樹Note: 如果刪除次數(shù)不多，那么如果刪除次數(shù)不多，那么懶惰刪除懶惰刪除是可行的：為每是可行的：為每

37、個(gè)結(jié)點(diǎn)添加一個(gè)標(biāo)識域，個(gè)結(jié)點(diǎn)添加一個(gè)標(biāo)識域，標(biāo)記標(biāo)記結(jié)點(diǎn)是可用還是已被刪除。結(jié)點(diǎn)是可用還是已被刪除。因此我們可以刪除一個(gè)結(jié)點(diǎn)而不實(shí)際地釋放結(jié)點(diǎn)空間。因此我們可以刪除一個(gè)結(jié)點(diǎn)而不實(shí)際地釋放結(jié)點(diǎn)空間。如果被刪除的結(jié)點(diǎn)重新插入，就不需要再次調(diào)用如果被刪除的結(jié)點(diǎn)重新插入，就不需要再次調(diào)用malloc了。了。當(dāng)樹中被刪除的結(jié)點(diǎn)數(shù)目當(dāng)樹中被刪除的結(jié)點(diǎn)數(shù)目和活躍結(jié)點(diǎn)的數(shù)目相當(dāng)時(shí)，和活躍結(jié)點(diǎn)的數(shù)目相當(dāng)時(shí)，操作的效率會受到很大的影響嗎？操作的效率會受到很大的影響嗎？編輯編輯pptppt3 二叉查找樹二叉查找樹4. 平均情形分析平均情形分析問題問題: 若一棵二叉查找樹中包含若一棵二叉查找樹中包含 n 個(gè)元素，這棵

38、樹有多高？個(gè)元素，這棵樹有多高？答案答案: 樹的高度依賴于插入的次序。樹的高度依賴于插入的次序。例例 給定元素給定元素 1, 2, 3, 4, 5, 6, 7. 將它們按以下順序插入將它們按以下順序插入一棵二叉查找樹：一棵二叉查找樹：4, 2, 1, 3, 6, 5, 7 和和 1, 2, 3, 4, 5, 6, 74567213h = 22314567h = 6編輯編輯pptppt3 二叉查找樹二叉查找樹【定義定義】一棵包含一棵包含 N 個(gè)結(jié)點(diǎn)的樹的個(gè)結(jié)點(diǎn)的樹的內(nèi)部路徑長內(nèi)部路徑長被定義為被定義為：0)1(, )()(1 DidNDNid( i ) 是結(jié)點(diǎn)是結(jié)點(diǎn) i 的的深度深度【定理定理】

39、 假設(shè)所有的二叉查找樹是等概率出現(xiàn)的，那么平假設(shè)所有的二叉查找樹是等概率出現(xiàn)的，那么平均的均的 D(N) (包括所有可能的輸入序列包括所有可能的輸入序列) 是是 O(N log N)。 因此任意結(jié)點(diǎn)的因此任意結(jié)點(diǎn)的期望期望深度是深度是 O(log N).證明證明: D( N ) = D( i ) + D( N i 1 ) + N 1rooti nodesN i 1 nodes+1由于所有的子樹大小是等概率的，由于所有的子樹大小是等概率的，因此因此 D( i ) 和和 D( N i 1 ) 的平均的平均值都是值都是. )(10NjDNj 1 )()(102 NjDNDNjN=p.212-213=

40、 O(N log N)編輯編輯pptppt4 AVL 樹樹目標(biāo)目標(biāo): 加速搜索（包括插入和刪除）。加速搜索（包括插入和刪除）。工具工具: 二叉查找樹二叉查找樹rootsmalllarge問題問題 : 雖然雖然 Tp = O( height ), 但是但是height最壞情況最壞情況下可能高達(dá)下可能高達(dá) O( N )。編輯編輯pptppt4 AVL 樹樹 例例不同的插入次序，將導(dǎo)致不同的不同的插入次序，將導(dǎo)致不同的深度深度和平均查找長度和平均查找長度ASL。 (a) 按一月到十二月的按一月到十二月的自然月份序列自然月份序列輸入所生成的；輸入所生成的； (b) 輸入序列為輸入序列為（July, F

41、eb, May, Mar, Aug, Jan, Apr, Jun, Oct, Sept, Nov, Dec） (c) 輸入序列則是按輸入序列則是按月份字符串月份字符串從小到大的順序排列的。從小到大的順序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept 按按ASL的定義，可以分別計(jì)算出三棵二叉搜索樹的的定義，可以分別計(jì)算出三棵二叉搜索樹的平均平均查找查找長度長度：ASL(a)=(1+22+33+43+52+61)/12 = 3.5；ASL(b)=(1+22

42、+34+45)/12 = 3.0；ASL(c)=(1+21+31+41+51+61+71+81+91+101+111+121)/12 = 6.5；編輯編輯pptppt4 AVL 樹樹【定義定義】一棵空的二叉樹是高度平衡的。如果一棵空的二叉樹是高度平衡的。如果 T 是一棵非空是一棵非空二叉樹，有二叉樹，有左子樹左子樹 TL 和右子樹和右子樹 TR, 那么那么 T 是是高度平衡的（高度平衡的（AVL樹）樹），當(dāng)且僅當(dāng)：，當(dāng)且僅當(dāng)： (1) TL 和和 TR 是高度平衡的是高度平衡的, 而且而且 (2) | hL hR | 1 ，hL 和和 hR 是是 TL 和和 TR 各自的高度各自的高度?！径x

43、定義】平衡因子平衡因子BF( node ) = hL hR 。在一棵。在一棵 AVL 樹中樹中, BF( node ) = 1, 0, 或或 1。582143778214354563217空樹的高度定義為空樹的高度定義為 1.編輯編輯pptppt4 AVL 樹樹例例1 輸入月份輸入月份MarMar0 1MayMay0NovNov0 1 2May0 1Nov0 0 2 1Mar0 00首個(gè)不平衡的首個(gè)不平衡的“發(fā)現(xiàn)者發(fā)現(xiàn)者”是是Mar（未必是根結(jié)點(diǎn)未必是根結(jié)點(diǎn)），它是調(diào)整起點(diǎn)位），它是調(diào)整起點(diǎn)位置。而置。而“麻煩結(jié)點(diǎn)麻煩結(jié)點(diǎn)”Nov 在發(fā)現(xiàn)者在發(fā)現(xiàn)者右右子樹的子樹的右邊右邊，因而叫，因而叫 RR

44、 插入插入，需要，需要RR 旋轉(zhuǎn)（右單旋）；旋轉(zhuǎn)（右單旋）；一般情況一般情況:A 1B0BLBRALRR插入插入RR旋轉(zhuǎn)旋轉(zhuǎn)A 2B 1BLBRALBLB0AALBR0A 不一定是樹的根不一定是樹的根Single rotation編輯編輯pptppt4 AVL 樹樹AugMay0 1Nov0 0 2 1Mar0 11Aug0AprApr0122LL旋轉(zhuǎn)旋轉(zhuǎn)May0 1Nov0 0 2 1Aug0 11 1Mar00Apr0一般情況一般情況:A1B0BRBLARLL插入插入A2B1BRBLARLL旋轉(zhuǎn)旋轉(zhuǎn)B0AARBLBR0 首個(gè)首個(gè)“發(fā)現(xiàn)者發(fā)現(xiàn)者”是是Mar； “麻煩結(jié)點(diǎn)麻煩結(jié)點(diǎn)”Apr 在發(fā)

45、現(xiàn)在發(fā)現(xiàn)者者左左子樹的子樹的左邊左邊，因而叫，因而叫 LL 插入；插入；編輯編輯pptppt4 AVL 樹樹May0 1Nov0 0 2 1Aug0 11 1Mar00Apr0JanJan01 12LR旋轉(zhuǎn)旋轉(zhuǎn)Mar0 1May0 1 2 1Aug0 10 1Jan00Apr0Nov0一般情況一般情況:A1B0BLARC0CRCLLR插入插入A2B 1BLARC 1CRCLORLR旋轉(zhuǎn)旋轉(zhuǎn)BLARC0A 1 or 0CRB0 or 1CLOR雙旋轉(zhuǎn)雙旋轉(zhuǎn)首個(gè)首個(gè)“發(fā)現(xiàn)者發(fā)現(xiàn)者”是是May； “麻煩結(jié)點(diǎn)麻煩結(jié)點(diǎn)”Jan在在左左子樹的子樹的右邊右邊，因而叫，因而叫 LR 插入插入；編輯編輯pptp

46、pt4 AVL 樹樹DecJulyMar0 1May0 1 2 1Aug0 11 1Jan0Apr0Nov0July0Dec0FebFeb0 11 22RL旋轉(zhuǎn)旋轉(zhuǎn)July0Dec0 1Aug0 1 2 1Jan0 10 1Feb00Apr0Mar0 1May0 1 2 1 1Nov0一般情況一般情況:A1B0BRALC0CLCRRL插入插入A 2B1BRALC 1CLCRORRL旋轉(zhuǎn)旋轉(zhuǎn)BRALC0A0 or 1CLB 1 or 0CROR編輯編輯pptppt4 AVL 樹樹July0Dec0 1Aug0 1 2 1Jan0 10 1Feb00Apr0Mar0 1May0 1 2 1 1No

47、v0JuneOctSeptJune0 1 1 12Nov0Dec0 1Aug1 2 1Feb01July 1Apr0Mar0May 1June0Jan0Oct0 1 2 1 1Oct0Dec0 1Aug1 2 1Feb01July 1Apr0Mar0Nov0June0Jan0May0Sept0 1 1 1 1Note: 有時(shí)候插入元素即便有時(shí)候插入元素即便不需要調(diào)整結(jié)構(gòu)，也可能需要重新計(jì)算不需要調(diào)整結(jié)構(gòu)，也可能需要重新計(jì)算一些平衡因子。一些平衡因子。另一個(gè)方法是為每一個(gè)結(jié)點(diǎn)保存一個(gè)另一個(gè)方法是為每一個(gè)結(jié)點(diǎn)保存一個(gè) height 信息。信息。編輯編輯pptppt4 AVL 樹樹AvlTree I

48、nsert( ElementType X, AvlTree T ) if ( T = NULL ) /* Create and return a one-node tree */ T = malloc( sizeof( struct AvlNode ) ); if ( T = NULL ) FatalError( Out of space! ); else T-Element = X; T-Height = 0; T-Left = T-Right = NULL; /* End creating a one-node tree */ elseif ( X Element ) /* handle

49、left insertion */ T-Left = Insert( X, T-Left ); if ( Height( T-Left ) - Height( T-Right ) = 2 ) /* not balanced */ if ( X Left-Element ) /* LL Rotation */T = SingleRotateWithLeft( T ); else /* LR Rotation */T = DoubleRotateWithLeft( T ); /* End left */else if( X T-Element ) /* handle right insertion

50、 */T-Right = Insert( X, T-Right ); if ( Height( T-Right ) - Height( T-Left ) = 2 ) /* not balanced */ if ( X T-Right-Element ) /* RR Rotation */T = SingleRotateWithRight( T ); else /* RL Rotation */T = DoubleRotateWithRight( T ); /* End right */ /* Else X is in the tree already; well do nothing */ T

51、-Height = Max( Height( T-Left ), Height( T-Right ) ) + 1; return T; 編輯編輯pptppt4 AVL 樹樹最后一個(gè)問題最后一個(gè)問題: 查找和插入的時(shí)間復(fù)雜性查找和插入的時(shí)間復(fù)雜性 Tp = O( h ) 其中其中 h 是二叉樹的高度，是二叉樹的高度，但是，但是， h = ?設(shè)設(shè) nh 為高度為為高度為h的平衡二叉樹的最小結(jié)點(diǎn)數(shù)的平衡二叉樹的最小結(jié)點(diǎn)數(shù). 二叉樹看起來應(yīng)該是如二叉樹看起來應(yīng)該是如下結(jié)構(gòu)形式：下結(jié)構(gòu)形式：Ah 2h 1Ah 2h 1或或 nh = nh 1 + nh 2 + 1 斐波那契序列斐波那契序列: F0 =

52、0, F1 = 1, Fi = Fi 1 + Fi 2 for i 1 nh = Fh+2 1, for h 0斐波那契序列的理論值是：斐波那契序列的理論值是：iiF 25151)(ln1251512nOhnhh 編輯編輯pptppt nh = nh 1 + nh 2 + 1設(shè)設(shè) nh 是高度為是高度為h的平衡二叉樹的的平衡二叉樹的最小結(jié)點(diǎn)數(shù)最小結(jié)點(diǎn)數(shù). h nh Fh0 1 11 2 12 4 23 7 34 12 55 20 86 33 137 54 218 88 349 nh = Fh+2 1, （對（對 h 0） 給定結(jié)點(diǎn)數(shù)為給定結(jié)點(diǎn)數(shù)為 n的的AVL樹的樹的最大高度為最大高度為O(l

53、og2n)！ )(lnnOh 1251512hhn 從而保證了從而保證了AVL樹的樹的查找時(shí)間性能為查找時(shí)間性能為O(log2n)！ 4 AVL 樹樹編輯編輯pptppt5 伸展樹伸展樹目標(biāo)目標(biāo) : 任意任意 M 次從空樹開始連續(xù)的操作最多花費(fèi)次從空樹開始連續(xù)的操作最多花費(fèi) O(M log N) 的時(shí)間。的時(shí)間。 這是否意味著每個(gè)操作只需這是否意味著每個(gè)操作只需花費(fèi)花費(fèi)O(log N) 時(shí)間時(shí)間?不，這意味著不，這意味著攤還攤還時(shí)間時(shí)間是是 O(log N). 所以單次操作可能仍需要所以單次操作可能仍需要 花費(fèi)花費(fèi) O(N) 時(shí)間時(shí)間? 那么，重點(diǎn)是什么？那么，重點(diǎn)是什么？這個(gè)界是很弱的，但效

54、果是相同的：這個(gè)界是很弱的，但效果是相同的：不存在不存在壞的壞的輸入序列。輸入序列。 但是，如果一個(gè)結(jié)點(diǎn)需要但是，如果一個(gè)結(jié)點(diǎn)需要 O(N) 時(shí)間去訪問，時(shí)間去訪問， 我們可以持續(xù)訪問它我們可以持續(xù)訪問它 M 次次, 對嗎？對嗎？ 我們當(dāng)然可以我們當(dāng)然可以 那只是意味著那只是意味著 任何時(shí)候結(jié)點(diǎn)被訪問后必須被任何時(shí)候結(jié)點(diǎn)被訪問后必須被移動移動。Idea : 一個(gè)結(jié)點(diǎn)被訪問后，它將通過一系列的一個(gè)結(jié)點(diǎn)被訪問后，它將通過一系列的AVL樹的旋轉(zhuǎn)操作被推至樹的旋轉(zhuǎn)操作被推至根根處。處。編輯編輯pptpptk5Fk4Ek3Dk2Ak1CB5 伸展樹伸展樹k5Fk4Ek3Dk2BAk1Ck5Fk4Ek2B

55、Ak1k3DCk5Fk4Ek2BAk1k3DCk4Ek5Fk2BAk1k3DC沒起作用沒起作用!編輯編輯pptppt5 伸展樹伸展樹更壞的情況更壞的情況:12213321Insert: 1, 2, 3, N321NFind: 1321NFind: 2312N Find: N321NT (N) = O ( N2 ) 編輯編輯pptppt5 伸展樹伸展樹另想辦法另想辦法 對任意非根結(jié)點(diǎn)對任意非根結(jié)點(diǎn) X , 用用 P 指代它的父結(jié)點(diǎn)，指代它的父結(jié)點(diǎn)， G 代表它的祖父結(jié)點(diǎn)代表它的祖父結(jié)點(diǎn):情況情況 1: P 是根結(jié)點(diǎn)是根結(jié)點(diǎn)旋轉(zhuǎn)旋轉(zhuǎn) X 和和 P情況情況 2: P 不是根結(jié)點(diǎn)不是根結(jié)點(diǎn)之字形之字形

56、GDPAXBCXGCDPAB雙旋轉(zhuǎn)雙旋轉(zhuǎn)一字形一字形GDPCXAB單旋轉(zhuǎn)單旋轉(zhuǎn)XAPBGDC編輯編輯pptppt5 伸展樹伸展樹k5Fk4Ek3Dk2Ak1CBk5Fk4Ek1k3DCk2BAk1k2BAk4k5FEk3DC伸展操作不僅將被訪問結(jié)點(diǎn)移到根處，伸展操作不僅將被訪問結(jié)點(diǎn)移到根處，而且整體上將路徑上大部分結(jié)點(diǎn)的深度而且整體上將路徑上大部分結(jié)點(diǎn)的深度減少了將近一半。減少了將近一半。編輯編輯pptppt5 伸展樹伸展樹Insert: 1, 2, 3, 4, 5, 6, 771654327654132Find: 176145321674532一個(gè)一個(gè)32個(gè)結(jié)點(diǎn)的例子在個(gè)結(jié)點(diǎn)的例子在圖圖 4.52 4.60編輯編輯pptppt5 伸展樹伸展樹Deletions: 步驟步驟 1: Find X ;X 將成為根。將成為根。 步驟步驟 2: Remove X ;將得到兩棵子樹將得到兩棵子樹 TL 和和 TR . 步驟步驟 3: FindMax ( TL ) ;最大的元素將成為最大的元素將成為 TL 的根的根, 而且沒有右子而且沒有右子樹。樹。 步驟步驟 4: 將將 TR 作為作為 TL 的根的右子樹的根的右子樹.伸展樹真的比伸展樹真的比 AVL 樹好嗎樹好嗎?編輯編輯pptppt 二叉查找樹的其他