A note on the Horton-Strahler number for random trees
type: Item
instance of: scholarly article
title: A note on the Horton-Strahler number for random trees
zbMATH Open document ID: 0809.05031
DOI: 10.1016/0020-0190(94)00135-9
author: Paul Kruszewski
author: Luc Devroye
published in: Information Processing Letters
publication date: 1994-11-20T00:00:00Z
review text: The Horton-Strahler number \(S(T)\) of a binary tree \(T\) is defined recursively as follows. If \(T\) is the trivial tree then \(S(T)= 1\); and if \(T\) is a non-trivial tree with main branches \(L\) and \(R\) then \(S(T)\) equals \(\max\{S(L),S(R)\}\) if \(S(L)\neq S(R)\) and \(S(L)+1\) otherwise. Let \(S_ n\) denote the Horton-Strahler number of a random equiprobable binary tree with \(n\) nodes. The authors extend known results by showing that there exists a constant \(C>0\) such that \(Pr\{| S_ n- \log_ 4 n|\geq x\}\leq C\cdot 4^{-x}\) for all \(x>0\).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 691036
zbMATH Keywords: random trees
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: Horton-Strahler number
zbMATH Keywords: binary tree
reviewed by: J. W. Moon
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00135-9
OpenAlex ID: W4245945537
cites work: On programming of arithmetic operations
cites work: The number of registers required for evaluating arithmetic expressions
cites work: Q3339285
cites work: The average number of registers needed to evaluate a binary tree optimally
cites work: On the Order of Random Channel Networks
cites work: On Horton's Law for Random Channel Networks
cites work: Q3703700
cites work: Q4027617
description: scientific article; zbMATH DE number 691036