数据结构与算法课件：Data Structure -Searching.PPT

1、第七章 查找v查找的概念查找的概念v静态查找表静态查找表v动态查找表动态查找表v 哈希表哈希表查找表查找表 是由同一类型的数据元素是由同一类型的数据元素(或记录或记录)构成的集合构成的集合,由于由于“集合集合”中的数据元素之中的数据元素之间存在着松散的关系，因此查找表是一种间存在着松散的关系，因此查找表是一种应用灵便的数据结构。应用灵便的数据结构。对查找表的操作对查找表的操作:查询某个查询某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；检索某个检索某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；在查找表中插入一个数据元素；在查找表中插入一个数据元素；从查找表中删

2、去某个数据元素从查找表中删去某个数据元素 查找的概念静态查找表静态查找表仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。动态查找表动态查找表在查找过程中同时插入查找表中不存在的在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，或者从查找表中删除已存在的某个数据元素数据元素,此类表为动态查找表。此类表为动态查找表。查找表的分类：查找表的分类：关键字关键字是数据元素（或记录）中某个数据项是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的（或记录）。若此关键字可以识别唯一

3、的一个记录，则称之谓一个记录，则称之谓“主关键字主关键字”。若此。若此关键字能识别若干记录，则称之谓关键字能识别若干记录，则称之谓“次关次关键字键字”。 根据给定的某个值，在查找表中确定一个其关根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查查找成功找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功查找不成功”，查找结果：给出“空记录”或“空指针”。 查找查找 如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。由于查

4、找表中的数据元素之间不存在明显的组由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。织规律，因此不便于查找。 为了提高查找的效率，为了提高查找的效率， 需要在查找表中的需要在查找表中的元素之间人为地元素之间人为地 附加某种确定的关系，换句附加某种确定的关系，换句话说，话说， 用另外一种结构来表示查找表。用另外一种结构来表示查找表。查找方法评价查找方法评价F查找速度查找速度F占用存储空间多少占用存储空间多少F算法本身复杂程度算法本身复杂程度F平均查找长度平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较为确定记录在表中的位置

5、，需和给定值进行比较的关键字的个数的期望值叫查找算法的的关键字的个数的期望值叫查找算法的平均查找平均查找长度长度个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii111抽象数据类型静态查找表的定义抽象数据类型静态查找表的定义:ADT StaticSearchTable D是具有相同特性的是具有相同特性的数据元素的集合。每数据元素的集合。每个数据元素含有类型个数据元素含有类型相同的关键字，可唯相同的关键字，可唯一标识数据元素。一标识数据元素。数据关系数据关系R：数据元素同属一个集合。：数据元素同属一个集合。9.1静静 态态 查

6、查 找找 表表数据对象数据对象D:顺序表的查找顺序表的查找typedef struct ElemType *elem; / 数据元素存储空间基址，建表时数据元素存储空间基址，建表时 按实际长度分配，按实际长度分配，0号单元留空号单元留空 int length; / 表的长度表的长度 SSTable;以顺序表表示静态查找表，则以顺序表表示静态查找表，则Search函数可函数可用顺序查找来实现。用顺序查找来实现。其顺序存储结构如下：其顺序存储结构如下：i0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找6464监视哨监视哨iiii

7、比较次数比较次数=5比较次数：比较次数：查找第查找第n个元素：个元素： 1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素： n查找第查找第i个元素：个元素： n+1-i查找失败查找失败： n+1查找过程：查找过程：从表的一端开始逐个进行记从表的一端开始逐个进行记录的关键字和给定值的比较。录的关键字和给定值的比较。例如：例如：int Search_Seq(SSTable ST, KeyType kval) / 在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为

