The algebra of binary search trees

DOI10.1016/J.TCS.2005.01.012MaRDI QIDQ557924zbMATH OpenOpenAlexFDO

Authors Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Publication date 30 June 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0401089

zbMATH Keywords

Hopf algebrasPlactic monoidRepresentation theorySymmetric functions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Symmetric functions and generalizations (05E05)

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.

Recommendations

• scientific article; zbMATH DE number 2051148
• An analogue of the plactic monoid for binary search trees
• Arithmetree.
• Algebraic and combinatorial structures on pairs of twin binary trees
• On some properties of the algebra of binary trees

Cites work

• scientific article; zbMATH DE number 417855 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 1375571 (Why is no real title available?)
• scientific article; zbMATH DE number 66551 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3570606 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 791254 (Why is no real title available?)
• scientific article; zbMATH DE number 3895079 (Why is no real title available?)
• A \(q\)-analogue of \(U(\mathfrak{gl}(N+1))\), Hecke algebra, and the Yang-Baxter equation
• A plactic algebra for semisimple Lie algebras
• An analogue of the plactic monoid for binary search trees
• Combinatorial Hopf algebras and generalized Dehn–Sommerville relations
• Crystal graphs and \(q\)-analogues of weight multiplicities for the root system \(A_ n\)
• Duality between quasi-symmetric functions and the Solomon descent algebra
• Duality of graded graphs
• Hopf algebra of the planar binary trees
• Ideals of quasi-symmetric functions and super-covariant polynomials for \(\mathcal S_n\)
• Longest Increasing and Decreasing Subsequences
• NONCOMMUTATIVE SYMMETRIC FUNCTIONS VI: FREE QUASI-SYMMETRIC FUNCTIONS AND RELATED ALGEBRAS
• Noncommutative symmetric functions. IV: Quantum linear groups and Hecke algebras at \(q=0\)
• Noncommutative symmetric functions. VII: Free quasi-symmetric functions revisited
• On some properties of the algebra of binary trees
• On the hypoplactic monoid
• Order structure on the algebra of permutations and of planar binary trees
• Ordered structures and partitions
• Permutation statistics and linear extensions of posets
• Permutations, matrices, and generalized Young tableaux
• Primitive elements in a free dendriform algebra
• The Hook Graphs of the Symmetric Group
• The On-Line Encyclopedia of Integer Sequences
• Une généralisation des fonctions quasi-symétriques et des fonctions symétriques non commutatives
• q-hook length formulas for forests

Cited in

(94)

