The algebra of binary search trees

DOI10.1016/j.tcs.2005.01.012zbMath1072.05052arXivmath/0401089OpenAlexW1966547931MaRDI QIDQ557924

Jean-Christophe Novelli, Florent Hivert, 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 algebrasRepresentation theoryPlactic monoidSymmetric functions

Mathematics Subject Classification ID

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

Related Items (77)

Construction of dendriform trialgebras. ⋮ Hopf algebras on decorated noncrossing arc diagrams ⋮ Pluriassociative algebras. II: The polydendriform operad and related operads. ⋮ Structure of the Loday-Ronco Hopf algebra of trees. ⋮ Noncommutative Bell polynomials and the dual immaculate basis ⋮ Pop-stack-sorting for Coxeter groups ⋮ Stack-sorting for Coxeter groups ⋮ Three Fuss-Catalan posets in interaction and their associative algebras ⋮ A multivariate ``inv hook formula for forests ⋮ A set-operad of formal fractions and dendriform-like sub-operads ⋮ Algebraic structures on integer posets ⋮ Combinatorial Hopf algebras from PROs ⋮ Representations and identities of plactic-like monoids ⋮ Compatibility fans for graphical nested complexes ⋮ Cambrian Hopf algebras ⋮ Identities in plactic, hypoplactic, sylvester, Baxter, and related monoids ⋮ Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions ⋮ Deciding conjugacy in sylvester monoids and other homogeneous monoids ⋮ The pop-stack-sorting operator on Tamari lattices ⋮ Mould calculus, polyhedral cones, and characters of combinatorial Hopf algebras. ⋮ Quadri-algebras, preLie algebras, and the Catalan family of Lie idempotents ⋮ Brick polytopes, lattice quotients, and Hopf algebras ⋮ Finite basis problems for stalactic, taiga, sylvester and baxter monoids ⋮ The canonical complex of the weak order ⋮ Tropical representations and identities of the stylic monoid ⋮ Algebraic structures on graph associahedra ⋮ The \((1-\mathbb{E})\)-transform in combinatorial Hopf algebras ⋮ Celebrating Loday's associahedron ⋮ Representations and identities of Baxter monoids with involution ⋮ Representations and identities of hypoplactic monoids with involution ⋮ Hopf dreams and diagonal harmonics ⋮ Identities and bases in the Sylvester and Baxter monoids ⋮ Three interacting families of Fuss-Catalan posets ⋮ Generalized descent patterns in permutations and associated Hopf algebras ⋮ Crystals and trees: quasi-Kashiwara operators, monoids of binary trees, and Robinson-Schensted-type correspondences ⋮ The algebraic combinatorics of snakes ⋮ A noncommutative cycle index and new bases of quasi-symmetric functions and noncommutative symmetric functions ⋮ Polynomial realizations of some combinatorial Hopf algebras ⋮ The monoids of the patience sorting algorithm ⋮ Noncommutative symmetric functions. VII: Free quasi-symmetric functions revisited ⋮ On a ternary operad connected to the Tamari lattice ⋮ The Hopf algebra of diagonal rectangulations. ⋮ Lie Theory for Quasi-Shuffle Bialgebras ⋮ On Postnikov's hook length formula for binary trees ⋮ Trees, functional equations, and combinatorial Hopf algebras ⋮ New identities in dendriform algebras ⋮ An equivalence of multistatistics on permutations ⋮ Arithmetic for rooted trees ⋮ Colored operads, series on colored operads, and combinatorial generating systems ⋮ Algebraic and combinatorial structures on pairs of twin binary trees ⋮ Combinatorial operads from monoids ⋮ Lattice congruences, fans and Hopf algebras. ⋮ Weak Bruhat order on the set of faces of the permutohedron and the associahedron. ⋮ Permutrees ⋮ Duality of graded graphs through operads ⋮ Le module dendriforme sur le groupe cyclique ⋮ Linear compactness and combinatorial bialgebras ⋮ Young-Fibonacci insertion, tableauhedron and Kostka numbers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quotientopes ⋮ Polytopal realizations and Hopf algebra structures for lattice quotients of the weak order ⋮ Hopf algebras of \(m\)-permutations, \((m + 1)\)-ary trees, and \(m\)-parking functions ⋮ A one-parameter family of dendriform identities. ⋮ Commutative combinatorial Hopf algebras. ⋮ Combinatorics of patience sorting monoids ⋮ Combinatorics of cyclic shifts in plactic, hypoplactic, Sylvester, Baxter, and related monoids ⋮ Intervals of balanced binary trees in the Tamari lattice ⋮ Meeting covered elements in \(\nu\)-Tamari lattices ⋮ Chinese syzygies by insertions ⋮ Duplicial algebras, parking functions, and Lagrange inversion ⋮ Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids ⋮ Tree expansion in time-dependent perturbation theory ⋮ Hopf algebra structure on packed square matrices. ⋮ Counting smaller elements in the Tamari and \(m\)-Tamari lattices ⋮ Identities and bases in the hypoplactic monoid ⋮ Troupes, cumulants, and stack-sorting

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Noncommutative symmetric functions. VII: Free quasi-symmetric functions revisited
• A plactic algebra for semisimple Lie algebras
• q-hook length formulas for forests
• A \(q\)-analogue of \(U(\mathfrak{gl}(N+1))\), Hecke algebra, and the Yang-Baxter equation
• Permutation statistics and linear extensions of posets
• Hopf algebra of the planar binary trees
• Duality of graded graphs
• Noncommutative symmetric functions. IV: Quantum linear groups and Hecke algebras at \(q=0\)
• On some properties of the algebra of binary trees
• Ideals of quasi-symmetric functions and super-covariant polynomials for \(\mathcal S_n\)
• Order structure on the algebra of permutations and of planar binary trees
• An analogue of the plactic monoid for binary search trees
• Crystal graphs and \(q\)-analogues of weight multiplicities for the root system \(A_ n\)
• Duality between quasi-symmetric functions and the Solomon descent algebra
• On the hypoplactic monoid
• Permutations, matrices, and generalized Young tableaux
• Longest Increasing and Decreasing Subsequences
• Combinatorial Hopf algebras and generalized Dehn–Sommerville relations
• Une généralisation des fonctions quasi-symétriques et des fonctions symétriques non commutatives
• NONCOMMUTATIVE SYMMETRIC FUNCTIONS VI: FREE QUASI-SYMMETRIC FUNCTIONS AND RELATED ALGEBRAS
• Ordered structures and partitions
• The Hook Graphs of the Symmetric Group

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