算法設(shè)計(jì)與分析-10紅黑樹(shù)

《算法設(shè)計(jì)與分析-10紅黑樹(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、算法設(shè)計(jì)與分析譚守標(biāo)安徽大學(xué)電子學(xué)院2007.9第九章紅黑樹(shù)紅黑樹(shù)的概念和性質(zhì)紅黑樹(shù)的旋轉(zhuǎn)操作（過(guò)程及分析）紅黑樹(shù)的插入操作（過(guò)程及分析）紅黑樹(shù)的刪除操作（過(guò)程及分析）程序演示及說(shuō)明二叉查找樹(shù)的概念和性質(zhì)二叉查找樹(shù)：（1）一個(gè)結(jié)點(diǎn)x的域：key，left，right和p。（2）二叉查找樹(shù)的性質(zhì)：設(shè)x為二叉查找樹(shù)中的一個(gè)結(jié)點(diǎn)。如果y是x的左子樹(shù)中的一個(gè)結(jié)點(diǎn)，則key[y]≤key[x]；如果y是x的右子樹(shù)中的一個(gè)結(jié)點(diǎn)，則key[y]≥key[x]。中序遍歷算法因?yàn)槟匙訕?shù)根的關(guān)鍵字在被印出時(shí)是介于其左子樹(shù)中的關(guān)鍵字和其右子樹(shù)中的

2、關(guān)鍵字之間，所以稱為中序遍歷算法.INORDER-TREE-WALK(x)1ifx≠NIL2thenINORDER-TREE-WALK(left[x])3printkey[x]4INORDER-TREE-WALK(right[x])中序遍歷算法見(jiàn)如下的二叉查找樹(shù):將根節(jié)點(diǎn)指針設(shè)為上面程序的參數(shù),則最終的輸出結(jié)果為有序排列的一組數(shù):235578二叉查找樹(shù)的查找算法查找關(guān)鍵字為k的節(jié)點(diǎn)：根據(jù)二叉查找樹(shù)的性質(zhì)，從根節(jié)點(diǎn)開(kāi)始查找，對(duì)碰到的每個(gè)節(jié)點(diǎn)x，比較k和key[x]，若k=key[x]，返回x；若k

3、子樹(shù)；否則繼續(xù)查找x的右子樹(shù).TREE-SEARCH(x,k)1ifx=NILork=key[x]2thenreturnx3ifk

4、找樹(shù)的查找算法給定一個(gè)二叉查找樹(shù)中的節(jié)點(diǎn),有時(shí)候要求出在中序遍歷下的前趨或后繼。節(jié)點(diǎn)的前趨：如果所有的關(guān)鍵字均不同，某節(jié)點(diǎn)x的前趨即具有小于key[x]中的關(guān)鍵字中最大者的那個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)的后繼：某節(jié)點(diǎn)x的后繼即具有大于key[x]中的關(guān)鍵字中最小者的那個(gè)節(jié)點(diǎn)。根據(jù)二叉樹(shù)的結(jié)構(gòu)我們可一不用做比較就可以找到某節(jié)點(diǎn)的前趨或后繼。下面的過(guò)程對(duì)二叉查找樹(shù)中的某節(jié)點(diǎn)x返回其后繼(如果存在的話)，或NIL(如果x有樹(shù)中最大的關(guān)鍵字的話)。節(jié)點(diǎn)的后繼TREE-SUCCESSOR(x)1ifright[x]≠NIL2thenreturnTRE

5、E-MINIMUM(right[x])3yp[x]4whiley≠NILandx=right[y]5doxy6yp[y]7returny節(jié)點(diǎn)的后繼TREE-SUCCESSOR的代碼中包含兩種情況.如果節(jié)點(diǎn)x的右子樹(shù)非空,則x的后繼即是右子樹(shù)中的最左點(diǎn),在第2行中通過(guò)調(diào)用TREE-MINIMUM(right[x])可以找到這個(gè)節(jié)點(diǎn).另一方面,如果節(jié)點(diǎn)x的右子樹(shù)為空且x有后繼y.則y是x的最低的一個(gè)祖先節(jié)點(diǎn),且y的左兒子也是x的祖先.節(jié)點(diǎn)的前趨(TREE-PREDECESSOR)：與上述方式對(duì)稱二叉查找樹(shù)的查找算法時(shí)間性能分析：

6、時(shí)間性能?如何改進(jìn)？二叉查找樹(shù)的插入和刪除操作除完成簡(jiǎn)單的插入或刪除操作外，還需要什么操作？后面結(jié)合紅黑樹(shù)操作一起介紹。一、紅黑樹(shù)的概念和性質(zhì)紅黑樹(shù)：一種“平衡的”二叉查找樹(shù)。一個(gè)結(jié)點(diǎn)的域增加一位存儲(chǔ)結(jié)點(diǎn)的color，具體可以是RED或BLACK。(1)紅黑樹(shù)的性質(zhì)：①每個(gè)結(jié)點(diǎn)或是紅的，或是黑的；②每個(gè)葉結(jié)點(diǎn)（NIL）是黑的；③如果一個(gè)結(jié)點(diǎn)是紅的，則它的兩個(gè)子女都是黑的；④從某一結(jié)點(diǎn)到達(dá)其子孫葉結(jié)點(diǎn)的每一條簡(jiǎn)單路徑上包含相同個(gè)數(shù)的黑結(jié)點(diǎn)。(2)黑高度：用bh(x)表示。從某一結(jié)點(diǎn)x出發(fā)（不包括該結(jié)點(diǎn)）到達(dá)一個(gè)葉結(jié)點(diǎn)的任意一條

7、路徑上的黑結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的黑高度。紅黑樹(shù)的黑高度定義為其根結(jié)點(diǎn)的黑高度。(3)一個(gè)引理：一個(gè)含有n個(gè)內(nèi)結(jié)點(diǎn)的紅黑樹(shù)的高度至多為2log2（n+1）。證明：先證明以結(jié)點(diǎn)x為根的子樹(shù)中至少包含2bh（x）-1個(gè)內(nèi)結(jié)點(diǎn)。用假設(shè)歸納法證明。①當(dāng)x的高度為0時(shí)，則x必為一個(gè)葉結(jié)點(diǎn)（NIL），bh(x)=0，內(nèi)結(jié)點(diǎn)個(gè)數(shù)為2bh(x)-1=20-1=0，假設(shè)成立；②當(dāng)x的高度為正值時(shí)，x是一個(gè)內(nèi)結(jié)點(diǎn)且有兩個(gè)子女(?)。每個(gè)子女根據(jù)自身顏色是紅或黑有黑高度bh(x)或bh(x)-1。根據(jù)假設(shè)，每個(gè)子女至少含內(nèi)結(jié)點(diǎn)數(shù)為2bh(x)-1-

8、1。則以x為根結(jié)點(diǎn)的子樹(shù)至少含內(nèi)結(jié)點(diǎn)為（2bh（x）-1-1）+（2bh（x）-1-1）+1=2bh（x）-1。假設(shè)成立，得證。再根據(jù)性質(zhì)③可知，高度為h的紅黑樹(shù)的黑高度至少為h/2，故有n≥2h/2-1，得h≤2log2（n+1）。引理證畢。二、紅黑樹(shù)的旋轉(zhuǎn)操作對(duì)紅黑樹(shù)進(jìn)行插入和刪除操作