2008级计算机 供课堂教学使用 Chapter 1 1 MULTIWAY TREES P 520 1. Orchards, Trees, and Binary Trees XIcographic Search Tr 3. External Searching: B-Trees 11.1 Orchards, Trees, and Binary Trees 11. 1. 1 On the Classification of Species P. 521-52 Definitions. o A(free)tree is any set of points(called vertices) and any set of pairs of distinct vertices(called edges or branches) such that(1)there is a sequence of edges(a path) from any vertex to any other, and( 2)there are no circuits, that is, no paths starting from a vertex and returning to the same vertex. A rooted tree is a tree in which one vertex, called the root, is distinguished An ordered tree is a rooted tree in which the children of each vertex are assigned an order A forest is a set of trees. We usually assume that all trees in a forest are rooted An orchard (also called an ordered forest)is an ordered set of ordered tre 1. 2 Implementations of Ordered Trees P 523 Multiple links first child and next sibling links Correspondence with binary trees Linked implementation of ordered tree: P 523 Rotated form: P. 524 11.1.3 Recursive Definitions P. 525 DEFINITION: A rooted tree consists of a single vertex v, called the root of the tree together with a forest F whose trees are alled the subtrees of the root. a forest F is a(possibly empty) set of rooted trees DEFINITION: An ordered tree t consists of a single vertex v. called the root of the tree. together with an orchard o. whose trees are called the subtrees of the root v. We may denote the ordered tree with the ordered pair t=(v, O). An orchard is either the empty set o, or consists of an ordered tree T, called the first tree of the orchard, together with another orchard o (which contains the remaining trees of the orchard). We may denote the orchard with the ordered pairO=(T,o) 11. 1. 4 The Formal Correspondence P 526 DEFINITION: A binary tree B is either the empty set O or consists of a root vertex v with two binary trees Bi and B2. We may denote the binary tree with the ordered triple b=[v, B1, B2 THEOREM 1l. 1: Let s be any finite set of vertices. There is a one-to-one correspondence f from the set of orchards whose set of vertices is S to the set of binary trees whose set of vertices is S 11.1.5 Rotations P. 527 1. Draw the orchard so that the first child of each vertex is immediately below the vertex 2. Draw a vertical link from each vertex to its first child. and draw a horizontal link from each vertex to its next sibling 3. Remove the remaining original link 4. Rotate the diagram 45 degrees clockwise, so that the vertical links appear as left links and the horizontal links as right links 11.1.6 Summary: P 528 Orchards and binary trees correspond by any of first child and next sibling links rotations of diagrams, formal notational equivalence 111.2 Lexicographic Search Trees: Tries 11.2.1 DEFINITION: A trie of order m is either empty or consists of an ordered sequence of exactly m tries of order m 2.2 Trie of words constructed from a, b, c P 531 11.2.3 C++ Trie Declarations P. 532 Every Record has a Key that is an alphanumeric string Method char key letter(int position)returns the character in the given position of the key or returns a blank, if the key has length less than position Auxiliary function int alphabetic order( char symbol) returns the alphabetic position of the character symbol, or 27 for nonblank, nonalphabetic characters, or 0 for blank characters 11.2. 4 Searching a Trie P. 532 11.2.5 Insertion into a Trie P. 533 111.3 External Searching: B-Trees P 535 11.3.2 Multiway Search Trees e 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
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 1 1 MULTIWAY TREES P.520 -------------------------------------------------------------------------------------------------------------------------------- 1. Orchards, Trees, and Binary Trees 2. Lexicographic Search Trees: Tries 3. External Searching: B-Trees [11.1] Orchards, Trees, and Binary Trees 11.1.1 On the Classification of Species P. 521-522 Definitions: ⚫ A (free) tree is any set of points (called vertices) and any set of pairs of distinct vertices (called edges or branches) such that (1) there is a sequence of edges (a path) from any vertex to any other, and (2) there are no circuits, that is, no paths starting from a vertex and returning to the same vertex. ⚫ A rooted tree is a tree in which one vertex, called the root, is distinguished. ⚫ An ordered tree is a rooted tree in which the children of each vertex are assigned an order. ⚫ A forest is a set of trees. We usually assume that all trees in a forest are rooted. ⚫ An orchard (also called an ordered forest) is an ordered set of ordered trees. 11.1.2 Implementations of Ordered Trees P. 523 ⚫ Multiple links ⚫ first_child and next_sibling links ⚫ Correspondence with binary trees Linked implementation of ordered tree: P. 523 Rotated form: P. 524 11.1.3 Recursive Definitions P. 525 DEFINITION: A rooted tree consists of a single vertex v , called the root of the tree, together with a forest F , whose trees are called the subtrees of the root. A forest F is a (possibly empty) set of rooted trees. DEFINITION: An ordered tree T consists of a single vertex v , called the root of the tree, together with an orchard O , whose trees are called the subtrees of the root v . We may denote the ordered tree with the ordered pair T = {v, O }. An orchard O is either the empty set , or consists of an ordered tree T , called the first tree of the orchard, together with another orchard O’ (which contains the remaining trees of the orchard). We may denote the orchard with the ordered pair O = (T , O’). 11.1.4 The Formal Correspondence P. 526 DEFINITION: A binary tree B is either the empty set or consists of a root vertex v with two binary trees B1 and B2 . We may denote the binary tree with the ordered triple B = [v, B1 , B2 ]. THEOREM 11.1: Let S be any finite set of vertices. There is a one-to-one correspondence f from the set of orchards whose set of vertices is S to the set of binary trees whose set of vertices is S . 11.1.5 Rotations P. 527 1. Draw the orchard so that the first child of each vertex is immediately below the vertex. 2. Draw a vertical link from each vertex to its first child, and draw a horizontal link from each vertex to its next sibling. 3. Remove the remaining original links. 4. Rotate the diagram 45 degrees clockwise, so that the vertical links appear as left links and the horizontal links as right links. 11.1.6 Summary: P. 528 Orchards and binary trees correspond by any of: ⚫ first_child and next_sibling links, ⚫ rotations of diagrams, ⚫ formal notational equivalence. [11.2] Lexicographic Search Trees: Tries 11.2.1 DEFINITION: A trie of order m is either empty or consists of an ordered sequence of exactly m tries of order m. 11.2.2 Trie of words constructed from a, b, c P. 531 11.2.3 C++ Trie Declarations P. 532 ⚫ Every Record has a Key that is an alphanumeric string. ⚫ Method char key letter(int position) returns the character in the given position of the key or returns a blank, if the key has length less than position. ⚫ Auxiliary function int alphabetic order(char symbol) returns the alphabetic position of the character symbol, or 27 for nonblank, nonalphabetic characters, or 0 for blank characters. 11.2.4 Searching a Trie P. 532 11.2.5 Insertion into a Trie P. 533 [11.3] External Searching: B-Trees P. 535 11.3.2 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
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 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*current
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ 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 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
2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教学使用 Action of push down function when a node splits P 542 Public Insertion Method P 543 cursive Insertion into a Subtree P 544 Inserting a Key into a Node P 545 Splitting a Full Node P 545 Example of Splitting a Full Node P 547 Function split node, Specifications P 546 1.3.6 Deletion from a B-Tree P 548 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 e We promote the immediate predecessor (or successor into the position occupied by the deleted entry, and delete the entry from the leaf If the leaf contains more than the minimum num ber of entries then one of them can be deleted with no further action o If the leaf contains the minimum number, then we first look at the two leaves(or, in the case of a node on the outside, one leaf) that are immediately adjacent to each other and are children of the same node e arent node, and the entry from the parent moved into the leaf where the deletion is octu a into the If one of these has more than the minimum number of entries then one of them can be moved into the If the adjacent leaf has only the minimum number of entries, then the two leaves and the median entry from the parent can all be combined as one new leaf, which will contain no more than the maximum number of entries allowed If this step leaves the parent node with too few entries, then the process propagates upward. In the limiting case, the last entry is removed from the root, and then the height of the tree decreases Example of Deletion from a B-tree P 549 Public Deletion Method P. 550 Recursive deletion P.550-551 auxiliary Functions Remove data from a leaf: P 551 Replace data by its immediate predecessor: P 552 Restore Minimum Num ber of Entries P. 552 Function to Restore Minimum Node Entries P. 552-553 Function move left P 553 Function move right P 554 Function com bine P 554 Pointers and Pitfalls 3 items P. 566-567 Errata p 524, Fig. 11.3: At upper right, "next child"should be"next sibling p 536, definition of B-tree: Change "m-way tree"to"m-way search tree p 547, Fig. 11. 13: Final node shown at lower right should have entries h and j rather than b and d
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Action of push_down function when a node splits P. 542 Public Insertion Method P. 543 Recursive Insertion into a Subtree P. 544 Inserting a Key into a Node P. 545 Splitting a Full Node P. 545 Example of Splitting a Full Node P. 547 Function split node, Specifications P. 546 11.3.6 Deletion from a B-Tree P. 548 ⚫ 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. ⚫ We promote the immediate predecessor (or successor) into the position occupied by the deleted entry, and delete the entry from the leaf. ⚫ If the leaf contains more than the minimum number of entries, then one of them can be deleted with no further action. ⚫ If the leaf contains the minimum number, then we first look at the two leaves (or, in the case of a node on the outside, one leaf) that are immediately adjacent to each other and are children of the same node. If one of these has more than the minimum number of entries, then one of them can be moved into the parent node, and the entry from the parent moved into the leaf where the deletion is occurring. ⚫ If the adjacent leaf has only the minimum number of entries, then the two leaves and the median entry from the parent can all be combined as one new leaf, which will contain no more than the maximum number of entries allowed. ⚫ If this step leaves the parent node with too few entries, then the process propagates upward. In the limiting case, the last entry is removed from the root, and then the height of the tree decreases. Example of Deletion from a B-tree P. 549 Public Deletion Method P. 550 Recursive Deletion P. 550-551 Auxiliary Functions Remove data from a leaf: P. 551 Replace data by its immediate predecessor: P. 552 Restore Minimum Number of Entries P. 552 Function to Restore Minimum Node Entries P. 552-553 Function move left P. 553 Function move right P. 554 Function combine P. 554 Pointers and Pitfalls 3 items P.566-567 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 524, Fig. 11.3: At upper right, "next_child" should be "next_sibling". p. 536, definition of B-tree: Change "m-way tree" to "m-way search tree". p. 547, Fig. 11.13: Final node shown at lower right should have entries h and j rather than b and d. -------------------------------------------------------------------------------------------------------------------------------