Recursive PGFs for BSTs and DSTs
From MaRDI portal
Exact enumeration problems, generating functions (05A15) Trees (05C05) Enumeration in graph theory (05C30) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) 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)
