Data Structures and Algorithms, Week 08, Lecture 1 11 B-Trees, Definition• Definition. Suppose m is a positive integer. Then a B-tree of order mis a tree with the following properties.1. Each nonempty node other than the root has between dm2e and mchildren.2. If the tree is nonempty, the root has between 2 and m children.3. If a node has c children then it stores c − 1 keys in increasingorder.4. If the keys stored in a node arek1< k2< · · · < ks,then(a) all keys stored in leftmost or 0th subtree are less than k1,(b) all keys stored in the ith subtree, 1 ≤ i < s, lie between kiand ki+1,(c) and all keys stored in the last subtree are greater than thanks.5. All the leaves have the same depth.Data Structures and Algorithms, Week 08, Lecture 1 2// insertsearch current node for key;if (found) {print message;return null;} else if (current node is a leaf) {insert key into current node;} else {recursively insert into appropriate child of currentnode, possibly returning a new key and a newchild;if (return is not null) {insert new key into current node;set reference to new child;}}if (current node has too many children) {split the current node, creating a new key and a newchild;return the key and child;} else {return null;}Data Structures and Algorithms, Week 08, Lecture 1 3// removesearch current node for key;if (found) {if (current node is a leaf) {delete key from current node;} else {temp == curr node;find immediate predecessor of key (changing current node);replace key in temp with predecessor;delete immediate predecessor from new current node;}} else if (current node is a leaf) {print message;return noMerge;} else {recursively delete key from appropriate child of current node,passing in "split key" and returning merge info;if (children were merged)delete split key;}if (current node has too few keys) {if (left sibling has extra key) {shuffle keys;return noMerge;} else if (right sibling has extra key) {shuffle keys;return noMerge;} else {merge current node, split key, and sibling;return merge;}elsereturn
View Full Document