Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Extremal properties of random trees.

E Ben-Naim1, P L Krapivsky, S N Majumdar

  • 1Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 3, 2001
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Finite-time blowup of a Brownian particle in a repulsive potential.

Physical review. E·2025
Same author

Self-Reinforcing Cascades: A Spreading Model for Beliefs or Products of Varying Intensity or Quality.

Physical review letters·2025
Same author

Expansion into the vacuum of stochastic gases with long-range interactions.

Physical review. E·2025
Same author

Templating aggregation.

Physical review. E·2025
Same author

Universal dynamics of a passive particle driven by Brownian motion.

Physical review. E·2025
Same author

Current fluctuations in the Dyson gas.

Physical review. E·2025

Researchers studied the maximal and minimal heights of random binary trees. The study found that extremal heights follow a traveling wave distribution, with expected heights growing logarithmically with tree size.

Area of Science:

  • Computer Science
  • Statistical Physics
  • Probability Theory

Background:

  • Random binary trees are fundamental structures in computer science and combinatorics.
  • Understanding the statistical properties of tree heights is crucial for algorithm analysis and data structure design.

Purpose of the Study:

  • To investigate the extremal statistical properties, specifically maximal and minimal heights, of randomly generated binary trees.
  • To analyze the asymptotic behavior and distribution of these extremal heights.

Main Methods:

  • Analysis of master evolution equations governing tree height distributions.
  • Derivation of analytical expressions for statistical characteristics of extremal heights.
  • Asymptotic analysis of tree height distributions.

Related Experiment Videos

Main Results:

  • The cumulative distribution of extremal heights approaches a traveling wave form.
  • The expected minimal and maximal heights exhibit logarithmic growth with tree size N (h(min) ~ 0.374 ln N, h(max) ~ 4.311 ln N).
  • Corrections to asymptotic behavior are of the order O(ln ln N).

Conclusions:

  • Extremal heights of random binary trees display predictable statistical properties.
  • The traveling wave form provides a robust model for understanding height distributions.
  • Logarithmic growth of extremal heights offers insights into the scalability of binary tree structures.