there is an interesting relationship between the number of entries and the number of external nodes proposition an -entry multi-way search tree has + external nodes we leave the justification of this proposition as an exercise ( - searching in multi-way tree given multi-way search tree twe note that searching for an entry with key is simple we perform such search by tracing path in starting at the root (see figure and when we are at -node during this searchwe compare the key with the keys stored at if for some ithe search is successfully completed otherwisewe continue the search in the child vi of such that < < (recall that we conventionally define and if we reach an external nodethen we know that there is no entry with key in tand the search terminates unsuccessfully data structures for representing multi-way search trees in section we discuss linked data structure for representing general tree this representation can also be used for multi-way search tree in factin using general tree to implement multi-way search treethe only additional information that we need to store at each node is the set of entries (including keysassociated with that node that iswe need to store with reference to some collection that stores the entries for recall that when we use binary search tree to represent an ordered dictionary dwe simply store reference to single entry at each internal node in using multi-way search tree to represent dwe must store reference to the ordered set of entries associated with at each internal node of this reasoning may at first seem like circular argumentsince we need representation of an ordered dictionary to represent an ordered dictionary we can avoid any circular argumentshoweverby using the bootstrapping techniquewhere we use previous (less advancedsolution to problem to create new (more advancedsolution in this casebootstrapping consists of representing the ordered set associated with each internal node using dictionary data structure that we have previously constructed (for examplea search table based on sorted arrayas shown in section in particularassuming we already have way of implementing ordered dictionarieswe can realize multi-way search tree by taking tree and storing such dictionary at each node of