/compute the suffix array for placing result into sa void computes vector vector sa int int ifk = /if unique namesdon' need recursion forint ++ sa [ ielse makesuffixarrays sa )/store unique names in using the suffix array forint ++ sa void computes const vector svector vector sa const vector sa int int int forint ++ ifsa + sa ]radixpasss sa sn )figure compute the suffix array for (possibly recursivelyand the suffix array for of matches reported by the query we would like to obtain similar bound for two or more dimensions the two-dimensional search tree has the simple property that branching on odd levels is done with respect to the first keyand branching on even levels is done with respect to the second key the root is arbitrarily chosen to be an odd level figure shows - tree insertion into - tree is trivial extension of insertion into binary search treeas we go down the treewe need to maintain the current level to keep our code simplewe assume that basic item is an array of two elements we then need to toggle the level between and figure shows the code to perform an insertion we use recursion in this sectiona nonrecursive implementation that would be used in practice is straightforward and left as exercise one difficulty is duplicatesparticularly since several items can agree in one key our code allows duplicatesand always places them in right branchesclearly this can be problem if there are too many duplicates moment' thought will convince you that randomly constructed - tree has the same structural properties as random binary search treethe height is (log non averagebut (nin the worst case