资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构与程序设计,*,数据结构与程序设计(30),王丽苹,10/15/2024,1,数据结构与程序设计,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.,10/15/2024,2,数据结构与程序设计,10/15/2024,3,数据结构与程序设计,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.,10/15/2024,4,数据结构与程序设计,B-Trees,10/15/2024,5,数据结构与程序设计,Data Structure-B_node(1)P539,template,struct B_node,/data members:,int count;,Entry dataorder-1;,B_node*branchorder;,/constructor:,B_node();,;,10/15/2024,6,数据结构与程序设计,Data Structure-B_node(1)P539,Data1,Data2,Data3,Data4,Data5,B_node*,B_node*,B_node*,B_node*,B_node*,B_node*,Data structure of B-tree node:,Example of one 6 order B-tree node:count=4,B,D,H,J,NULL,A C E I K,10/15/2024,7,数据结构与程序设计,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=positionbranchposition,target);,else,target=current-dataposition;,return result;,10/15/2024,15,数据结构与程序设计,B-tree search a node,template,Error_code B_tree:search_node(,B_node*current,const Entry&target,int&position),/*Pre:current points to a node of a B tree.,Post:If the Key of target is found in*current,then a code of success is returned,the parameter position is set to the index of target,and the corresponding,Entry is copied to target.Otherwise,a code of not present is returned,and position is set to the branch index on which to continue the search.,Uses:Methods of class Entry.*/,position=0;,while(position count&target current-dataposition),position+;/Perform a sequential search through the keys.,if(position count&target=current-dataposition),return success;,else,return not_present;,10/15/2024,16,数据结构与程序设计,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.,10/15/2024,17,数据结构与程序设计,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:,10/15/2024,18,数据结构与程序设计,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.,10/15/2024,19,数据结构与程序设计,Example Growth of 5 B-tree P538,10/15/2024,20,数据结构与程序设计,Example Growth of 5 B-tree P538,10/15/2024,21,数据结构与程序设计,Example Growth of 5 B-tree P538,10/15/2024,22,数据结构与程序设计,B-tree insert method declaration,#includeB_node.cpp,enum Error_codenot_present,duplicate_error,overflow,success;,template,class B_tree,public:/Add public methods.,Error_code insert(const Entry,private:/data members,B_node*root;,Error_code push_down(,B_node*current,const Entry&new_entry,Entry,void push_in(B_node*current,const Entry,void split_node(B_node*current,/node to be split,const Entry&extra_entry,B_node*extra_branch,int position,/index in node whereextra entry goes,B_node*,/new node for right half of entries,;,10/15/2024,23,数据结构与程序设计,B-tree insert:push down,Error_code push_down(,B_node*current,const Entry&new_entry,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 poin
展开阅读全文