查找技術(shù)ppt課件(編輯修改稿)
2024-11-30 23:08 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的二叉排序樹(shù)開(kāi)始，依次插入一個(gè)個(gè)結(jié)點(diǎn) 。 例：關(guān)鍵碼集合為 {63， 90， 70， 55， 58}， 二 叉排序樹(shù)的構(gòu)造過(guò)程為： 樹(shù)表的查找技術(shù) 63 55 90 58 70 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) ? 一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列 。 ? 每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn) 。 ? 找到插入位置后，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針； ? 在左子樹(shù) /右子樹(shù)的查找過(guò)程與在整棵樹(shù)上查找過(guò)程相同； ? 新插入的結(jié)點(diǎn)沒(méi)有破壞原有結(jié)點(diǎn)之間的關(guān)系。 小 結(jié)： 樹(shù)表的查找技術(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 二叉排序樹(shù)的刪除 在二叉排序樹(shù)上刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性。 分三種情況討論： ?被刪除的結(jié)點(diǎn)是葉子； ?被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)； ?被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù) 。 樹(shù)表的查找技術(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 情況 1—— 被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn) 樹(shù)表的查找技術(shù) 50 30 20 80 90 85 88 40 35 32 50 30 20 80 90 85 40 35 32 操作： 將雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為空。 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 情況 2—— 被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù) 操作： 將雙親結(jié)點(diǎn)的相應(yīng)指針域的值指向被刪除結(jié)點(diǎn)的左子樹(shù)（或右子樹(shù)）。 樹(shù)表的查找技術(shù) 50 30 20 80 90 85 88 40 35 32 50 30 20 90 85 88 40 35 32 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 情況 3—— 被刪除的結(jié)點(diǎn)既有左子樹(shù)也有右子樹(shù) 操作： 以其左子樹(shù)中的最大值替代之。 樹(shù)表的查找技術(shù) 50 30 20 80 90 85 88 40 35 32 40 30 20 80 90 85 88 35 32 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：在二叉排序樹(shù)中查找關(guān)鍵字值為 35， 95的過(guò)程： 樹(shù)表的查找技術(shù) 50 30 20 80 90 85 88 40 35 32 二叉排序樹(shù)的查找 50 30 20 80 90 85 88 40 35 32 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 平衡二叉樹(shù)： 或者是一棵空的二叉排序樹(shù)，或者是具有下列性質(zhì)的二叉排序樹(shù)： ⑴ 根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度最多相差 1。 ⑵ 根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。 平衡因子： 結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)的左子樹(shù)的深度與右子樹(shù)的深度之差。 平衡二叉樹(shù) 樹(shù)表的查找技術(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 5 4 8 2 5 4 8 2 1 是平衡樹(shù) 非平衡樹(shù) 散列表的查找技術(shù) 平衡二叉樹(shù) 在平衡樹(shù)中，結(jié)點(diǎn)的平衡因子可以是 1， 0， 1。 結(jié)點(diǎn)的平衡因子＝ HLHR 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 最小不平衡子樹(shù)： 在平衡二叉樹(shù)的構(gòu)造過(guò)程中， 以距離 插入結(jié)點(diǎn) 最近的、且平衡因子的絕對(duì)值大于 1的結(jié)點(diǎn)為 根 的子樹(shù)。 樹(shù)表的查找技術(shù) 5 4 2 8 1 平衡二叉樹(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 基本思想 ：在構(gòu)造二叉排序樹(shù)的過(guò)程中，每插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹(shù)的平衡性，若是，則找出最小不平衡子樹(shù)，在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹(shù)。 樹(shù)表的查找技術(shù) 平衡二叉樹(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：設(shè)序列 {20， 35， 40， 15， 30， 25} ，構(gòu)造平衡樹(shù)。 20 35 40 樹(shù)表的查找技術(shù) 35 20 40 15 30 15 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：設(shè)序列 {20， 35， 40， 15， 30， 25} ，構(gòu)造平衡樹(shù)。 樹(shù)表的查找技術(shù) 35 20 40 15 30 25 20 25 15 35 40 30 35 40 30 20 25 15 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 設(shè)結(jié)點(diǎn) A為 最小不平衡子樹(shù) 的根結(jié)點(diǎn)，對(duì)該子樹(shù)進(jìn)行平衡調(diào)整歸納起來(lái)有以下四種情況： 1. LL型 2. RR型 3. LR型 4. RL型 樹(shù)表的查找技術(shù) 平衡二叉樹(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 插入前 插入后 ， 調(diào)整前 調(diào)整后 樹(shù)表的查找技術(shù) 平衡二叉樹(shù) —— LL型 A 1 BL h BR h 0 AR h B h 2 BL h BR h 1 AR A B X h+1 BL h AR BR h 0 0 B A X 旋轉(zhuǎn)：扁擔(dān)原理；沖突：旋轉(zhuǎn)優(yōu)先 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 6 1→2 例 :LL型 樹(shù)表的查找技術(shù) 10 8 7 9 12 9 10 12 8 7 6 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 平衡二叉樹(shù) —— RR型 樹(shù)表的查找技術(shù) 插入前 插入后 ， 調(diào)整前 調(diào)整后 A 1 BL h BR h 0 AL h B X A 2 BL h BR h 0 AL h B B AL h BL h 0 BR h+1 A X 0 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 插入后 ， 調(diào)整前 先順時(shí)針旋轉(zhuǎn) 再逆時(shí)針旋轉(zhuǎn) 樹(shù)表的查找技術(shù) 平衡二叉樹(shù) —— LR型 A 2 CL h1 BL h 1 AR h B C CR h1 X X A CL h1 C B CR h
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1