The algebra of binary search trees

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. [Copyright &y& Elsevier]