数据结构与程序设计(王丽苹)30multiwaysearch.ppt

9/18/2023,数据结构与程序设计,1,数据结构与程序设计(30),王丽苹,9/18/2023,数据结构与程序设计,2,Multiway Search Trees,An m-way search tree is a tree in which,for some integer m called the order of the tree,each node has at most m children.If k=m is the number of children,then the node contains exactly k-1 keys,which partition all the keys into k subsets consisting of all the keys less than the first key in the node,all the keys between a pair of keys in the node,and all keys greater than the largest key in the node.,9/18/2023,数据结构与程序设计,3,9/18/2023,数据结构与程序设计,4,Balanced Multiway Trees(B-Trees)p536,DEFINITION A B-tree of order m is an m-way search tree in which:1.All leaves are on the same level.2.All internal nodes except the root have at most m nonempty children,and at least m/2 nonempty children.3.The number of keys in each internal node is one less than the number of its nonempty children,and these keys partition the keys in the children in the fashion of a search tree.4.The root has at most m children,but may have as few as 2 if it is not a leaf,or none if the tree consists of the root alone.,9/18/2023,数据结构与程序设计,5,B-Trees,9/18/2023,数据结构与程序设计,6,Data Structure-B_node(1)P539,template struct B_node/data members:int count;Entry dataorder-1;B_node*branchorder;/constructor:B_node();,9/18/2023,数据结构与程序设计,7,Data Structure-B_node(1)P539,Data structure of B-tree node:,Example of one 6 order B-tree node:count=4,A C E I K,9/18/2023,数据结构与程序设计,8,Discuss-B_node(2),count gives the number of Entrys in the B_node.If count is nonzero then the node has count+1 children.branch0 points to the subtree containing all Entrys with keys less than that in data0.For 1=position=count-1,branchposition points to the subtree with keys strictly between those in the subtrees pointed to by dataposition-1 and dataposition.branchcount points to the subtree with keys greater than that of datacount-1.,9/18/2023,数据结构与程序设计,9,Data Struct-B_node(3),template B_node:B_node()/data members:count=0;,9/18/2023,数据结构与程序设计,10,Method in B-tree,Search target in B-Tree.P540-541Insertion a node to B-Tree.P542-547Remove a node in B-Tree.P548-554,9/18/2023,数据结构与程序设计,11,B-tree Search Method Declaration,#includeB_node.cppenum Error_codenot_present,duplicate_error,overflow,success;template class B_tree public:/Add public methods.Error_code search_tree(Entry,9/18/2023,数据结构与程序设计,12,B-tree constructor,template B_tree:B_tree()/data members:root=NULL;,9/18/2023,数据结构与程序设计,13,B_tree Search implementation,template Error_code B_tree:search_tree(Entry,9/18/2023,数据结构与程序设计,14,How to search target Key u or h,9/18/2023,数据结构与程序设计,15,template Error_code B_tree:recursive_search_tree(B_node*current,Entry,9/18/2023,数据结构与程序设计,16,B-tree search a node,template Error_code B_tree:search_node(B_node*current,const Entry,9/18/2023,数据结构与程序设计,17,Discuss:B-tree search a node,For B-trees of large order,this function should be modified to use binary search instead of sequential search.Another possibility is to use a linked binary search tree instead of a sequential array of entries for each node.,9/18/2023,数据结构与程序设计,18,Insertion into a B-Tree,In contrast to binary search trees,B-trees are not allowed to grow at their leaves;instead,they are forced to grow at the root.General insertion method:,9/18/2023,数据结构与程序设计,19,Insertion into a B-Tree P538,1.Search the tree for the new key.This search(if the key is truly new)will terminate in failure at a leaf.2.Insert the new key into to the leaf node.If the node was not previously full,then the insertion is finished.Full node Split:3.When a key is added to a full node,then the node splits into two nodes,side by side on the same level,except that the median key is not put into either of the two new nodes.4.When a node splits,move up one level,insert the median key into this parent node,and repeat the splitting process if necessary.5.When a key is added to a full root,then the root splits in two and the median key sent upward becomes a new root.This is the only time when the B-tree grows in height.,9/18/2023,数据结构与程序设计,20,Example Growth of 5 B-tree P538,9/18/2023,数据结构与程序设计,21,Example Growth of 5 B-tree P538,9/18/2023,数据结构与程序设计,22,Example Growth of 5 B-tree P538,9/18/2023,数据结构与程序设计,23,B-tree insert method declaration,#includeB_node.cppenum Error_codenot_present,duplicate_error,overflow,success;template class B_tree public:/Add public methods.Error_code insert(const Entry,9/18/2023,数据结构与程序设计,24,B-tree insert:push down,Error_code push_down(B_node*current,const Entry The recursive function push down uses three more output parameters.current is the root of the current subtree under consideration.If*current splits to accommodate new entry,push down returns a code of oveflow,and the following come into use:The old node*current contains the left half of the entries.median gives the median record.right branch points to a new node containing the right half of the former*current.If*current is NULL.Median is the new_entry,right branch is NULL,9/18/2023,数据结构与程序设计,25,B-tree insert:push down,9/18/2023,数据结构与程序设计,26,B-tree insert method implementation p542-543,template Error_code B_tree:insert(const Entry,9/18/2023,数据结构与程序设计,27,B-tree push down method p544,template Error_code B_tree:push_down(B_node*current,const Entry,9/18/2023,数据结构与程序设计,28,B-tree push in method,template void B_tree:push_in(B_node*current,const Entry&entry,B_node*right_branch,int position),9/18/2023,数据结构与程序设计,29,B-tree push in method,template void B_tree:push_in(B_node*current,const Entry,9/18/2023,数据结构与程序设计,30,B-tree split node p546,template void B_tree:split_node(B_node*current,const Entry&extra_entry,B_node*extra_branch,int position,B_node*&right_half,Entry&median)/median entry(in neither half),9/18/2023,数据结构与程序设计,31,B-tree split node p546,template void B_tree:split_node(B_node*current,/node to be splitconst Entry,9/18/2023,数据结构与程序设计,32,B-tree Remove,(1)If the entry that is to be deleted is not in a leaf,then its immediate predecessor(or successor)under the natural order of keys is guaranteed to be in a leaf.(2)We promote the immediate predecessor(or successor)into the position occupied by the deleted entry,and delete the entry from the leaf.(3)handle the leaf been deleted an entry.如果删除一个元素后，叶子节点的元素个数=m/2;删除结束。如果删除一个元素后，叶子节点的元素个数 m/2;查看该叶子节点的左兄弟或者友兄弟节点是否有多余的元素：有则调整元素的结构即可。左右兄弟的元素如果正好是 m/2-1，则需要进行合并操作。,9/18/2023,数据结构与程序设计,33,5 B-tree Remove,9/18/2023,数据结构与程序设计,34,5 B-tree Remove,9/18/2023,数据结构与程序设计,35,B-tree Remove P550-554,#includeB_node.cppenum Error_codenot_present,duplicate_error,overflow,success;template class B_tree public:/Add public methods.Error_code remove(const Entry,9/18/2023,数据结构与程序设计,36,Main,#includeBTree.cppvoid main()B_tree mybtree;mybtree.insert(a);mybtree.insert(g);mybtree.insert(f);mybtree.insert(b);mybtree.insert(k);mybtree.insert(d);mybtree.insert(h);mybtree.insert(m);mybtree.insert(j);mybtree.insert(e);mybtree.insert(s);mybtree.insert(i);mybtree.insert(r);mybtree.insert(x);mybtree.insert(c);mybtree.insert(l);mybtree.insert(n);mybtree.insert(t);mybtree.insert(u);mybtree.insert(p);,9/18/2023,数据结构与程序设计,37,Main,char target=k;coutmybtree.search_tree(target);mybtree.remove(k);coutmybtree.search_tree(target);,9/18/2023,数据结构与程序设计,38,Result,30,9/18/2023,数据结构与程序设计,39,上机：实现BTree的操作,请实现BTree的查找和插入操作。删除操作为选作内容。,9/18/2023,数据结构与程序设计,40,homework,P555E1E2(c),