8、该元素在表中的位置，否则为0。 ST.elem0.key = kval; / 设置设置“哨兵哨兵” for (i=ST.length; ST.elemi.key!=kval; -i); / 从后往前找从后往前找 return i; / 找不到时，找不到时，i为为0 / Search_Seq算法描述：算法描述：顺序查找性能分析顺序查找性能分析查找算法的平均查找长度查找算法的平均查找长度(Average Search Length)： 为确定记录在查找表中的位置，需和给定值为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值。进行比较的关键字个数的期望值。 niiiCPASL1其中

9、其中: n 为表长为表长Pi 为查找表中第为查找表中第i个记录的概率个记录的概率Ci为找到该记录时，曾和给定值比较过的为找到该记录时，曾和给定值比较过的关键字的个数关键字的个数11niiP顺序表查找的平均查找长度为：顺序表查找的平均查找长度为：对顺序表而言，对顺序表而言，Ci = n-i+121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+PnnPi1在等概率查找的情况下，在等概率查找的情况下， 在不等概率查找的情况下，在不等概率查找的情况下，ASLss 在在 PnPn-1P2P1时取极小值。表中记录按查找概率由小到时取极小值。表中记录按查找概率由小到

10、达重新排列达重新排列,以提高查找效率。以提高查找效率。若查找概率无法事先测定，则查找过若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置将刚刚查找到的记录直接移至表尾的位置上。上。顺序表的查找算法简单，但平均查找长顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。度较大，不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过若以有序表表示静态查找表，则查找过程可以基于程可以基于“折半折半”进行。进行。有序表的查找有序表的查找折半查找折半查找查找过程查找过程：每次将待查记录所在区间缩

11、小一半。每次将待查记录所在区间缩小一半。适用条件适用条件：采用顺序存储结构的有序表。采用顺序存储结构的有序表。1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。2.初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k=rmid.key，查找成功若krmid.key，则low=mid+13.重复上述操作，直至lowhigh时，查找失败。折半查找算法实现折半查找算法实现lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找21

12、1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例如例如 key =21 的查找过程的查找过程low 指示查找区间的下界;high 指示查找区间的上界;mid = (low+high)/2。例例key =70 的查找过程的查找过程1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7

13、 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92当下界当下

