emerges as an alternative to the avl-balancing criterion performance comparison is therefore both possible and desirable we refrain from involved mathematical analysis and concentrate on some basic differences it can be proven that the avl-balanced trees are subset of the sbb-trees hencethe class of the latter is larger it follows that their path length is on the average larger than in the avl case note in this connection the worst-case tree ( in fig on the other handnode rearrangement is called for less frequently the balanced tree is therefore preferred in those applications in which key retrievals are much more frequent than insertions (or deletions)if this quotient is moderatethe sbb-tree scheme may be preferred it is very difficult to say where the borderline lies it strongly depends not only on the quotient between the frequencies of retrieval and structural changebut also on the characteristics of an implementation this is particularly the case if the node records have densely packed representationand if therefore access to fields involves part-word selection the sbb-tree has later found rebirth under the name of red-black tree the difference is that whereas in the case of the symmetricbinary -tree every node contains two -fields indicating whether the emanating pointers are horizontalevery node of the red-black tree contains single -fieldindicating whether the incoming pointer is horizontal the name stems from the idea to color nodes with incoming down-pointer blackand those with incoming horizontal pointer red no two red nodes can immedaitely follow each other on any path thereforelike in the cases of the bband sbb-treesevery search path is at most twice as long as the height of the tree there exists canonical mapping from binary -trees to red-black trees priority search trees treesand in particular binary treesconstitute very effective organisations for data that can be ordered on linear scale the preceding have exposed the most frequently used ingenious schemes for efficient searching and maintenance (insertiondeletiontreeshoweverdo not seem to be helpful in problems where the data are located not in one-dimensionalbut in multi-dimensional space in factefficient searching in multi-dimensional spaces is still one of the more elusive problems in computer sciencethe case of two dimensions being of particular importance to many practical applications upon closer inspection of the subjecttrees might still be applied usefully at least in the two-dimensional case after allwe draw trees on paper in two-dimensional space let us therefore briefly review the characteristics of the two major kinds of trees so far encountered search tree is governed by the invariants left nil implies right nil implies left xp right xholding for all nodes with key it is apparent that only the horizontal position of nodes is at all constrained by the invariantand that the vertical positions of nodes can be arbitrarily chosen such that access times in searching( path lengthsare minimized heapalso called priority treeis governed by the invariants left nil implies right nil implies < left yp < right yholding for all nodes with key here evidently only the vertical positions are constrained by the invariants it seems straightforward to combine these two conditions in definition of tree organization in twodimensional spacewith each node having two keys and which can be regarded as coordinates of the node such tree represents point set in planei in two-dimensional cartesian spaceit is therefore