کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334744 | 690570 | 2005 | 37 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The algebra of binary search trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 339, Issue 1, 11 June 2005, Pages 129-165
Journal: Theoretical Computer Science - Volume 339, Issue 1, 11 June 2005, Pages 129-165
نویسندگان
F. Hivert, J.-C. Novelli, J.-Y. Thibon,