- -

Topological and categorical properties of binary trees

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Topological and categorical properties of binary trees

Mostrar el registro sencillo del ítem

Ficheros en el ítem

dc.contributor.author Pajoohesh, H. es_ES
dc.date.accessioned 2017-07-28T07:40:25Z
dc.date.available 2017-07-28T07:40:25Z
dc.date.issued 2008-04-01
dc.identifier.issn 1576-9402
dc.identifier.uri http://hdl.handle.net/10251/85927
dc.description.abstract [EN] Binary trees are very useful tools in computer science for estimating the running time of so-called comparison based algorithms, algorithms in which every action is ultimately based on a prior comparison between two elements. For two given algorithms A and B where the decision tree of A is more balanced than that of B, it is known that the average and worst case times of A will be better than those of B, i.e., ₸A(n) ≤₸B(n) and TWA (n)≤TWB (n). Thus the most balanced and the most imbalanced binary trees play a main role. Here we consider them as semilattices and characterize the most balanced and the most imbalanced binary trees by topological and categorical properties. Also we define the composition of binary trees as a commutative binary operation, *, such that for binary trees A and B, A * B is the binary tree obtained by attaching a copy of B to any leaf of A. We show that (T,*) is a commutative po-monoid and investigate its properties. es_ES
dc.language Inglés es_ES
dc.publisher Universitat Politècnica de València
dc.relation.ispartof Applied General Topology
dc.rights Reconocimiento - No comercial - Sin obra derivada (by-nc-nd) es_ES
dc.subject Algorithm es_ES
dc.subject Decision tree es_ES
dc.subject Lower topology es_ES
dc.subject Semilattice es_ES
dc.title Topological and categorical properties of binary trees es_ES
dc.type Artículo es_ES
dc.date.updated 2017-07-28T07:36:05Z
dc.identifier.doi 10.4995/agt.2008.1863
dc.rights.accessRights Abierto es_ES
dc.description.bibliographicCitation Pajoohesh, H. (2008). Topological and categorical properties of binary trees. Applied General Topology. 9(1):1-14. https://doi.org/10.4995/agt.2008.1863 es_ES
dc.description.accrualMethod SWORD es_ES
dc.relation.publisherversion https://doi.org/10.4995/agt.2008.1863 es_ES
dc.description.upvformatpinicio 1 es_ES
dc.description.upvformatpfin 14 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 9
dc.description.issue 1
dc.identifier.eissn 1989-4147


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem