Unformatted text preview:

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

USF CS 245 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?