skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

Unique binary-search-tree representations and equality testing of sets and sequences

RAJAMANI SUNDAR ; TARJAN, R. E

SIAM journal on computing, 1994-02, Vol.23 (1), p.24-44 [Periódico revisado por pares]

Philadelphia, PA: Society for Industrial and Applied Mathematics

Texto completo disponível

Citações Citado por
  • Título:
    Unique binary-search-tree representations and equality testing of sets and sequences
  • Autor: RAJAMANI SUNDAR ; TARJAN, R. E
  • Assuntos: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Binary system ; Combinatorics ; Combinatorics. Ordered structures ; Computer science ; Computer science; control theory; systems ; Dictionaries ; Equality ; Exact sciences and technology ; Graph theory ; Information retrieval. Graph ; Mathematics ; Programming languages ; Sciences and techniques of general use ; Signatures ; Theoretical computing
  • É parte de: SIAM journal on computing, 1994-02, Vol.23 (1), p.24-44
  • Descrição: This paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. Although efficient randomized solutions to the problem are known, its deterministic complexity has been open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. The results demonstrate an exponential separation between the deterministic and randomized complexities of the problem. Unique representations are applied to obtain efficient data structures for maintaining a dynamic collection of sets/sequences under queries that test the equality of a pair of objects. The data structure for set equality testing tests equality of sets in constant time and processes set updates in $O(\log m)$ amortized time and $O(\log m)$ space, where $m$ denotes the total number of updates performed. It is based on an efficient implementation of cascades of CONS operations on uniquely stored S-expressions. The data structure for sequence equality testing tests equality of sequences in constant time and processes updates in $O(\sqrt {n\log m} = \log m)$ amortized time and $O(\sqrt n )$ amortized space where $n$ denotes the length of the sequence that is updated and $m$ denotes the total number of updates performed.
  • Editor: Philadelphia, PA: Society for Industrial and Applied Mathematics
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.