7/26/2024数据结构与程序设计1Multiway Search TreesnAn 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.nIf 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.7/26/2024数据结构与程序设计27/26/2024数据结构与程序设计3Balanced Multiway Trees (B-Trees) p536nDEFINITION A B-tree of order m is an m-way search tree in which:n1. All leaves are on the same level.n2. All internal nodes except the root have at most m nonempty children, and at least m/2 nonempty children.n3. 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.n4. 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.7/26/2024数据结构与程序设计4B-Trees7/26/2024数据结构与程序设计5Data Structure - B_node(1) P539ntemplate nstruct B_node n/ data members:nint count;nEntry dataorder-1;nB_node *branchorder;n/ constructor:nB_node( );n;7/26/2024数据结构与程序设计6Data Structure - B_node(1) P539Data1Data2Data3Data4Data5B_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=4BDHJNULLA C E I K7/26/2024数据结构与程序设计7Discuss - B_node(2)ncount gives the number of Entrys in the B_node.nIf count is nonzero then the node has count+1 children.nbranch0 points to the subtree containing all Entrys with keys less than that in data0.nFor 1=position=count - 1, branchposition points to the subtree with keys strictly between those in the subtrees pointed to by dataposition - 1 and dataposition.nbranchcount points to the subtree with keys greater than that of datacount - 1.7/26/2024数据结构与程序设计8Data Struct - B_node(3)ntemplate nB_node: B_node()n/ data members:ncount=0;n7/26/2024数据结构与程序设计9Method in B-tree nSearch target in B-Tree. P540-541nInsertion a node to B-Tree. P542-547nRemove a node in B-Tree. P548-554 7/26/2024数据结构与程序设计10B-tree Search Method Declarationn#includeB_node.cppnenum Error_codenot_present, duplicate_error, overflow, success;ntemplate nclass B_tree npublic: / Add public methods.nError_code search_tree(Entry &target);nB_tree();nprivate: / data membersnB_node *root;n/ Add private auxiliary functions here.nError_code recursive_search_tree(B_node *current, Entry &target);nError_code search_node(B_node *current, const Entry &target, int &position);n;7/26/2024数据结构与程序设计11B-tree constructorntemplate nB_tree : B_tree()n/ data members:nroot=NULL;n;7/26/2024数据结构与程序设计12B_tree Search implementationntemplate nError_code B_tree :search_tree(Entry &target)n/* Post: If there is an entry in the B-tree whose key matches that intarget , the pa-nrametertarget is replaced by the correspondingEntry from the B-treenand a code of success is returned. Otherwise a code of not presentnis returned.nUses: recursive search tree */nnreturn recursive_search_tree(root, target);n7/26/2024数据结构与程序设计13How to search target Key u or h7/26/2024数据结构与程序设计14template Error_code B_tree :recursive_search_tree(B_node *current, Entry &target)/* Pre: current is eitherNULL or points to a subtree of theB tree .Post: If the Key of target is not in the subtree, a code of not present isreturned. Otherwise, a code ofsuccess is returned andtarget is set tothe correspondingEntry of the subtree.Uses: recursive search tree recursively andsearch node */Error_code result = not_present;int position;if (current != NULL) result = search_node(current, target, position);if (result = not_present)result = recursive_search_tree(current-branchposition, target);elsetarget = current-dataposition; return result;7/26/2024数据结构与程序设计15B-tree search a nodetemplate 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 correspondingEntry 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;elsereturn not_present;7/26/2024数据结构与程序设计16Discuss: B-tree search a nodenFor B-trees of large order, this function should be modified to use binary search instead of sequential search.nAnother possibility is to use a linked binary search tree instead of a sequential array of entries for each node.7/26/2024数据结构与程序设计17Insertion into a B-TreenIn 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:7/26/2024数据结构与程序设计18Insertion into a B-Tree P538n1. Search the tree for the new key. This search (if the key is truly new) will terminate in failure at a leaf.n2. Insert the new key into to the leaf node. If the node was not previously full, then the insertion is finished.nFull node Split: n3. 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.n4. When a node splits, move up one level, insert the median key into this parent node, and repeat the splitting process if necessary.n5. 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.7/26/2024数据结构与程序设计19Example Growth of 5 B-tree P5387/26/2024数据结构与程序设计20Example Growth of 5 B-tree P5387/26/2024数据结构与程序设计21Example Growth of 5 B-tree P5387/26/2024数据结构与程序设计22B-tree insert method declarationn#includeB_node.cppnenum Error_codenot_present, duplicate_error, overflow, success;ntemplate nclass B_tree npublic: / Add public methods.nError_code insert(const Entry &new_entry);nprivate: / data membersnB_node *root;nError_code push_down(nB_node *current, const Entry &new_entry,nEntry &median, B_node * &right_branch);nvoid push_in(B_node *current,nconst Entry &entry, B_node *right_branch, int position);nvoid split_node(B_node *current, / node to be splitnconst Entry &extra_entry,B_node *extra_branch,nint position, /index in node whereextra entry goesnB_node * &right_half, Entry &median); n / new node for right half of entriesn;7/26/2024数据结构与程序设计23B-tree insert: push downError_code push_down(B_node *current, const Entry &new_entry,Entry &median, B_node * &right_branch);nThe recursive function push down uses three more output parameters.ncurrent 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:nThe old node *current contains the left half of the entries.nmedian gives the median record.nright branch points to a new node containing the right half of the former *current.nIf *current is NULL. Median is the new_entry, right branch is NULL7/26/2024数据结构与程序设计24B-tree insert: push down7/26/2024数据结构与程序设计25B-tree insert method implementation p542-543ntemplate nError_code B_tree :insert(const Entry &new_entry)nnEntry median;nB_node *right_branch, *new_root;nError_code result = push_down(root, new_entry, median, right_branch);nif (result = overflow) / The whole tree grows in height.n/ Make a brand new root for the whole B-tree.nnew_root = new B_node;nnew_root-count = 1;nnew_root-data0 = median;nnew_root-branch0 = root;nnew_root-branch1 = right_branch;nroot = new_root;nresult = success;n nreturn result;n7/26/2024数据结构与程序设计26B-tree push down method p544template Error_code B_tree :push_down(B_node *current, const Entry &new_entry,Entry &median, B_node * &right_branch)Error_code result;int position;if (current = NULL) / Since we cannot insert in an empty tree, the recursion terminates.median = new_entry;right_branch = NULL;result = overflow; else / Search the current node.if (search_node(current, new_entry, position) = success)result = duplicate_error;else Entry extra_entry;B_node *extra_branch;result = push_down(current-branchposition, new_entry,extra_entry, extra_branch);if (result = overflow) / Entry extra entry now must be added tocurrentif (current-count order-1) result = success;push_in(current, extra_entry, extra_branch, position); else split_node(current, extra_entry, extra_branch, position, right_branch, median);/ Entry median and itsright branch will go up to a higher node. return result;7/26/2024数据结构与程序设计27B-tree push in methodntemplate nvoid B_tree : push_in(nB_node *current, const Entry &entry, B_node *right_branch, int position)7/26/2024数据结构与程序设计28B-tree push in method ntemplate nvoid B_tree : push_in(nB_node *current,nconst Entry &entry, B_node *right_branch, int position)n/* Pre: current points to a node of aB tree . The node*current is not full andentrynbelongs in*current at indexposition .nPost: entry has been inserted along with its right-hand branch right branch inton*current at indexposition . */nnfor (int i = current-count; i position; i- ) n/ Shift all later data to the right.ncurrent-datai = current-datai-1;ncurrent-branchi+1 = current-branchi;n ncurrent-dataposition = entry;ncurrent-branchposition+1 = right_branch;ncurrent-count+;n7/26/2024数据结构与程序设计29B-tree split node p546ntemplate nvoid 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)7/26/2024数据结构与程序设计30B-tree split node p546ntemplate nvoid B_tree :split_node(nB_node *current, / node to be splitnconst Entry &extra_entry, / new entry to insertnB_node *extra_branch,n/ subtree on right ofextra entrynint position, /index in node whereextra entry goesnB_node * &right_half, / new node for right half of entriesnEntry &median) / median entry (in neither half)nnright_half = new B_node;nint mid = order/2; / The entries frommid on will go toright half .nif (position = mid) / First case: extra entry belongs in left half.nfor (int i = mid; i datai-mid = current-datai;nright_half-branchi+1-mid = current-branchi+1;n ncurrent-count = mid;nright_half-count = order-1-mid;npush_in(current, extra_entry, extra_branch, position);n nelse / Second case: extra entry belongs in right half.nmid+; /Temporarily leave the median in left half.nfor (int i = mid; i datai-mid = current-datai;nright_half-branchi+1-mid = current-branchi+1;n ncurrent-count = mid;nright_half-count = order-1-mid;npush_in(right_half, extra_entry, extra_branch, position-mid);n nmedian = current-datacurrent-count-1;n/ Remove median from left half.nright_half-branch0 = current-branchcurrent-count;ncurrent-count-;n7/26/2024数据结构与程序设计31B-tree Removen(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. n(2) We promote the immediate predecessor (or successor) into the position occupied by the deleted entry, and delete the entry from the leaf.n(3) handle the leaf been deleted an entry.n如果删除一个元素后，叶子节点的元素个数如果删除一个元素后，叶子节点的元素个数= m/2 ; 删除除结束。束。n如果删除一个元素后，叶子节点的元素个数如果删除一个元素后，叶子节点的元素个数 m/2 ; n查看该叶子节点的左兄弟或者友兄弟节点是否有多余的元素：查看该叶子节点的左兄弟或者友兄弟节点是否有多余的元素：n有则调整元素的结构即可。有则调整元素的结构即可。n左右兄弟的元素如果正好是左右兄弟的元素如果正好是 m/2 -1，则需要需要进行合并操作。行合并操作。7/26/2024数据结构与程序设计325 B-tree Remove7/26/2024数据结构与程序设计335 B-tree Remove7/26/2024数据结构与程序设计34B-tree Remove P550-554n#includeB_node.cppnenum Error_codenot_present, duplicate_error, overflow, success;ntemplate nclass B_tree npublic: / Add public methods.nError_code remove(const Entry &target);nprivate: / data membersnError_code recursive_remove(B_node *current, const Entry &target);nvoid remove_data(B_node *current, int position);nvoid copy_in_predecessor(B_node *current, int position);nvoid restore(B_node *current, int position);nvoid move_left(B_node *current, int position);nvoid move_right(B_node *current, int position);nvoid combine(B_node *current, int position);n;7/26/2024数据结构与程序设计35Mainn#includeBTree.cppnvoid main()n B_tree mybtree;n mybtree.insert(a);n mybtree.insert(g);n mybtree.insert(f);n mybtree.insert(b);n mybtree.insert(k);n mybtree.insert(d);n mybtree.insert(h);n mybtree.insert(m);n mybtree.insert(j);n mybtree.insert(e);n mybtree.insert(s);n mybtree.insert(i);n mybtree.insert(r);n mybtree.insert(x);n mybtree.insert(c);n mybtree.insert(l);n mybtree.insert(n);n mybtree.insert(t);n mybtree.insert(u);n mybtree.insert(p);7/26/2024数据结构与程序设计36Mainn char target=k;n coutmybtree.search_tree(target);n mybtree.remove(k);n coutmybtree.search_tree(target); n7/26/2024数据结构与程序设计37Result307/26/2024数据结构与程序设计38上机：实现上机：实现BTree的操作的操作n请实现BTree的查找和插入操作。n删除操作为选作内容。7/26/2024数据结构与程序设计39homeworknP555nE1nE2(c)