• Troupes, cumulants, and stack-sorting
• A multivariate ``inv hook formula for forests
• Mould calculus, polyhedral cones, and characters of combinatorial Hopf algebras.
• An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms
• A noncommutative cycle index and new bases of quasi-symmetric functions and noncommutative symmetric functions
• Generalized descent patterns in permutations and associated Hopf algebras
• The algebraic combinatorics of snakes
• Noncommutative symmetric functions. VII: Free quasi-symmetric functions revisited
• Duality of graded graphs through operads
• Polynomial realizations of some combinatorial Hopf algebras
• Jump interpolation search trees and symmetric binary numbers
• Hopf algebra structure on packed square matrices.
• Trees, functional equations, and combinatorial Hopf algebras
• Colored operads, series on colored operads, and combinatorial generating systems
• Permutrees
• Representations and identities of Baxter monoids with involution
• Noncommutative Bell polynomials and the dual immaculate basis
• The Hopf algebra of diagonal rectangulations.
• Crystals and trees: quasi-Kashiwara operators, monoids of binary trees, and Robinson-Schensted-type correspondences
• Structure of the Loday-Ronco Hopf algebra of trees.
• Representations and identities of hypoplactic monoids with involution
• Quotientopes
• Pluriassociative algebras. II: The polydendriform operad and related operads.
• Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions
• Hopf algebras on decorated noncrossing arc diagrams
• Three Fuss-Catalan posets in interaction and their associative algebras
• Algebraic structures on integer posets
• The monoids of the patience sorting algorithm
• Hopf algebras of \(m\)-permutations, \((m + 1)\)-ary trees, and \(m\)-parking functions
• Cambrian Hopf algebras
• Plactic-like monoids arising from meets and joins of stalactic and taiga congruences
• Lattices of varieties of plactic-like monoids
• Compatibility fans for graphical nested complexes
• Counting smaller elements in the Tamari and \(m\)-Tamari lattices
• Commutative combinatorial Hopf algebras.
• Identities and bases in the hypoplactic monoid
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Algebraic structures on graph associahedra
• New identities in dendriform algebras
• A set-operad of formal fractions and dendriform-like sub-operads
• Forest polynomials and the class of the permutahedral variety
• Weak Bruhat order on the set of faces of the permutohedron and the associahedron.
• scientific article; zbMATH DE number 7203483 (Why is no real title available?)
• Young-Fibonacci insertion, tableauhedron and Kostka numbers
• Algebraic and combinatorial structures on pairs of twin binary trees
• Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids.
• Finite basis problems for stalactic, taiga, sylvester and baxter monoids
• Generalized Schur operators on planar binary trees
• Combinatorial Hopf algebras from PROs
• On some properties of the algebra of binary trees
• An analogue of the plactic monoid for binary search trees
• Order structure on the algebra of permutations and of planar binary trees
• Intervals of balanced binary trees in the Tamari lattice
• The pop-stack-sorting operator on Tamari lattices
• Implementing geometric algebra products with binary trees
• The \(s\)-weak order and \(s\)-permutahedra. II: The combinatorial complex of pure intervals
• Decompositions of packed words and self duality of word quasisymmetric functions
• Three interacting families of Fuss-Catalan posets
• Brick polytopes, lattice quotients, and Hopf algebras
• Linear compactness and combinatorial bialgebras
• Identities and bases in the Sylvester and Baxter monoids
• Lie Theory for Quasi-Shuffle Bialgebras
• The product of trees in the Loday-Ronco algebra through Catalan alternative tableaux
• Identities in plactic, hypoplactic, sylvester, Baxter, and related monoids
• scientific article; zbMATH DE number 2051148 (Why is no real title available?)
• Hopf dreams and diagonal harmonics
• On (non-) freeness of some tridendriform algebras
• The \((1-\mathbb{E})\)-transform in combinatorial Hopf algebras
• scientific article; zbMATH DE number 844505 (Why is no real title available?)
• Acyclic reorientation lattices and their lattice quotients
• Combinatorial operads from monoids
• A one-parameter family of dendriform identities.
• Duplicial algebras, parking functions, and Lagrange inversion
• Quadri-algebras, preLie algebras, and the Catalan family of Lie idempotents
• Representations and identities of plactic-like monoids
• Construction of dendriform trialgebras.
• Tropical representations and identities of the stylic monoid
• A geometric algebra implementation using binary tree
• Meeting covered elements in \(\nu\)-Tamari lattices
• The \(s\)-weak order and \(s\)-permutahedra. I: Combinatorics and lattice structure
• Lattice congruences, fans and Hopf algebras.
• Chinese syzygies by insertions
• Combinatorics of cyclic shifts in plactic, hypoplactic, Sylvester, Baxter, and related monoids
• Tree expansion in time-dependent perturbation theory
• Rectangulotopes
• Polytopal realizations and Hopf algebra structures for lattice quotients of the weak order
• On a ternary operad connected to the Tamari lattice
• Celebrating Loday's associahedron
• On Postnikov's hook length formula for binary trees
• Le module dendriforme sur le groupe cyclique
• Deciding conjugacy in Sylvester monoids and other homogeneous monoids.
• An equivalence of multistatistics on permutations
• Combinatorics of patience sorting monoids

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The algebra of binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557924)