Technical Report No. 4, November 1987 - Abstract

Christian Icking, Rolf Klein, Thomas Ottmann:
Priority Search Trees in Secondary Memory

This report is not available in electronic form!

In this paper we investigate how priority search trees can be adapted to secondary memory. We give an optimal solution for the static case, where the set of points to be stored is fixed. For the dynamic case we present data structures derived from B-trees and from a generalized version of red-black trees. The latter are interesting in the internal case, too, since they are better balanced than standard red-black trees, in that the ratio longest path/shortest path is smaller.