procedure search (xintegervar pnode)begin if nil then (* not in treeinsert*new( ) key :xp count : left :nilp right :nil elsif key then search(xp leftelsif key then search(xp rightelse inc( countend end search the use of sentinel again simplifies the task somewhat clearlyat the start of the program the variable root must be initialized by the pointer to the sentinel instead of the value niland before each search the specified value must be assigned to the key field of the sentinel procedure search (xintegervar pnode)begin if key then search(xp leftelsif key then search(xp rightelsif then inc( countelse (*insert*new( ) key :xp left :sp right :sp count : end end search although the purpose of this algorithm is searchingit can be used for sorting as well in factit resembles the sorting by insertion method quite stronglyand because of the use of tree structure instead of an arraythe need for relocation of the components above the insertion point vanishes tree sorting can be programmed to be almost as efficient as the best array sorting methods known but few precautions must be taken after encountering matchthe new element must also be inserted if the case key is handled identically to the case keythen the algorithm represents stable sorting methodi items with identical keys turn up in the same sequence when scanning the tree in normal order as when they were inserted in generalthere are better ways to sortbut in applications in which searching and sorting are both neededthe tree search and insertion algorithm is strongly recommended it isin factvery often applied in compilers and in data banks to organize the objects to be stored and retrieved an appropriate example is the construction of cross-reference index for given textan example that we had already used to illustrate list generation our task is to construct program that (while reading text and printing it after supplying consecutive line numberscollects all words of this textthereby retaining the numbers of the lines in which each word occurred when this scan is terminateda table is to be generated containing all collected words in alphabetical order with lists of their occurrences obviouslythe search tree (also called lexicographic treeis most suitable candidate for representing the words encountered in the text each node now not only contains word as key valuebut it is also the head of list of line numbers we shall call each recording of an occurrence an item hencewe encounter both trees and linear lists in this example the program consists of two main partsnamelythe scanning phase and the table printing phase the latter is straightforward application of tree traversal routine in which visiting each node implies the printing of the key value (wordand the scanning of its associated list of line numbers (itemsthe following are further clarifications regarding the program listed below table shows the results of processing the text of the preceding procedure search