Thumbnail
Access Restriction
Subscribed

Author Zerling, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1985
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A new algorithm that, for the first time, exploits the rotational geometry of binary trees is developed in order to allow for the lexicographic generation of computer representations of these trees in average time $\textit{O}(1)$ per tree. “Rotation” codewords for these trees (in average time $\textit{O}(1)$ per tree) are also generated. It is shown how these codewords relate to lattice paths, and, using this relationship, that $\textit{n}(\textit{n}$ - $1)/(\textit{n}$ + 2) is the average number of rotations needed to generate a binary tree on $\textit{n}$ nodes. Finally, a necessary and sufficient condition that a codeword represent a full binary tree (each node has 0 or 2 sons) on $\textit{n}$ = $2\textit{m}$ + 1 nodes is given and how to contract this codeword to obtain the codeword for the binary tree on $\textit{m}$ nodes for which this full tree is the extended binary tree is shown.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1985-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 32
Issue Number 3
Page Count 8
Starting Page 694
Ending Page 701


Open content in new tab

   Open content in new tab
Source: ACM Digital Library