The Algebra of Binary Search Trees
Preprint
Abstract
We introduce a monoid structure on the set of binary search trees, by a process very similar to the construction of the plactic monoid, the Robinson-Schensted insertion being replaced by the binary search tree insertion. This leads to a new construction of the algebra of Planar Binary Trees of Loday-Ronco, defining it in the same way as Non-Commutative Symmetric Functions and Free Symmetric Functions. We briefly explain how the main known properties of the Loday-Ronco algebra can be described and proved with this combinatorial point of view, and then discuss it from a representation theoretical point of view, which in turns leads to new combinatorial properties of binary trees.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- NONCOMMUTATIVE SYMMETRIC FUNCTIONS VI: FREE QUASI-SYMMETRIC FUNCTIONS AND RELATED ALGEBRASInternational Journal of Algebra and Computation, 2002
- Order Structure on the Algebra of Permutations and of Planar Binary TreesJournal of Algebraic Combinatorics, 2002
- Hopf Algebra of the Planar Binary TreesAdvances in Mathematics, 1998
- Noncommutative Symmetric Functions Iv: Quantum Linear Groups and Hecke Algebras at q = 0Journal of Algebraic Combinatorics, 1997
- A Plactic Algebra for Semisimple Lie AlgebrasAdvances in Mathematics, 1996
- Duality between Quasi-Symmetrical Functions and the Solomon Descent AlgebraJournal of Algebra, 1995
- Duality of Graded GraphsJournal of Algebraic Combinatorics, 1994
- Permutation statistics and linear extensions of posetsJournal of Combinatorial Theory, Series A, 1991
- q-Hook length formulas for forestsJournal of Combinatorial Theory, Series A, 1989
- A q-analogue of U(g[(N+1)), Hecke algebra, and the Yang-Baxter equationLetters in Mathematical Physics, 1986