Topological and categorical properties of binary trees
Submitted: 2013-11-12
|Accepted: 2013-11-12
|Downloads
Keywords:
Algorithm, Decision tree, Lower topology, Semilattice
Supporting agencies:
Abstract:
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.
References:
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.
