advanced data structures and implementation /merge sorted sa suffixes and sorted sa suffixes void mergeconst vector sconst vector vector saconst vector sa const vector sa int nint int int int whilet ! & ! int getindexintossa tn )/ int sa ]/ ifsuffix issmallerss sa ijt sak+ ++telse sak+ ++pwhilep sak+sa +]whilet sak+getindexintossa ++ )figure merge the suffix arrays sa and sa unlike binary search treesfor which clever (log nworst-case variants existthere are no schemes that are known to guarantee balanced - tree the problem is that such scheme would likely be based on tree rotationsand tree rotations don' work in - trees the best one can do is to periodically rebalance the tree by reconstructing subtreeas described in the exercises similarlythere are no deletion algorithms beyond the obvious lazy deletion strategy if all the items arrive before we need to process queriesthen we can construct perfectly balanced - tree in ( log ntimewe leave this as exercise (cseveral kinds of queries are possible on - tree we can ask for an exact match or match based on one of the two keysthe latter type of request is partial match query both of these are special cases of an (orthogonalrange query an orthogonal range query gives all items whose first key is between specified set of values and whose second key is between another specified set of values this is exactly the problem that was described in the introduction to this section range query is easily