Recursive PGFs for BSTs and DSTs
From MaRDI portal
Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Exact enumeration problems, generating functions (05A15) Searching and sorting (68P10) Enumeration in graph theory (05C30) Probability theory (educational aspects) (97K50) Mathematical programming (educational aspects) (97N60)
Abstract: We review fundamentals underlying binary search trees and digital search trees, with (atypical) emphasis on recursive formulas for associated probability generating functions. Other topics include higher moments of BST search costs and combinatorics for a certain finite-key analog of DSTs.
This page was built for publication: Recursive PGFs for BSTs and DSTs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6334322)
