array maintenance average complexity data structures models of computation
Institute of Information Theories and Applications FOI ITHEA
In this paper we present a data structure which improves the average complexity of the operations of
updating and a certain type of retrieving information on an array. The data structure is devised from a particular
family of digraphs verifying conditions so that they represent solutions for this problem.