2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教 e If ksm is the number of children, then the node cont ains exactly k-l 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 A5-way search tree(not a B-tree)P. 536 11. 3. 3 Balanced Multiway Trees(B-Trees) P 536 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 non- empty children, and at least ceiling(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 A B-tree of order 5 P 537 11.3.4 Insertion into a B-Tree P. 537 n 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 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 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 11.3.5 B-Tree Declarations in C+ We add the order as a second template parameter. For example, B tree<int, 5> sample tree, declares ample tree as a b tree of order 5 that holds integer records B-tree class declaration: P. 539 Node declaration: P 539 Conventions: P 540 count gives the number of records in the B node If count is nonzero then the node has count+l children branch[o points to the subtree containing all records with keys less than that in datalog For 1 s position s count-l, branch[position] points to the subtree with keys strictly between those in the subtrees pointed to by datal position-1 and datal position] branch count] points to the subtree with keys greater than that of datal count-1 Searching in a B-Tree P 540 Public method: P 540 Recursive function: P. 540-541 o This function has been written recursively to exhibit the similarity of its structure to that of the insertion function o The recursion is tail recursion and can easily be replaced by iteration Searching a node P 541 This function determines if the target is present in the current node, and, if not, finds which of the count+l branches will contain the target key. P54 For B-trees of large order, this function should be modified to use binary search instead of sequential seart Another possibility is to use a linked binary search tree in- stead of a sequential array of entries for each node Insertion: Parameters and push down P 542 Insertion is done with recursion in a function called push down We require that the record new entry being inserted is not already present in the tree 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 overflow, and the following come into 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*current2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ 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. A5-way search tree(not a B-tree) P. 536 11.3.3 Balanced Multiway Trees (B-Trees) P. 536 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 non- empty children, and at least ceiling(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. A B-tree of order 5 P. 537 11.3.4 Insertion into a B-Tree P. 537 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: 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. 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. Growth of a B-Tree P. 538 11.3.5 B-Tree Declarations in C++ We add the order as a second template parameter. For example, B_tree<int, 5> sample_tree; declares sample tree as a B_tree of order 5 that holds integer records. B-tree class declaration: P. 539 Node declaration: P. 539 Conventions: P. 540 ⚫ count gives the number of records in the B_node. ⚫ If count is nonzero then the node has count+1 children. ⚫ branch[0] points to the subtree containing all records with keys less than that in data[0]. ⚫ For 1 ≤ position ≤ count−1 , branch[position] points to the subtree with keys strictly between those in the subtrees pointed to by data[position−1] and data[position]. ⚫ branch[count] points to the subtree with keys greater than that of data[count − 1]. Searching in a B-Tree P. 540 Public method: P. 540 Recursive function: P. 540-541 ⚫ This function has been written recursively to exhibit the similarity of its structure to that of the insertion function. ⚫ The recursion is tail recursion and can easily be replaced by iteration. Searching a Node P. 541 This function determines if the target is present in the current node, and, if not, finds which of the count+1 branches will contain the target key. P. 541 ⚫ 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 in- stead of a sequential array of entries for each node. Insertion: Parameters and push_down P. 542 ⚫ Insertion is done with recursion in a function called push_down. ⚫ We require that the record new_entry being inserted is not already present in the tree. 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 overflow, 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