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 children2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 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