The Algebra of Binary Search Trees

Details The Algebra of Binary Search Trees The Algebra of Binary Search Trees

2004-01-09

arxiv.org/abs/math/0401089v2

Mathematics

Combinatorics

49 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Algebra of Binary Search Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Algebra of Binary Search Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Algebra of Binary Search Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66647