數(shù)據(jù)結(jié)構(gòu)之查找課件(編輯修改稿)
2024-09-14 09:41 本頁面
【文章內(nèi)容簡介】 return (search (bright,k))。 } } 非遞歸算法 btree treesearch (BSTree *b, int k) { BSTree *p。 p=b。 while(p!=NULL)。 { if (pdata==k) return (p)。 else if (kpdata) p=pleft。 else p=pright。 } return (NULL)。 } 二叉排序樹查找分析 ?樹型查找最壞情況時(shí)，需要的查找時(shí)間取決于樹的高度，當(dāng)二叉排序樹接近滿二叉樹時(shí)，其高度為 log2n，最壞情況下查找時(shí)間為 O(log n)，與二分查找是同樣數(shù)量級(jí)的；當(dāng)二叉排序樹為只有一個(gè)端結(jié)點(diǎn)的所謂“退化樹”時(shí)，其高度等于 n，最壞情況下查找時(shí)間為 O(n)，與順序查找屬于同一數(shù)量級(jí)。 ?為了保證樹型查找有較高的查找速度，我們希望該二叉樹接近滿二叉樹，也就是希望二叉樹的每一個(gè)結(jié)點(diǎn)的左、右子樹高度盡量接近平衡，即使按任意次序不斷地插入結(jié)點(diǎn)，也不要使此樹成為退化樹。 圖 兩個(gè)二叉排序樹 45 24 53 12 37 100 12 45 24 100 53 37 在二叉排序樹上插入結(jié)點(diǎn) 基本思想 插入結(jié)點(diǎn)的非遞歸算法 Void insertbst(BSTree *tptr,*s) /*tptr指向根 {…… /*s 指向要插入的結(jié)點(diǎn) slchild=srchild=null。 If (tptr==null) { tptr=s。 return。 } else { p=tptr。 While(p!=null) { if (pkey==skey) return。 /*無需插入 q=p。 /*q記錄 p的父親 if (skey pkey) /*尋找要插入的位置 p=plchild。 else p=prchild。 } If ( skeyqkey) /*至此 ,q指向的是 qlchild=s。 /*要插入結(jié)點(diǎn) s的父 else qrchild=s。 /*結(jié)點(diǎn) } } 在二叉排序樹上刪除結(jié)點(diǎn) 在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)后，要使剩余的結(jié)點(diǎn)仍為二叉排序樹。 設(shè)被刪除的結(jié)點(diǎn)為 P, 且 P為 F的左兒子（若為右兒子時(shí)，道理相同）。 1. P無兒子 刪除 P, 修改有關(guān)指針 flchild=null 2. P只有一個(gè)兒子 設(shè) P只有左兒子 Pl(或右兒子 Pr), 只要令 Pl （或 Pr ）成為 F的左兒子即可。 Flchild=plchild 或 Flchild=prchild 3. P有兩個(gè)兒子時(shí)，有兩種方法。設(shè) P的前驅(qū)為 S. （ 1）令 P的左子樹成為 F的左子樹， P的右子樹成為 S的右子樹。 Flchild=plchild。 r=prchild。 /*r為臨時(shí)變量 S=flchild。 While(srchild != null) s=srchild。 S=r。 /*使 P的右子樹成為 S的右子樹 ?（ 2）使 P的前驅(qū) S代替 P,然后刪除 S. 若 S有左兒子，則用 S的左兒子代替 S的位置。 設(shè) Q為 S的父親。 q=p。 S=plchild。 While(srchild != null) { q=s。 S=srchild。 /*找 P左子樹最右下方的結(jié)點(diǎn) S } Pkey=skey。 If (q!=p) qrchild=slchild。 Else qlchild=slchild。 /*當(dāng) Q=P時(shí)， S即為 P的左兒子，此時(shí)把 S的左兒子作為 P的左兒子 平衡樹 ?平衡樹 (Balanced tree)也稱為 AVL樹，是由阿德爾森 — 維爾斯基和蘭迪斯 (Adelsonvelskii and landis)于 1962年首先提出的。 ?這是一種附加了一定限制條件的二叉樹。我們定義二叉樹中每一結(jié)點(diǎn)的左子樹高度減右子樹高度為該結(jié)點(diǎn)的平衡因子（ Balance factor），所謂平衡樹，是指一個(gè)二叉樹其任一結(jié)點(diǎn)的平衡因子值只能是 +1， 0或 1，即任一結(jié)點(diǎn)的左、右子樹高度之差不超過 1。 ?如圖 ，圖中數(shù)字為該結(jié)點(diǎn)的平衡因子。 平衡樹 ?平衡二叉樹 1 1 1 1 0 0 0 1 2 0 0 1 0 ?不平衡二叉樹 ?假設(shè)給平衡樹某個(gè)結(jié)點(diǎn)的左子樹插入一個(gè)新結(jié)點(diǎn)，且此新結(jié)點(diǎn)使左子樹的高度加 1，我們可能會(huì)遇到以下三種情況： (1) 如果原來其左子樹高度 hl與右子樹高度 hr相等 ，即原來此結(jié)點(diǎn)的平衡因子等于 0,插入新結(jié)點(diǎn)后將
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1