( , trees in this sectionwe consider data structure known as ( , tree it is particular example of more general structure known as multiway search treein which internal nodes may have more than two children other forms of multiway search trees will be discussed in section multiway search trees recall that general trees are defined so that internal nodes may have many children in this sectionwe discuss how general trees can be used as multiway search trees map items stored in search tree are pairs of the form (kv)where is the key and is the value associated with the key definition of multiway search tree let be node of an ordered tree we say that is -node if has children we define multiway search tree to be an ordered tree that has the following propertieswhich are illustrated in figure aeach internal node of has at least two children that iseach internal node is -node such that > each internal -node of with children cd stores an ordered set of key-value pairs ( )(kd- vd- )where <<kd- let us conventionally define and kd for each item (kvstored at node in the subtree of rooted at ci dwe have that ki- < <ki that isif we think of the set of keys stored at as including the special fictitious keys and kd +then key stored in the subtree of rooted at child node ci must be "in betweentwo keys stored at this simple viewpoint gives rise to the rule that -node stores regular keysand it also forms the basis of the algorithm for searching in multiway search tree by the above definitionthe external nodes of multiway search do not store any data and serve only as "placeholders these external nodes can be efficiently represented by none referencesas has been our convention with binary search trees (section howeverfor the sake of expositionwe will discuss these as actual nodes that do not store anything based on this definitionthere is an interesting relationship between the number of key-value pairs and the number of external nodes in multiway search tree proposition an -item multiway search tree has external nodes we leave the justification of this proposition as an exercise ( -