scientific article
From MaRDI portal
Publication:4004056
zbMath0762.68033MaRDI QIDQ4004056
Publication date: 18 September 1992
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Data structures (68P05)
Related Items
Weakly protected nodes in random binary search trees ⋮ Simply generated trees, B-series and Wigner processes ⋮ A SPECTRUM OF SERIES–PARALLEL GRAPHS WITH MULTIPLE EDGE EVOLUTION ⋮ Pruned Discrete Random Samples ⋮ On random cartesian trees ⋮ Transfer theorems and asymptotic distributional results for m‐ary search trees ⋮ Greedy Search on the Binary Tree with Random Edge-Weights ⋮ Generalized Digital Trees and Their Difference—Differential Equations ⋮ An Improved Bound for Random Binary Search Trees with Concurrent Insertions ⋮ The strong convergence of maximal degrees in uniform random recursive trees and dags ⋮ The variance of a partial match retrieval in a multidimensional symmetric trie ⋮ Hypergeometrics and the cost structure of quadtrees ⋮ Node profiles of symmetric digital search trees: Concentration properties ⋮ Analysis of quickselect : an algorithm for order statistics ⋮ DEGREE PROFILE OF m-ARY SEARCH TREES: A VEHICLE FOR DATA STRUCTURE COMPRESSION ⋮ Balancing \(m\)-ary search trees with compressions on the fringe ⋮ Degree distributions in recursive trees with fitnesses ⋮ An Analysis of the Height of Tries with Random Weights on the Edges ⋮ A Mathematical Connection Between Single-Elimination Sports Tournaments and Evolutionary Trees ⋮ Limit distribution of the quartet balance index for Aldous’s $(\beta \ge 0)$-model ⋮ Cutting Edges at Random in Large Recursive Trees ⋮ The move-to-root rule for self-organizing trees with Markov dependent requests∗ ⋮ Profiles of random trees: correlation and width of random recursive trees and binary search trees ⋮ Trees grown under young-age preferential attachment ⋮ On the Variety of Shapes on the Fringe of a Random Recursive Tree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dependence and phase changes in random m‐ary search trees ⋮ Properties of phylogenetic trees generated by Yule-type speciation models ⋮ The climbing depth of random trees ⋮ On the Subtree Size Profile of Binary Search trees ⋮ Level of nodes in increasing trees revisited ⋮ Dependence between path-length and size in random digital trees ⋮ The stack-size of tries: A combinatorial study ⋮ The variance of the height of binary search trees ⋮ On 2-protected nodes in random digital trees ⋮ Profile of Tries ⋮ On the internal path length ofd-dimensional quad trees ⋮ A family of random trees with random edge lengths ⋮ Random suffix search trees ⋮ An almost sure result for path lengths in binary search trees ⋮ Multiple choice tries and distributed hash tables ⋮ m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements ⋮ One-sided variations on interval trees ⋮ Refined quicksort asymptotics ⋮ Upper tail analysis of bucket sort and random tries ⋮ Upper tail analysis of bucket sort and random tries ⋮ Partial match queries in random quadtrees ⋮ Ancestors and descendants in evolving k‐tree models ⋮ Universal Limit Laws for Depths in Random Trees ⋮ On the asymptotic behaviour of random recursive trees in random environments ⋮ A binomial splitting process in connection with corner parking problems ⋮ The Wiener Index of Random Digital Trees ⋮ Distribution of distances in random binary search trees. ⋮ The profile of binary search trees ⋮ Limit laws for partial match queries in quadtrees ⋮ Solutions to complex smoothing equations ⋮ The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees ⋮ Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ On the number of full levels in tries ⋮ Spanning tree size in random binary search trees. ⋮ One-sided variations on binary search trees ⋮ Reductions in binary search trees ⋮ On rotations in fringe-balanced binary trees ⋮ On the richness of the collection of subtrees in random binary search trees ⋮ Paths in \(m\)-ary interval trees ⋮ Average case analysis for tree labelling schemes ⋮ Central limit theorems for additive functionals and fringe trees in tries ⋮ On the contraction method with degenerate limit equation. ⋮ Stochastic analysis of the extra clustering model for animal grouping ⋮ On the distribution for the duration of a randomized leader election algorithm ⋮ Distances in random digital search trees ⋮ Phase transition in a generalized Eden growth model on a tree ⋮ Rounding of continuous random variables and oscillatory asymptotics ⋮ Profile of random exponential binary trees ⋮ The left-right-imbalance of binary search trees ⋮ Analytic methods in asymptotic enumeration ⋮ Limit distributions of the number of vertices of a given out-degree in a random forest ⋮ Large deviations for combinatorial distributions. I: Central limit theorems ⋮ Average-case analysis of multiple Quickselect: An algorithm for finding order statistics ⋮ Continued fraction algorithms, functional operators, and structure constants ⋮ Analytical depoissonization and its applications ⋮ A limit process for partial match queries in random quadtrees and 2-d trees ⋮ Equality of Shapley value and fair proportion index in phylogenetic trees ⋮ Retracted: Strong limiting behavior in binary search trees ⋮ Continuous-time digital search tree and a border aggregation model ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ Emerging behavior as binary search trees are symmetrically updated. ⋮ Asymptotic expectation of protected node profile in random digital search trees ⋮ Long and short paths in uniform random recursive dags ⋮ Analysis of a drop-push model for percolation and coagulation ⋮ General Edgeworth expansions with applications to profiles of random trees ⋮ The \(m\)-version of binary search trees: an average case analysis ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Combinatiorial Markov chains ⋮ Trees with exponentially growing costs ⋮ Refined asymptotics for the composition of cyclic urns ⋮ Maximal flow in branching trees and binary search trees ⋮ Limit distributions for multitype branching processes of \(m\)-ary search trees ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ Search trees: metric aspects and strong limit theorems ⋮ Renewals for exponentially increasing lifetimes, with an application to digital search trees ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ Mellin transforms and asymptotics: Harmonic sums ⋮ Mellin transforms and asymptotics: Finite differences and Rice's integrals ⋮ Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees ⋮ Probabilistic analysis of bucket recursive trees ⋮ On the variance of a class of inductive valuations of data structures for digital search ⋮ A note on binomial recurrences arising in the analysis of algorithms ⋮ Page usage in a quadtree index ⋮ A functional limit theorem for the profile of search trees ⋮ Average-case analysis on simple families of trees using a balanced probability model ⋮ Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ The expected profile of digital search trees ⋮ Limiting distributions for additive functionals on Catalan trees ⋮ On the Stack-Size of General Tries ⋮ D?E?K=(1000)8 ⋮ Size and path length of Patricia tries: Dynamical sources context ⋮ Phase changes in randomm-ary search trees and generalized quicksort ⋮ On a multivariate contraction method for random recursive structures with applications to Quicksort ⋮ On Robson's convergence and boundedness conjectures concerning the height of binary search trees ⋮ Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees ⋮ Uniform distribution modulo one and binary search trees ⋮ The oscillatory distribution of distances in random tries ⋮ Mixed Poisson approximation of node depth distributions in random binary search trees ⋮ A probabilistic analysis of some tree algorithms ⋮ Asymptotic distribution of two-protected nodes in random binary search trees ⋮ On the silhouette of binary search trees ⋮ Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model ⋮ Analytic urns ⋮ A functional limit theorem for the profile of \(b\)-ary trees ⋮ On finding a minimum spanning tree in a network with random weights ⋮ The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance ⋮ Width and mode of the profile for some random trees of logarithmic height ⋮ Toward a Formal Derivation of the Expected Behavior of Prefix B-Trees ⋮ On weighted depths in random binary search trees ⋮ Ascents and descents in random trees ⋮ Branching random walks on binary search trees: convergence of the occupation measure ⋮ Limit laws for the Randić index of random binary tree models ⋮ The number of winners in a discrete geometrically distributed sample ⋮ Imbalance in random digital trees ⋮ Renewal theory in the analysis of tries and strings ⋮ On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach ⋮ Probabilistic analysis of algorithms for the Dutch national flag problem ⋮ Normality of tree-growing search strategies ⋮ Functional limit theorems for multitype branching processes and generalized Pólya urns. ⋮ The height of a binary search tree: the limiting distribution perspective. ⋮ Extreme value statistics and traveling fronts: Various applications ⋮ On joint properties of vertices with a given degree or label in the random recursive tree ⋮ Psi-series method for equality of random trees and quadratic convolution recurrences ⋮ Asymptotic analysis of a class of functional equations and applications ⋮ On the expected height of fringe-blanced trees
