算法設計與分析-10紅黑樹課件.ppt

《算法設計與分析-10紅黑樹課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、算法設計與分析譚守標安徽大學電子學院2007.9第九章紅黑樹紅黑樹的概念和性質紅黑樹的旋轉操作（過程及分析）紅黑樹的插入操作（過程及分析）紅黑樹的刪除操作（過程及分析）程序演示及說明二叉查找樹的概念和性質二叉查找樹：（1）一個結點x的域：key，left，right和p。（2）二叉查找樹的性質：設x為二叉查找樹中的一個結點。如果y是x的左子樹中的一個結點，則key[y]≤key[x]；如果y是x的右子樹中的一個結點，則key[y]≥key[x]。中序遍歷算法因為某子樹根的關鍵字在被印出時是介于其

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

3、k=key[x]，返回x；若k

4、left[x]3returnx最大元素(TREE-MAXIMUM)：和上述算法對稱。二叉查找樹的查找算法給定一個二叉查找樹中的節(jié)點,有時候要求出在中序遍歷下的前趨或后繼。節(jié)點的前趨：如果所有的關鍵字均不同，某節(jié)點x的前趨即具有小于key[x]中的關鍵字中最大者的那個節(jié)點。節(jié)點的后繼：某節(jié)點x的后繼即具有大于key[x]中的關鍵字中最小者的那個節(jié)點。根據(jù)二叉樹的結構我們可一不用做比較就可以找到某節(jié)點的前趨或后繼。下面的過程對二叉查找樹中的某節(jié)點x返回其后繼(如果存在的話)，或NIL(如果x有樹中最

5、大的關鍵字的話)。節(jié)點的后繼TREE-SUCCESSOR(x)1ifright[x]≠NIL2thenreturnTREE-MINIMUM(right[x])3yp[x]4whiley≠NILandx=right[y]5doxy6yp[y]7returny節(jié)點的后繼TREE-SUCCESSOR的代碼中包含兩種情況.如果節(jié)點x的右子樹非空,則x的后繼即是右子樹中的最左點,在第2行中通過調用TREE-MINIMUM(right[x])可以找到這個節(jié)點.另一方面,如果節(jié)點x的右子樹為空且x有后繼y.則

6、y是x的最低的一個祖先節(jié)點,且y的左兒子也是x的祖先.節(jié)點的前趨(TREE-PREDECESSOR)：與上述方式對稱二叉查找樹的查找算法時間性能分析：時間性能?如何改進？二叉查找樹的插入和刪除操作除完成簡單的插入或刪除操作外，還需要什么操作？后面結合紅黑樹操作一起介紹。一、紅黑樹的概念和性質紅黑樹：一種“平衡的”二叉查找樹。一個結點的域增加一位存儲結點的color，具體可以是RED或BLACK。(1)紅黑樹的性質：①每個結點或是紅的，或是黑的；②每個葉結點（NIL）是黑的；③如果一個結點是紅的，

7、則它的兩個子女都是黑的；④從某一結點到達其子孫葉結點的每一條簡單路徑上包含相同個數(shù)的黑結點。(2)黑高度：用bh(x)表示。從某一結點x出發(fā)（不包括該結點）到達一個葉結點的任意一條路徑上的黑結點的個數(shù)稱為該結點的黑高度。紅黑樹的黑高度定義為其根結點的黑高度。(3)一個引理：一個含有n個內結點的紅黑樹的高度至多為2log2（n+1）。證明：先證明以結點x為根的子樹中至少包含2bh（x）-1個內結點。用假設歸納法證明。①當x的高度為0時，則x必為一個葉結點（NIL），bh(x)=0，內結點個數(shù)為2b

8、h(x)-1=20-1=0，假設成立；②當x的高度為正值時，x是一個內結點且有兩個子女(?)。每個子女根據(jù)自身顏色是紅或黑有黑高度bh(x)或bh(x)-1。根據(jù)假設，每個子女至少含內結點數(shù)為2bh(x)-1-1。則以x為根結點的子樹至少含內結點為（2bh（x）-1-1）+（2bh（x）-1-1）+1=2bh（x）-1。假設成立，得證。再根據(jù)性質③可知，高度為h的紅黑樹的黑高度至少為h/2，故有n≥2h/2-1，得h≤2log2（n+1）。引理證畢。二、紅黑樹的旋轉操作對紅黑樹進行插入和刪除操作