The algebra of binary search trees
From MaRDI portal
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
Cites work
- 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
- 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?)
- 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
- q-hook length formulas for forests
- 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
Cited in
(only showing first 100 items - show all)- Young-Fibonacci insertion, tableauhedron and Kostka numbers
- A one-parameter family of dendriform identities.
- Commutative combinatorial Hopf algebras.
- Jump interpolation search trees and symmetric binary numbers
- An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms
- On some properties of the algebra of binary trees
- Order structure on the algebra of permutations and of planar binary trees
- Hopf algebras on decorated noncrossing arc diagrams
- Noncommutative Bell polynomials and the dual immaculate basis
- Identities in plactic, hypoplactic, sylvester, Baxter, and related monoids
- Brick polytopes, lattice quotients, and Hopf algebras
- A geometric algebra implementation using binary tree
- Crystals and trees: quasi-Kashiwara operators, monoids of binary trees, and Robinson-Schensted-type correspondences
- An equivalence of multistatistics on permutations
- Algebraic and combinatorial structures on pairs of twin binary trees
- An analogue of the plactic monoid for binary search trees
- Colored operads, series on colored operads, and combinatorial generating systems
- Duality of graded graphs through operads
- Linear compactness and combinatorial bialgebras
- Meeting covered elements in -Tamari lattices
- Chinese syzygies by insertions
- Troupes, cumulants, and stack-sorting
- Representations and identities of plactic-like monoids
- Three interacting families of Fuss-Catalan posets
- A noncommutative cycle index and new bases of quasi-symmetric functions and noncommutative symmetric functions
- Combinatorial operads from monoids
- 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
- Combinatorics of patience sorting monoids
- Combinatorics of cyclic shifts in plactic, hypoplactic, Sylvester, Baxter, and related monoids
- Hopf algebra structure on packed square matrices.
- Counting smaller elements in the Tamari and \(m\)-Tamari lattices
- Structure of the Loday-Ronco Hopf algebra of trees.
- A multivariate ``inv hook formula for forests
- Compatibility fans for graphical nested complexes
- Cambrian Hopf algebras
- Generalized descent patterns in permutations and associated Hopf algebras
- Polynomial realizations of some combinatorial Hopf algebras
- Weak Bruhat order on the set of faces of the permutohedron and the associahedron.
- Algebraic structures on integer posets
- The pop-stack-sorting operator on Tamari lattices
- Quadri-algebras, preLie algebras, and the Catalan family of Lie idempotents
- Tropical representations and identities of the stylic monoid
- Pluriassociative algebras. II: The polydendriform operad and related operads.
- Deciding conjugacy in Sylvester monoids and other homogeneous monoids.
- A set-operad of formal fractions and dendriform-like sub-operads
- Combinatorial Hopf algebras from PROs
- Lie Theory for Quasi-Shuffle Bialgebras
- Generalized Schur operators on planar binary trees
- Mould calculus, polyhedral cones, and characters of combinatorial Hopf algebras.
- The algebraic combinatorics of snakes
- scientific article; zbMATH DE number 2051148 (Why is no real title available?)
- The monoids of the patience sorting algorithm
- scientific article; zbMATH DE number 844505 (Why is no real title available?)
- Quotientopes
- Identities and bases in the hypoplactic monoid
- Pop-stack-sorting for Coxeter groups
- Stack-sorting for Coxeter groups
- Three Fuss-Catalan posets in interaction and their associative algebras
- scientific article; zbMATH DE number 7203483 (Why is no real title available?)
- On (non-) freeness of some tridendriform algebras
- Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids.
- Tree expansion in time-dependent perturbation theory
- Lattice congruences, fans and Hopf algebras.
- Permutrees
- Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions
- Finite basis problems for stalactic, taiga, sylvester and baxter monoids
- Algebraic structures on graph associahedra
- 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
- The product of trees in the Loday-Ronco algebra through Catalan alternative tableaux
- The \((1-\mathbb{E})\)-transform in combinatorial Hopf algebras
- Lattices of varieties of plactic-like monoids
- Noncommutative symmetric functions. VII: Free quasi-symmetric functions revisited
- Forest polynomials and the class of the permutahedral variety
- On a ternary operad connected to the Tamari lattice
- Plactic-like monoids arising from meets and joins of stalactic and taiga congruences
- 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
- The Hopf algebra of diagonal rectangulations.
- The \(s\)-weak order and \(s\)-permutahedra. I: Combinatorics and lattice structure
- Acyclic reorientation lattices and their lattice quotients
- Rectangulotopes
- On the lattice of the weak factorization systems on a finite lattice
- Acyclic pipe dreams, subword complexes and lattice quotients of weak order intervals
- Power quotients of plactic-like monoids
- Lattices of acyclic pipe dreams
- The ascent lattice on Dyck paths
- Hochschild polytopes
- Clones of pigmented words and realizations of special classes of monoids
- The noncommutative KP hierarchy and its solution via descent algebra
- Separating trees and simple congruences of the weak order
- Combinatorial generation via permutation languages. VII: Supersolvable hyperplane arrangements
- Implementing geometric algebra products with binary trees
- Intervals of balanced binary trees in the Tamari lattice
- Duplicial algebras, parking functions, and Lagrange inversion
- Construction of dendriform trialgebras.
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)
