Internal path length of the binary representation of heap-ordered trees

We show that the average internal path length of the binary representation of a random n-node heap-ordered tree is asymptotically n πn −2n + O( n ) .

Saved in:
Bibliographic Details
Published in:Information processing letters 1994-08, Vol.51 (3), p.129-132
Main Authors: Chen, Wen-Chin, Ni, Wen-Chun
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Binomial distribution
Combinatorial enumeration
Computer science
control theory
systems
Data structures
Decision trees
Exact sciences and technology
Generating functions
Heap-ordered trees
Information processing
Internal path length
Mathematical models
Probability
Queuing theory
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the average internal path length of the binary representation of a random n-node heap-ordered tree is asymptotically n πn −2n + O( n ) .
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(94)00081-6