called cartesian tree [ - we prefer the term priority search treebecause it exhibits that this structure emerged from combination of the priority tree and the search tree it is characterized by the following invariants holding for each node pp left nil implies ( left ( < left yp right nil implies ( right ( < right yit should come as no big surprisehoweverthat the search properties of such trees are not particularly wonderful after alla considerable degree of freedom in positioning nodes has been taken away and is no longer available for choosing arrangements yielding short path lengths indeedno logarithmic bounds on efforts involved in searchinginsertingor deleting elements can be assured although this had already been the case for the ordinaryunbalanced search treethe chances for good average behaviour are slim even worsemaintenance operations can become rather unwieldy considerfor examplethe tree of fig (ainsertion of new node whose coordinates force it to be inserted above and between and requires considerable effort transforming (ainto ( ( (bfig insertion into priority search tree mccreight discovered schemesimilar to balancingthatat the expense of more complicated insertion and deletion operationguarantees logarithmic time bounds for these operations he calls that structure priority search tree [ - ]in terms of our classificationhoweverit should be called balanced priority search tree we refrain from discussing that structurebecause the scheme is very intricate and in practice hardly used by considering somewhat more restrictedbut in practice no less relevant problemmccreight arrived at yet another tree structurewhich shall be presented here in detail instead of assuming that the search space be unboundedhe considered the data space to be delimited by rectangle with two sides open we denote the limiting values of the -coordinate by xmin and xmax in the scheme of the (unbalancedpriority search tree outlined aboveeach node divides the plane into two parts along the line all nodes of the left subtree lie to its leftall those in the right subtree to its right for the efficiency of searching this choice may be bad fortunatelywe may choose the dividing line differently let us associate with each node an interval [ )ranging over all values including up to but excluding this shall be the interval within which the -value of the node may lie then we postulate that the left descendant (if anymust lie within the left halfthe right descendant within the right half of this interval hencethe dividing line is not xbut ( + )/ for each descendant the interval is halvedthus limiting the height of the tree to log(xmax -xminthis result holds only if no two nodes have the same -valuea condition whichhoweveris guaranteed by the invariant if we deal with integer coordinatesthis limit is at most equal to the wordlength of the computer used effectivelythe search proceeds like bisection or radix searchand therefore these trees are called radix priority search trees [ they feature logarithmic bounds on the number of operations required for searchinginsertingand deleting an elementand are governed by the following invariants for each node