On rotations in fringe-balanced binary trees
From MaRDI portal
Publication:293176
DOI10.1016/S0020-0190(97)00184-1zbMath1339.68057OpenAlexW1997146555MaRDI QIDQ293176
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097001841?np=y
Related Items (14)
The Class of Tenable Zero-Balanced Pólya Urn Schemes: Characterization and Gaussian Phases ⋮ Occupancy urn models in the analysis of algorithms ⋮ The characterization of tenable Pólya urns ⋮ Effective splaying with restricted rotations ⋮ Balancing \(m\)-ary search trees with compressions on the fringe ⋮ First-passage properties of the Pólya urn process ⋮ Phase changes in randomm-ary search trees and generalized quicksort ⋮ Random sprouts as internet models, and Pólya processes ⋮ Analytic urns ⋮ An almost sure result for path lengths in binary search trees ⋮ DRAWING MULTISETS OF BALLS FROM TENABLE BALANCED LINEAR URNS ⋮ Functional limit theorems for multitype branching processes and generalized Pólya urns. ⋮ An analytic approach for the analysis of rotations in fringe-balanced binary search trees ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic analysis of bucket recursive trees
- Martingale functional central limit theorems for a generalized Pólya urn
- Improving time and space efficiency in generalized binary search trees
- Some average measures in m-ary search trees
- On the distribution of leaves in rooted subtrees of recursive trees
- On random 2-3 trees
- A martingale approach to strong convergence in a generalized Pólya- Eggenberger urn model
- Central limit theorems for urn models
- Functionals of critical multitype branching processes
- Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are Unreliable
- Limit laws for local counters in random binary search trees
- Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
- Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
- The analysis of a fringe heuristic for binary search trees
- Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
- Locally balanced binary trees
- On the structure of random plane‐oriented recursive trees and their branches
- The theory of fringe analysis and its application to 23 trees and b-trees
- Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems
- Binary Search Trees of Bounded Balance
This page was built for publication: On rotations in fringe-balanced binary trees
