chap advanced tree structures ( ( ( (ad ( ( ( (bfigure example of - tree (athe - tree decomposition for -unit region containing seven data points (bthe - tree for the region of (asearching - tree for the record with specified xy-coordinate is like searching bstexcept that each level of the - tree is associated with particular discriminator example consider searching the - tree for record located at ( first compare with the point stored at the root (record in figure if matches the location of athen the search is successful in this example the positions do not match ( ' location ( is not the same as ( ))so the search must continue the value of is compared with that of to determine in which direction to branch because ax ' value of is less than ' value of we branch to the right subtree (all cities with value greater than or equal to are in the right subtreeay does not affect the decision on which way to branch at this level at the second levelp does not match record ' positionso another branch must be taken howeverat this level we branch based on the relative values of point and record (because mod which corresponds to the -coordinatebecause cy ' value of is less than py ' value of we branch to the right at this pointp is compared against the position of match is made and the search is successful as with bstif the search process reaches null pointerthen the search point is not contained in the tree here is an implementation for - tree search