Topological and categorical properties of binary trees
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.
J. Adamek, H. Herrlich and G. Strecker, Abstract and Concrete Categories, John Wiley and Sons, Inc., 1990.
A. Aho, J. Hopcroft and J. Ullman, Data Structures and Algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley, 1983.
G. Birkhoff. Lattice Theory, American Mathematical Society Colloquium Publications, Volume XXV, 1967.
B. C. Pierce, Basic category theory for computer scientists, Foundations of computing series 1991.
G. K. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove and D. S. Scott, A Compendium of Continuous Lattices, Springer-Verlag, Berlin, 1980. http://dx.doi.org/10.1007/978-3-642-67678-9
D. Knuth, The Art of Computer Programming vol. 1, Addison-Wesley, 1973.
D. Knuth, The Art of Computer Programming vol. 3, Addison-Wesley, 1973.
R. Kopperman and R.Wilson, On the role of finite, hereditarily normal spaces and maps in the genesis of compact Hausdorff spaces, Topology Appl. 135 (2004), 265-275. http://dx.doi.org/10.1016/S0166-8641(03)00181-0
M. O’Keeffe, H. Pajoohesh and M. Schellekens, On the relation between balance and speed of algorithms, Hadronic Journal, to appear.
M. O’Keeffe, H. Pajoohesh and M. Schellekens, Decision trees of algorithms and a semivaluation to measure their distance, Electron. Notes Theor. Comput. Sci. (Proceeding of MFCSIT 2004), to appear.
D. Stott Parker and P. Ram, The construction of Huffman codes is a submodular (”convex”) optimization problem over a lattice of binary trees, Sociely for industrial and Applied Mathematics 28, no. 5, 1875–1905.
Metrics powered by PLOS ALM
Cited-By (articles included in Crossref)
This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site
1. The Meet Operation in the Imbalance Lattice of Maximal Instantaneous Codes: Alternative Proof of Existence
Stephan Foldes, Douglas Stott Parker, Sandor Radeleczki
IEEE Transactions on Information Theory vol: 65 issue: 12 first page: 8207 year: 2019
Esta revista se publica bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
Universitat Politècnica de València
e-ISSN: 1989-4147 https://doi.org/10.4995/agt