數(shù)據(jù)結(jié)構(gòu)講義查找

1、數(shù)據(jù)結(jié)構(gòu)講義查找數(shù)據(jù)結(jié)構(gòu)講義查找不使用哨兵不使用哨兵int seq_search( SSTable l, KeyType key) for (i = 0; i next) if (p-key = key) return p; return NULL; 無頭單鏈表在鏈尾設(shè)置專用的無頭單鏈表在鏈尾設(shè)置專用的“哨兵記錄，可減少比較次數(shù)哨兵記錄，可減少比較次數(shù)struct ELEM *seq_search( KeyType key) tail-key = key; for (p = head; p-key != key; p = p-next); return p = tail ? NULL : p;

2、32021/2/24性能分析n查找成功時查找成功時pASLs(n)= =(1+2+ . +n)/n=(n+1)/2n查找失敗時查找失敗時pASLf =n+1niiiCP142021/2/24p有序表p查找表中的各記錄的關(guān)鍵字的值是有序的p順序查找p不需比較到表尾，只需比較到比給定值大的記錄p折半查找二分查找p將給定值與中間的記錄進展比較p假設(shè)找到那么查找成功；p否那么：假設(shè)比中間記錄小，那么對前一半子表進展折半查找，反之對后一半子表進展折半查找p折半查找的限制p順序表p事先排好序p折半查找的性能不是查找算法的性能極限52021/2/24p查找性能分析p折半查找每次只查表的一半，其所有記錄的查找

