advanced data structures and implementation publicvoid insertconst vector insertxroot )privatevoid insertconst vector xkdnode tint level ift =nullptr new kdnodex }else ifxlevel datalevel insertxt->left level )else insertxt->right level )figure insertion into - trees solved by recursive tree traversalas shown in figure by testing before making recursive callwe can avoid unnecessarily visiting all nodes to find specific itemwe can set low equal to high equal to the item we are searching for to perform partial match querywe set the range for the key not involved in the match to to the other range is set with the low and high point equal to the value of the key involved in the match an insertion or exact match search in - tree takes time that is proportional to the depth of the treenamelyo(log non average and (nin the worst case the running time of range search depends on how balanced the tree iswhether or not partial match is requestedand how many items are actually found we mention three results that have been shown for perfectly balanced treea range query could take ( ntime in the worst case to report matches at any nodewe may have to visit two of the four grandchildrenleading to the equation ( ( / ( in practicehoweverthese searches tend to be veryefficientand even the worst case is not poor because for typical nthe difference between and log is compensated by the smaller constant that is hidden in the big-oh notation for randomly constructed treethe average running time of partial match query is ( na )where (- )/ (see belowa recentand somewhat surprisingresult is that this essentially describes the average running time of range search of random - tree for dimensionsthe same algorithm workswe just cycle through the keys at each level howeverin practicethe balance starts getting worse because typically the effect of duplicates and nonrandom inputs becomes more pronounced we leave the coding details as an exercise for the reader and mention the analytical resultsfor perfectly balanced