14、界low大于上界大于上界high时，则说明表中时，则说明表中没有关键字等于没有关键字等于Key的元素，查找不成功。的元素，查找不成功。int Search_Bin ( SSTable ST, KeyType kval ) low = 1; high = ST.length; / 置区间初值置区间初值 while (low = high) mid = (low + high) / 2; if （kval = ST.elemmid.key ) return mid; / 找到待查元素找到待查元素 else if ( kval 50 时，可得近似结果时，可得近似结果 1) 1(log2nASLbs可

15、见，可见，折半查找的效率比顺序查找高。折半查找的效率比顺序查找高。折半查找只能适用于有序表，并且以顺序存折半查找只能适用于有序表，并且以顺序存储结构存储。储结构存储。顺序表顺序表有序表有序表表的特性表的特性无序无序有序有序存储结构存储结构顺序顺序 或或 链式链式顺序顺序插删操作插删操作易于进行易于进行需移动元素需移动元素ASL的值的值大大小小顺序表和有序表的比较顺序表和有序表的比较索引顺序表索引顺序表在建立顺序表的同时，建立一个索引项，包括两在建立顺序表的同时，建立一个索引项，包括两项：关键字项和指针项。索引表按关键字有序，项：关键字项和指针项。索引表按关键字有序，表则为分块有序表则为分块有序

16、012345678910111213170821191431332225405261784621 040 578 10索引顺序表索引顺序表 = = 索引索引 + + 顺序表顺序表顺序表顺序表索引表索引表索引顺序查找索引顺序查找又称分块查找又称分块查找查找过程查找过程：将表分成几块，块内无序，块间有将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找序；先确定待查记录所在块，再在块内查找适用条件适用条件：分块有序表分块有序表算法实现算法实现：用数组存放待查记录用数组存放待查记录,每个数据元素至少含有每个数据元素至少含有关键字域关键字域建立索引表，每个索引表结点含有最大关键建立索引

17、表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针字域和指向本块第一个结点的指针1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38例如例如分块查找方法评价分块查找方法评价2) 1(log)2(1)(21212111) 1 (211ssnASLssnsbisjbASLsbnLLLLASLbssibjbswbwbbs：用折半查找确定所在块：用顺序查找确定所在块率相等，则：表中每个记录的查找概个记录，并设块，每块

18、含的表平均分成若将表长为均查找长度在块中查找元素的平块的平均查找长度查找索引表确定所在其中：查找方法比较查找方法比较ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构顺序存储结构顺序存储结构线性链表线性链表顺序查找顺序查找折半查找折半查找 分块查找分块查找 (n) (1) (n) (1)几种查找表的特性几种查找表的特性查找查找 插入插入 删除删除无序顺序表无序顺序表 无序线性链表无序线性链表有序顺序表有序顺序表 有序线性链表有序线性链表 (n) (n) (

19、logn) (n) (1) (1) (n) (1)从查找性能看，最好情况能达从查找性能看，最好情况能达 (logn)，此时要求表有序；此时要求表有序；从插入和删除的性能看，最好情况能达从插入和删除的性能看，最好情况能达 (1)，此时要求存储结构是链表。，此时要求存储结构是链表。结论：结论：9.2动态查找表动态查找表动态查找表的特点动态查找表的特点:表结构本身是在查找过程表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定中动态生成。若表中存在其关键字等于给定值值key的记录的记录,表明查找成功；否则插入关键表明查找成功；否则插入关键字等于字等于key的记录。的记录。9.2.1 二叉搜索

20、树（二叉搜索树（Binary Search Tree）一、基本概念一、基本概念1、定义或是空、或是具有下列性质的二叉树：每个结点有一个作为搜索依据的关键码（Key）。左子树上所有关键码小于根结点关键码。右子树上所有关键码大于根结点关键码。2、举例中序遍历结果：09，17，23，45，53，65，78，81，87，94显然是有序的，故又称二叉排序树。53658187094523177894一、基本概念一、基本概念 3、BST是基于二叉树的动态搜索结构，其删除和插入结点可能要改变树的结构。 4、BST类定义特点 类定义基于二叉链存贮表示 与一般二叉树类定义十分相似 可以继承一般二叉树类的定义 基本

21、运算Find, Insert 和 Remove 都用递归实现所以在类定义中包括私有和公用两种性质的声明二叉查找树的二叉查找树的C+类说明类说明template class BST: public Dictionaryprivate: BinTreeNode * root; Elem RefValue int nodecount; void clearhelp(BinTreeNode*); BinTreeNode* inserthelp(BinTreeNode*,const Elem&); BinTreeNode* deletemin(BinTreeNode*,BinTreeNode*& ) ;

22、 BinTreeNode* removehelp(BinTreeNode*, const Key&, BinTreeNode*&); bool findhelp(BinTreeNode*, int) const; void printhelp(BinTreeNode* ,int) const;public: BST( ) root=NULL; nodecount=0; BST()clearhelp(root); void clear()clearhelp(root); root=NULL; nodecount=0; bool insert(const Elem& e) root=inserth

23、elp(root,e); nodecount+; return true; bool remove(const Key&K, Elem& e) BinTreeNode*t=NULL; root=removehelp(root, K, t); e=t-val(); nodecount-; delete t; return true; bool removeAny(Elem& e) if(root=NULL) return false; root=deletemin(root, t); e=t-val(); delete t; nodecount-; return true; bool find(

24、counst Key& K, Elem& e) const return findhelp(root, K,e); int size()return nodecount; void print()const if(root=NULL) count“The BST is empty.n”; else printHelp(root, 0); ;二、二、BST上的搜索上的搜索1、基本方法从根开始将给定值 x 与结点值进行比较若 x 小，沿着左子树继续搜索若 x 大，沿着右子树继续搜索若与 x 等则成功返回结点地址，若为空则失败2、举例 x = 2353658187094523177894 成功，比较

25、次数为4 x = 88 失败，比较次数为4 比较次数不大于 h + 13、递归算法template bool BST:findHelp (BinNode*subroot, constKey &K,Elem&e) const if (subroot = = NULL) return false; else if (KEComp:lt(K,subroot-val() return findHelp (subroot-left(),K,e); else if (KEComp:gt(K,subroot-val() return findHelp (subroot-rightt(),K,e); else

26、 e=subroot-val(); return true; 该算法的递归调用语句都于程序的最尾，称为尾递归 返回时返回到上一层调用处的下条语句去执行 因为是最尾语句，程序结束，不必用栈保存返回地址和局部变量的值 该算法可以不用栈，采用迭代方法改写成非递归程序二、二、BST上的搜索上的搜索4、迭代算法template bool BST:findHelp (BinTreeNode*subroot, constKey &K,Elem&e) if (subroot != NULL) BinTreeNode * temp = subroot; while (temp != NULL) if (KECo

27、mp:eq(K, temp-val() e=temp-val(); return true; if (KEComp:gt(K, temp-val() temp = temp -left();else temp = temp - leftChild; return false; 一般对尾递归或单向递归的情形，都可利用迭代方法，不使用栈将递归过程改为非递归过程二、二、BST上的搜索上的搜索三、三、BST中的插入中的插入1、方法先搜索BST中有无该结点，只有无才插入插入是作为叶子插入，插入后仍满足BST插入位置应是搜索操作停止（指针ptr为空）的地方2、算法template bool BST: in

28、serthelp(BinTreeNode*subroot,const Elem& e) if (subroot = = NULL) subroot = new BinTreeNode (e,NULL,NULL); return true; else if (EEComp:lt(e,subroot-val() inserthelp (subroot-left(),e); else if EEComp:gt(e,subroot-val() inserthelp(subroot-right(),e); else cout Node existed; return false; 3、建BST 逐次输入

29、关键码序列建一棵BST，是从空开始逐步插入结点 每次从根开始搜索插入位置，然后将新结点作为叶子插入 关键码集合相同但输入序列不同得到的BST也不同若输入次序：81, 65, 78, 94, 87, 88, 23, 45 , 09, 17, 538187172378096594455388三、三、BST中的插入中的插入四、四、BST中的结点删除中的结点删除1、原则删除结点所断开的链要重新接起来删除链接后仍是BST重新链接后树的高度不增加2、方法 被删结点为叶子，只需将双亲结点的相应指针置为空 被删结点无右子树，拿左孩子结点顶替它的位置 被删结点无左子树，拿右孩子结点顶替它的位置 被删结点左右子树

30、都有，在右子树中找中序遍历第一个结点，用它的值填补到被删结点，然后再来删这个结点 结点删除是一个递归的过程3、有左右子树的结点删除举例 删除关键码78的结点 右子树中序第一结点是8181复盖7881结点无左子树，用右孩 子88顶替5365819409452317788881四、四、BST中的结点删除中的结点删除8188template BinTreeNode* BST:deletemin(BinTreeNode*subroot,BinTreeNode*&min)if(subroot-left()=NULL) min=subroot; return subroot-right();else su

31、broot-SetLeft(deletemin(subroot-left(),min) template BinTreeNode* BST: removehelp(BinTreeNode*subroot, constKey&K,BinTreeNode*&t) if(subroot=NULL)return NULL;else if(KEComp:lt(K,subroot-val() subroot-setLeft(removehelp(subroot-left(),K,t); else if(KEComp:gt(K,subroot-val() subroot-setRight(removehel

32、p(subroot-right(),K,t);else BinTreeNode*temp; t=subroot; if(subroot-left()=NULL) subroot=subroot-right(); else if(subroot-right()=NULL)subroot=subroot-left(); else subroot-setRight(deletemin(subroot-right(),temp); Elem te=subroo-val(); subroot-setVal(temp-val(); temp-setVal(te); t=temp return subroo

33、t;二叉排序树查找性能的分析二叉排序树查找性能的分析 对于每一棵特定的二叉排序树，均可按照对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的平均查找长度的定义来求它的 ASL 值，显然，值，显然，由值相同的由值相同的 n 个关键字，构造所得的不同形态个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长的各棵二叉排序树的平均查找长 度的值不同，度的值不同，甚至可能差别很大。甚至可能差别很大。由关键字序列由关键字序列 3，1，2，5，4构造构造而得的二叉排序树而得的二叉排序树由关键字序列由关键字序列 1，2，3，4，5构构造而得的二叉排序树，造而得的二叉排序树，例如：例如：2134

34、535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 下面讨论平均情况下面讨论平均情况: 不失一般性，假设长度为不失一般性，假设长度为 n 的序列中有的序列中有 k 个个关键字小于第一个关键字，则必有关键字小于第一个关键字，则必有 n-k-1 个关键个关键字大于第一个关键字字大于第一个关键字,由它构造的二叉排序树由它构造的二叉排序树n-k-1k的平均查找长度是的平均查找长度是 n 和和 k 的函数的函数P(n, k) ( 0 k n-1 ) 假设假设 n 个关键字可能出现的个关键字可能出现的 n! 种排列的可种排列的可能性相同，则含能性相

35、同，则含 n 个关键字的二叉排序树的个关键字的二叉排序树的平均查找长度平均查找长度10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在等概率查找的情况下，在等概率查找的情况下，RiLirootniiCCCnCnknP11),(1)1)1()(1()1)(11knPknkPkn)1()1()(11knPknkPkn由此由此可类似于解差分方程，此递归方程有解：可类似于解差分方程，此递归方程有解：CnnnnPlog12)(10) 1() 1()(111)(nkknPknkPknnnP112)(21nkkPkn AVL树树一、一、AVL树（高度平衡的树（高度平衡的BST）概

36、念）概念 1、定义AVL或是空树，或是具有下列性质的BST：它的左、右子树都是AVL树，且左右子树的高度之差的绝对值不超过1。2、举例 是二叉搜索树 树和所有子树的左右子树高度之差绝对值不超过1 属AVL树1115142639718161000000013、平衡因子（balance factor） 结点右子树高度减去左子树高度所得高度差 AVL树中所有结点的平衡因子只能取0，1，1 AVL树的ASL可保持在O(log2n)二、平衡化旋转二、平衡化旋转 1、向AVL树插入结点可能造成不平衡，此时要调整树的结构使之重新达到平衡 2、平衡化旋转方法 从插入位置沿通向根的路径回溯检查各结点的平衡因子

37、若发现不平衡结点，则从该结点起沿刚才回溯路径取直接下两层结点 若三个结点在一条直线上，则采用单旋转进行平衡化；若三结点在一条折线上，则采用双旋转进行平衡化3、平衡化旋转示例左单旋转hhhABCDE01(a)AVL树hhh+1ABCDE12(b)E子树中插入结点hhh+1ABCDE00(c)左向旋转后的AVL树二、平衡化旋转二、平衡化旋转右单旋转hhhABCDE0- 1(a)AVL树hhh+1ABCDE- 1- 2(b)D子树中插入结点hhh+1ABCDE00(c) 右向旋转后的AVL树3、平衡化旋转示例二、平衡化旋转二、平衡化旋转先左后右双旋转hhh-1hABCDEFG插入(a)F子树插入结点

38、高度变为h- 21- 1hhh-1hABCDEFG(b)绕E，将B逆时针转后hhh-1hABCDEFG(c)绕E，将A顺时针转后03、平衡化旋转示例二、平衡化旋转二、平衡化旋转先右后左旋转hhh-1hABCDEFG插入(a)G子树插入结点高度变为h21- 1hhh-1hABCDEFG(b)绕D，C顺时针转之后hhh-1hABCDEFG(c)绕D，A逆时针转之后03、平衡化旋转示例二、平衡化旋转二、平衡化旋转三、三、AVL树的建立树的建立 对于一组关键码的输入序列，从空开始不断插入结点，最后构成AVL树 每插入一个结点后就应判断从该结点到根的路径上有无结点发生不平衡 如有不平衡问题，利用旋转方法

39、进行树的调整，使之平衡化 建AVL树过程是不断插入结点和必要时进行平衡化的过程9.2.2 B9.2.2 B树和树和B+B+树树B-树及其查找 B-树是一种平衡的多路查找树，它在文件系统中很有用。 Definition of a B-treenA B-tree of order m is an m-way tree (i.e., a tree where each node may have up to m children) in which:1.the number of keys in each non-leaf node is one less than the number of it

40、s children and these keys partition the keys in the children in the fashion of a search tree2.all leaves are on the same level3.all non-leaf nodes except the root have at least m / 2 children4.the root is either a leaf node, or it has from two to m children5.a leaf node contains no more than m 1 key

41、snThe number m should always be oddAn example B-Tree5162426122655607064904512478131518252729464853A B-tree of order 5 containing 26 itemsnSuppose we start with an empty B-tree and keys arrive in the following order:1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45nWe want to construct a B-tree o

42、f order 5nThe first four items go into the root:nTo put the fifth item in the root would violate condition 5nTherefore, when 25 arrives, pick the middle key to make a new rootConstructing a B-tree12812Constructing a B-tree (contd.)12812256, 14, 28 get added to the leaf nodes:128121462528Constructing

43、 a B-tree (contd.)Adding 17 to the right leaf node would over-fill it, so we take the middle key, promote it (to the root) and split the leaf817121425281267, 52, 16, 48 get added to the leaf nodes817121425281261648527Constructing a B-tree (contd.)Adding 68 causes us to split the right most leaf, pro

44、moting 48 to the root, and adding 3 causes us to split the left most leaf, promoting 3 to the root; 26, 29, 53, 55 then go into the leaves38174852535568252628291267121416Adding 45 causes a split of 25262829and promoting 28 to the root then causes the root to splitConstructing a B-tree (contd.)173828

45、4812671214165253556825262945Inserting into a B-TreenAttempt to insert the new key into a leafnIf this would result in that leaf becoming too big, split the leaf into two, promoting the middle key to the leafs parentnIf this would result in the parent becoming too big, split the parent into two, prom

46、oting the middle keynThis strategy might have to be repeated all the way to the topnIf necessary, the root is split in two and the middle key is promoted to a new root, making the tree one level higherExercise in Inserting a B-Tree nInsert the following keys to a 5-way B-tree:n3, 7, 9, 23, 45, 1, 5,

47、 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56nCheck your approach with a neighbour and discuss any differences.Removal from a B-treenDuring insertion, the key always goes into a leaf. For deletion we wish to remove from a leaf. There are three possible ways we can do this:n1 - If the key is already in a

48、 leaf node, and removing it doesnt cause that leaf node to have too few keys, then simply remove the key to be deleted.n2 - If the key is not in a leaf then it is guaranteed (by the nature of a B-tree) that its predecessor or successor will be in a leaf - in this case can we delete the key and promo

49、te the predecessor or successor key to the non-leaf deleted keys position.Removal from a B-tree (2)nIf (1) or (2) lead to a leaf node containing less than the minimum number of keys then we have to look at the siblings immediately adjacent to the leaf in question: u3: if one of them has more than th

50、e min number of keys then we can promote one of its keys to the parent and take the parent key into our lacking leaf u4: if neither of them has more than the min number of keys then the lacking leaf and one of its neighbours can be combined with their shared parent (the opposite of promoting a key)