3、途徑構(gòu)成一棵二叉樹，稱為折半查找樹或斷定樹，每次查找只走了該樹的一條分支，故平均查找長度不超過 log2n + 1int binsearch (SSTable ST, keytype key) low= 1; high = ST.length; while (low = high) mid = (low + high) / 2; if (key=ST.elemmid.key) return mid; else if ( keydata. key ) ) return ( T ) ; else if ( LT( key , T -data. key ) ) return (SearchBST (

4、 T - lchild, key ); else return (SearchBST ( T - rchild, key ); 102021/2/24例：例：122122、9999、250250、110110、300300、280280作為二叉排序樹作為二叉排序樹的結(jié)點的關(guān)鍵字值，生成二叉排序樹。的結(jié)點的關(guān)鍵字值，生成二叉排序樹。執(zhí)行查找算法，找出被插結(jié)點的父親結(jié)點執(zhí)行查找算法，找出被插結(jié)點的父親結(jié)點判斷被插結(jié)點是左判斷被插結(jié)點是左/ /右孩子。將被插結(jié)點作為葉子插入右孩子。將被插結(jié)點作為葉子插入假設(shè)二叉樹為空。那么首先單獨生成根結(jié)點。假設(shè)二叉樹為空。那么首先單獨生成根結(jié)點。注意：新插入的結(jié)點

5、總是葉子結(jié)點。注意：新插入的結(jié)點總是葉子結(jié)點。12225030011028099112021/2/24struct Node *root, *pptr; /* 全局變量 */Status SearchBst(struct Node *t, KeyType key) if (t = NULL) return FALSE; else if (key = t-key) return TRUE; else if (key key) pptr = &t-lchild; return SearchBst(t-lchild, key); else pptr = &t-rchild; retu

6、rn SearchBst(t-rchild, key); InsertBST (KeyType key) pptr = &root; if (!SearchBst(root, key) *pptr = p = malloc(sizeof(struct Node); p-key = key; p-lchild = p-rchild = NULL; 122021/2/24 最好和最糟情況折半查找/順序查找下述兩種情況下的成功的平均查找下述兩種情況下的成功的平均查找長度長度 ASLASL156070302050ASL=(1+2+2+3+3+3)/6=14/6=2.3156070302050A

7、SL=(1+2+3+4+5+6)/6=21/6=3.5平均情況下，平均情況下，log2n數(shù)量級數(shù)量級132021/2/24 1葉子結(jié)點：直接刪除，更改它的父親結(jié)點的相應(yīng)指針域為空。葉子結(jié)點：直接刪除，更改它的父親結(jié)點的相應(yīng)指針域為空。 如：刪除數(shù)據(jù)域為如：刪除數(shù)據(jù)域為 15、70 的結(jié)點。的結(jié)點。15607030205060302050142021/2/24122250300110200991052302164004505002被刪結(jié)點的左孩子為空或者右孩子為空：被刪結(jié)點的左孩子為空或者右孩子為空：如以下圖所示，刪除結(jié)點的數(shù)據(jù)域為如以下圖所示，刪除結(jié)點的數(shù)據(jù)域為 99 的結(jié)點的結(jié)點。被刪結(jié)點被

8、刪結(jié)點122250300200230216400450500110105刪除刪除99152021/2/24 (3)(3)被刪結(jié)點的左、右子樹皆不空。被刪結(jié)點的左、右子樹皆不空。維持二叉排序樹的特性不變。維持二叉排序樹的特性不變。在中序遍歷中緊靠著被刪結(jié)點的結(jié)點才可以替代被刪節(jié)點在中序遍歷中緊靠著被刪結(jié)點的結(jié)點才可以替代被刪節(jié)點做法做法1:1:左子樹中最大的結(jié)點做替身左子樹中最大的結(jié)點做替身, , 選左子樹最右結(jié)點，其右孩子必為空選左子樹最右結(jié)點，其右孩子必為空 12225030011020099105230216400450500被刪結(jié)點被刪結(jié)點替身替身替身替身1102503001052009

9、9230216400450500做法：將替身的數(shù)據(jù)域復(fù)制到被刪做法：將替身的數(shù)據(jù)域復(fù)制到被刪結(jié)點的數(shù)據(jù)域結(jié)點的數(shù)據(jù)域?qū)⒔Y(jié)點將結(jié)點110110的左孩子作為的左孩子作為 110110的父的父結(jié)點結(jié)點9999的右孩子的右孩子( (選中的結(jié)點選中的結(jié)點110110右右孩子必為空孩子必為空) )162021/2/24 12225030011020099105230216400450500被刪結(jié)點被刪結(jié)點替身替身替身替身20025030011099105230216400450500做法：將替身的數(shù)據(jù)域復(fù)制到被刪結(jié)點做法：將替身的數(shù)據(jù)域復(fù)制到被刪結(jié)點的數(shù)據(jù)域。的數(shù)據(jù)域。將結(jié)點將結(jié)點200的右孩子作為的右孩

10、子作為200的父結(jié)點的父結(jié)點250的左孩子。注意：結(jié)點的左孩子。注意：結(jié)點 200左孩子左孩子必為空必為空右子樹中最小的結(jié)點做替身。右子樹中最小的結(jié)點做替身。 選右子樹中的最左的結(jié)點，其左孩子指針必為空選右子樹中的最左的結(jié)點，其左孩子指針必為空 172021/2/24FP被刪結(jié)點被刪結(jié)點CCLPRQQLSSLFCCLPRQQLSSL做法做法2 2：刪除節(jié)點，原左子樹補上來，原右子樹做原左子：刪除節(jié)點，原左子樹補上來，原右子樹做原左子樹最右節(jié)點的右子樹樹最右節(jié)點的右子樹 ( (或?qū)ΨQ的：原右子樹補上來，原左或?qū)ΨQ的：原右子樹補上來，原左子樹做原右子樹最左節(jié)點的左子樹子樹做原右子樹最左節(jié)點的左子樹

11、) )182021/2/24全局變量struct NODE *pptr;Status DeleteBST (struct Node *t，KeyType key) if (t = NULL) / 二叉排序樹 t 中不存在關(guān)鍵字為 key 的結(jié)點 return FALSE; else if (key = t- key) DeleteNode(t); / 存在關(guān)鍵字為 key 的結(jié)點，進展刪除 else if (key key) pptr = &t-lchild; DeleteBST(t-lchild, key); else pptr = &t-rchild; DeleteBST(

12、t-rchild, key); return TRUE; 主程序： pptr = &root; DeleteBST(root,key);192021/2/24Status DeleteNode(struct Node *p)/ 在二叉排序樹中刪除地址為 p 的結(jié)點，并保持二叉排序樹的性質(zhì)不變。 if (p-rchild = NULL) *pptr = p-lchild ; else if (p-lchild = NULL) *pptr = p-rchild; else *pptr = p-lchild; for (s = p-lchild; s-rchild !=NULL; s = s

13、-rchild); s-rchild = p-rchild; free(p); 202021/2/24DABCFEG 起因：進步查找速度，防止最壞情況出現(xiàn)。如以起因：進步查找速度，防止最壞情況出現(xiàn)。如以下圖情況的出現(xiàn)。雖然完全二叉樹的樹型最好，但下圖情況的出現(xiàn)。雖然完全二叉樹的樹型最好，但構(gòu)造困難。常使用平衡樹。構(gòu)造困難。常使用平衡樹。 212021/2/24p平衡二叉樹p平衡二叉樹又稱 AVL樹(Adelson-Velskii & Landis于 1962年創(chuàng)造)，它具有如下性質(zhì)：p或者為空樹，p或者根結(jié)點的左、右子樹也均為平衡二叉樹，且左、右子樹的樹高之差的絕對值不超過1。p平衡因

14、子p結(jié)點的左子樹高度減去右子樹高度的值稱為該結(jié)點的平衡因子。p平衡二叉樹也可以這樣定義：平衡二叉樹是所有結(jié)點的平衡因子的絕對值均小于2的二叉樹。結(jié)點的平衡因子為 1、1、0222021/2/24注意：完全二叉樹必為平衡樹，平衡樹不一定是完全二叉注意：完全二叉樹必為平衡樹，平衡樹不一定是完全二叉樹。樹。141253928635360501718730+1+1-1-1-100000000是平衡樹是平衡樹不是完全二叉樹不是完全二叉樹145392863536050171830+1+2-1-100000+1不是平衡樹不是平衡樹-1232021/2/24141253928635360501718730+1

15、+1-1-1-100000000平衡樹平衡樹141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡因原平衡因子為子為 0危機結(jié)點危機結(jié)點p要求：插入之后仍保持平衡二叉樹的性質(zhì)不變在平衡樹中插入數(shù)據(jù)域為在平衡樹中插入數(shù)據(jù)域為 2 的結(jié)點的結(jié)點242021/2/24141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡因原平衡因子為子為 0危機結(jié)點危機結(jié)點插入操作解決方案：插入操作解決方案：1. 新結(jié)點插入后，找到平衡因子越軌新結(jié)點插入后，找到平衡因子越軌的結(jié)點，調(diào)整以此節(jié)點為根的子樹的結(jié)點，調(diào)整以

16、此節(jié)點為根的子樹,調(diào)調(diào)整后，子樹高度一定要保持不變能整后，子樹高度一定要保持不變能做到嗎？做到嗎？2. 不涉及到危機結(jié)點的父親結(jié)點不涉及到危機結(jié)點的父親結(jié)點3. 仍保持平衡二叉樹的性質(zhì)不變。仍保持平衡二叉樹的性質(zhì)不變。252021/2/24141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡因子為因子為 0危機結(jié)點危機結(jié)點23597122359712 右旋轉(zhuǎn)處理右旋轉(zhuǎn)處理中序序列中序序列262021/2/24141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡因子為因子為 0危機

17、結(jié)點危機結(jié)點14932528635360501718730+1+1-1-1-100000001200272021/2/24 左處理新插入結(jié)點出如今危機結(jié)點的左子樹上進展的調(diào)整的情況分析左處理新插入結(jié)點出如今危機結(jié)點的左子樹上進展的調(diào)整的情況分析(設(shè)插入前樹高設(shè)插入前樹高h)1、LL 情況：情況：LL：表示新插入結(jié)點在危機結(jié)點的左子樹的左子樹上：表示新插入結(jié)點在危機結(jié)點的左子樹的左子樹上AB+1h-10+2+1h-2h-2LL 處理處理BLBRARBA0h-10h-2h-2BLBRAR危機結(jié)點危機結(jié)點處理前：高度為處理前：高度為 h + 1 中序序列：中序序列：ABBLBRAR處理后：高度為處理

18、后：高度為 h 中序序列：中序序列：ABBLBRAR注意：處理后注意：處理后 平衡因子為平衡因子為 0AB右旋轉(zhuǎn)右旋轉(zhuǎn)A282021/2/242、LR 情況：情況：LR：表示新插入結(jié)點在危機結(jié)點的左子樹的右子樹上：表示新插入結(jié)點在危機結(jié)點的左子樹的右子樹上 情況情況A：AB+1h-20+2-1h-2LR 處理處理BLAR危機結(jié)點危機結(jié)點處理前：處理前： 高度為高度為 h + 1 中序序列：中序序列：注意：處理后注意：處理后 平衡因子為平衡因子為 0,0,-1CBCCLCRh-3h-20+1CB0h-2h-2BLARACRh-3CLh-2-10ABBLARCCLCR處理后：處理后： 高度為高度為

19、 h 中序序列：中序序列：ABBLARCCLCRA左旋轉(zhuǎn)左旋轉(zhuǎn)B然后右旋轉(zhuǎn)然后右旋轉(zhuǎn)A292021/2/24LR :新插入結(jié)點在危機結(jié)點的新插入結(jié)點在危機結(jié)點的左子樹左子樹的的右子樹上右子樹上 情況情況B：AB+1h-20+2-1h-2LR 處理處理BLAR危機結(jié)點危機結(jié)點處理前：處理前： 高度為高度為 h + 1 中序序列：中序序列：注意：處理后注意：處理后 平衡因子為平衡因子為 +1,0,0CBCCRCLh-2h-30-1CB0h-2h-2BLARACLh-2CRh-3+10ABBLARCCRCL處理后：處理后： 高度為高度為 h 中序序列：中序序列：AABBLARCCRCL左旋轉(zhuǎn)左旋轉(zhuǎn)B

20、然后右旋轉(zhuǎn)然后右旋轉(zhuǎn)A302021/2/24LR：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的左子樹左子樹的的右子樹上右子樹上 情況情況C：AB+10+2-1LR 處理處理危機結(jié)點危機結(jié)點處理前：處理前： 高度為高度為 2 中序序列：中序序列：注意：處理后注意：處理后 平衡因子為平衡因子為 0,0,0CBC0ABCA新插入結(jié)點新插入結(jié)點ABC處理后：處理后： 高度為高度為 1 中序序列：中序序列：CB0A00 四種情況的區(qū)分：如果 的平衡因子為1 則為 LL型處理；否則為 LR型處理：若 的平衡因子為1、1 、0 ；則分別為 LRA、LRB、LRC型處理BC312021/2/24右處理

21、新插入結(jié)點出如今右子樹上需進展的調(diào)整：右處理新插入結(jié)點出如今右子樹上需進展的調(diào)整：1 1、RR RR 情況：情況：RRRR：表示新插入結(jié)點在危機結(jié)點的右子樹的右子樹上：表示新插入結(jié)點在危機結(jié)點的右子樹的右子樹上 處理圖形和處理圖形和 LL LL 鏡象相似鏡象相似2 2、RL RL 情況：情況：RLRL：表示新插入結(jié)點在危機結(jié)點的右子樹的左子樹上：表示新插入結(jié)點在危機結(jié)點的右子樹的左子樹上 A A、處理圖形和、處理圖形和 LRA LRA 鏡象相似鏡象相似 B B、處理圖形和、處理圖形和 LRB LRB 鏡象相似鏡象相似 C C、處理圖形和、處理圖形和 LRC LRC 鏡象相似鏡象相似322021

22、/2/24p例：有一組關(guān)鍵字序列JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC，以此建立 AVL 樹。 JAN FEB APR AUG MAR JUN MAY JUL JAN FEB MAR APR MAY JUN JUL AUG SEP OCTLR AUG0 APR-1 FEB2 OCT0 SEP1 MAY-2332021/2/24 SEP OCT JAN FEB MAR APR MAY JUN JUL AUG NOV DEC NOV SEP OCT JAN FEB MAR APR MAY JUN JUL AUGRLRR OCT1 MAR-1

23、JAN-2342021/2/24具有具有 N N 個結(jié)點的平衡樹，高度個結(jié)點的平衡樹，高度 h h 滿足：滿足：loglog2 2(N+1) (N+1) h h log loga a(sqrt(5)(sqrt(5)* *(N+1) - 2(N+1) - 2其中：其中：a a (1(1sqrt(5)/2sqrt(5)/2查找的時間復(fù)雜度查找的時間復(fù)雜度O(logn)O(logn)352021/2/24構(gòu)造一系列結(jié)點個數(shù)最少的平衡二叉樹，構(gòu)造一系列結(jié)點個數(shù)最少的平衡二叉樹， T T1,1, T T2 ,2 , T T3 3 ,T,Th h；這種樹的高度分別為這種樹的高度分別為 1 1、2 2、3

24、3、h h。T1 高度高度 h = 1 結(jié)點個結(jié)點個 數(shù)最少數(shù)最少T2 高度高度 h = 2 結(jié)點個結(jié)點個 數(shù)最少數(shù)最少T3 高度高度 h = 3 結(jié)點個結(jié)點個 數(shù)最少數(shù)最少有有t th h = t = th-2h-2 + t + th-1h-1 + 1+ 1該數(shù)的序列為該數(shù)的序列為 1、2、4、7、12、20、33、54、88 .而而 Fibonacci 數(shù)列為：數(shù)列為：0、1、1、2、3、5、8、13、21、34、55、89所以：所以： t(h) = f(h+2) - 1；于是轉(zhuǎn)化為求于是轉(zhuǎn)化為求 Fibonacci 數(shù)的問題。數(shù)的問題。由于：由于： f(h) h h/ sqrt(5);

25、(1sqrt(5)/2.362021/2/249345121055102411892048121444096132338192143771638415610327681698765536171597131072182584262144194181524288206765211094622177112328657244636825750252612139327196418134217728283178112684354562951422953687091230832040107374182431214748364832429496729633858993459234171798691843534

26、35973836836687194767363723839M275G3963M550G40 102M 1100G41 165M2200G42 267M 4398G43 433M8796G44 701M 17592G372021/2/24struct Node ElemType data; int bf; struct Node *lchild, *rchild;#define LH +1 /* 左子樹高 */#define EH 0 /* 等高 */#define RH -1 /* 右子樹高 */382021/2/24void R_Rotate(struct Node *pp) p = *pp

27、; lc = p-lchild; p-lchild = lc-rchild; lc-rchild = p; *pp = lc;void L_Rotate(struct Node *pp) p = *pp; rc = p-rchild; p-rchild = rc-lchild; rc-lchild = p; *pp = rc;392021/2/24int InsertAVL(struct Node *pp, ElemType e)/返回值：-1未插入，0高度不變，1增高 T = *pp; if (T = NULL) / 遞歸出口 *pp = T = malloc(sizeof(struct N

28、ode); T-data = e; T-lchild = T-rchild = NULL; T-bf = EH; return 1; else if (e.key = T-Data.key) return -1; else if (e.key Data.key) .402021/2/24 else if (e.key Data.key) result = InsertAVL(&T-lchild, e); if (result != 1) return result; switch (T-bf) case LH: LeftBalance(pp); return 0; case EH: T

29、-bf = LH; return 1; case RH: T-bf = EH; return 0; else if (e.key T-Data.key) result =InsertAVL(&T-rchild, e); if (result != 1) return result; switch (T-bf) case RH: RightBalance(T); return 0; case EH: T-bf = RH; return 1; case LH: T-bf = EH; return 0; 412021/2/24void LeftBalance(struct Node *pp)

30、 a = *pp; b = a-lchild; switch (b-bf) case LH: a-bf = b-bf = EH; R_Rotate(pp); break; case RH: c = b-rchild; switch (c-bf) case LH: a-bf = RH; b-bf = EH; break; case EH: a-bf = b-bf = EH; break; case RH: a-bf = EH; b-bf = LH; break; c-bf = EH; L_Rotate(&a-lchild); R_Rotate(pp); 422021/2/24參照二叉排序

31、樹中的算法，刪除后修正平衡因子，假設(shè)平衡性被破壞，利用單一/雙重旋轉(zhuǎn)恢復(fù)。432021/2/24樹的每個結(jié)點都被著上了紅色或者黑色，結(jié)點所著的顏色被用來檢測樹的平衡性 。1972年由Rudolf Bayer創(chuàng)造的。它的平衡性要求比AVL樹梢寬松，理論證明該算法效率很高442021/2/24內(nèi)存內(nèi)存例如例如: 用二叉樹組織文件，當(dāng)文件用二叉樹組織文件，當(dāng)文件的記錄個數(shù)為的記錄個數(shù)為 100，000時，要找時，要找到給定關(guān)鍵字的記錄，需訪問外存到給定關(guān)鍵字的記錄，需訪問外存17次次log100,000,太長了！太長了！502510751535609020304055708095索索引引文文件件數(shù)數(shù)

32、據(jù)據(jù)文文件件文件頭，可常駐內(nèi)存文件頭，可常駐內(nèi)存文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上452021/2/24p B樹是一種平衡的多路查找樹，主要應(yīng)用在文件系統(tǒng)中。樹是一種平衡的多路查找樹，主要應(yīng)用在文件系統(tǒng)中。p 一棵一棵 m 階的階的B樹，或為空樹，或為滿足以下特性的樹，或為空樹，或為滿足以下特性的 m 叉樹：叉樹： p 樹中每個結(jié)點最多有樹中每個結(jié)點最多有 m 棵子樹；棵子樹；p 假設(shè)根結(jié)點不是葉子結(jié)點，那么最少有兩棵子樹；假設(shè)根結(jié)點不是葉子結(jié)點，那么最少有兩棵子樹；p 除根之外的所有非終端結(jié)點最少有除根之外的所有非終端結(jié)點最少有 m/2 棵子

33、樹；棵子樹；p 所有非終端結(jié)點包含所有非終端結(jié)點包含(n,A0,K1,A1,K2,Kn,An)信息數(shù)據(jù)；信息數(shù)據(jù)；p 其中：其中：n為結(jié)點中關(guān)鍵字個數(shù)，為結(jié)點中關(guān)鍵字個數(shù)，Ai為指向子樹的指針，為指向子樹的指針，Ki為關(guān)鍵字。為關(guān)鍵字。pA0： K1 且且 Kn 的結(jié)點的地址指在該的結(jié)點的地址指在該 B_ 樹中樹中p 注意：注意：K1 K2 . Knp所有葉子結(jié)點在同一層次上，不帶信息。所有葉子結(jié)點在同一層次上，不帶信息。462021/2/24例如：例如：m = 4 階階B樹。樹。除根結(jié)點和葉子結(jié)點之外，每個結(jié)點的孩子個數(shù)除根結(jié)點和葉子結(jié)點之外，每個結(jié)點的孩子個數(shù)至少為至少為 m/2 = 2

34、個；結(jié)點的關(guān)鍵字個數(shù)至少為個；結(jié)點的關(guān)鍵字個數(shù)至少為 1 。該該B樹的深度為樹的深度為 4。葉子結(jié)點都在第葉子結(jié)點都在第 4 層上。層上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第第 1 層層第第 2 層層第第 3 層層(L層層)第第 4 層層(L1層層)472021/2/24查找過程，類似于二叉排序樹的查找。如查找關(guān)鍵字為查找過程，類似于二叉排序樹的查找。如查找關(guān)鍵字為 KEY 的記錄。的記錄。從根從根r開場查找，假如開場查找，假如 Ki = KEY 那么查找成功，那么查找成功，Ri 為關(guān)鍵字為為關(guān)鍵字為 KEY 的記錄的地址

35、。的記錄的地址。 假設(shè)假設(shè) Ki KEY Ki+1; 在子樹在子樹 Ai 中查找中查找 假設(shè)假設(shè) KEY Kn;在子樹在子樹 An 中查找中查找 假設(shè)假設(shè) 找到葉子找到葉子(r為為NULL)，那么查找失敗。，那么查找失敗。注意：每次查找將去掉注意：每次查找將去掉 s-1/s 個分支。個分支。B樹節(jié)點定義#define m 3typedef struct BTNode int keynum; struct BTNode *parent; KeyType key1+m; /* 0號未用 *. struct BTNode *ptr1+m; Record *recptr1+m; BTNode, *BT

36、ree;482021/2/24 步驟：步驟：1、確定插入位置，將結(jié)點插入到第、確定插入位置，將結(jié)點插入到第 L 層注意：第層注意：第 L+1 層為葉子結(jié)點層為葉子結(jié)點2、找到插入位置，將關(guān)鍵字和其它信息按序插入。、找到插入位置，將關(guān)鍵字和其它信息按序插入。3、假設(shè)被插入結(jié)點的關(guān)鍵字個數(shù)、假設(shè)被插入結(jié)點的關(guān)鍵字個數(shù) m-1, 那么該結(jié)點滿。必須分裂成兩個結(jié)點。否那么，完畢。那么該結(jié)點滿。必須分裂成兩個結(jié)點。否那么，完畢。如結(jié)點原為：如結(jié)點原為： m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)插入一個關(guān)鍵字之后變?yōu)椋翰迦胍粋€關(guān)鍵字之后變?yōu)椋?m, A0, (K1

37、, A1), (K2, A2), (Km, Am)該結(jié)點將進展分裂：該結(jié)點將進展分裂： . (K m/2, p ) . m/2 -1, A0, (K1, A1), (K m/2 , Am/2 ) m- m/2 , A m/2 , (Km, Am) 生成新結(jié)點生成新結(jié)點 p, 將原結(jié)點的后半部分復(fù)制過去。假設(shè)分裂一直進展到根結(jié)點，樹可能長高一層。將原結(jié)點的后半部分復(fù)制過去。假設(shè)分裂一直進展到根結(jié)點，樹可能長高一層。PP(K m/2 , p) 數(shù)據(jù)項數(shù)據(jù)項插入上層結(jié)點之中插入上層結(jié)點之中492021/2/24 例如：例如：3 階階 B 樹的插入操作。樹的插入操作。m=3, m/2 - 1 = 1;

38、 至少至少 1 個關(guān)鍵字，二個孩子結(jié)點。個關(guān)鍵字，二個孩子結(jié)點。3，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入插入502021/2/24p 根本要求p 刪除一個關(guān)鍵字之后節(jié)點的關(guān)鍵字個數(shù)小于m/2-1，那么設(shè)法合并512021/2/24pB+樹是B樹的變形，廣泛應(yīng)用在數(shù)據(jù)庫系統(tǒng)中p一棵m階B+樹與一棵m階B樹的不同之處在于：p葉子結(jié)點包含了關(guān)鍵字的信息及指向記錄的指針，且葉子結(jié)點以關(guān)鍵字自小至大順序鏈接p非葉子節(jié)點僅僅作為索引部分使用，不含有關(guān)鍵字對應(yīng)的指針pB+樹已不是一棵真正意義上的樹型構(gòu)造了，其終端結(jié)點已連成了線性有序表p查找算法p每次查找都要從樹根到樹葉522021/2/24p鍵樹p又稱數(shù)字查找樹；p每個結(jié)點只包含組成關(guān)鍵字的字符或數(shù)字p常用存儲方式p孩子兄弟的二叉樹表示法雙鍵樹；p多重鏈表表示法Trie 樹532021/2/24p哈希表p一個有限的連續(xù)地址空間，用以包容按哈希地址存儲的記錄。p哈希函數(shù)p記錄的存儲位置與它的關(guān)鍵字