Computing parent nodes in threaded binary trees

DOI10.1007/BF01935047MaRDI QIDQ1090107zbMATH OpenFDO

Authors Keith Brinck

Publication date 1986

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01935047

zbMATH Keywords

analysis of algorithmsaverage case complexitybinary treesdata structuresparent of a noderecurrence relationsthreaded binary treeworst case complexity

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

We give three algorithms for computing the parent of a node in a threaded binary tree, and calculate the average case complexity of each. By comparing these to the unit cost of obtaining the parent of a node with an explicit parent-pointer field, it is possible to balance runtime and storage cost with respect to the task of finding parent nodes in binary trees. The results obtained shows that, although the worst case complexity for an n-node tree is obviously O(n) for all three algorithms, the average case complexity for two input distributions is asymptotic (from below) to either 3 or 2.

Recommendations

• On deletion in threaded binary trees
• The new design of the threaded binary trees
• A study of binary tree traversal algorithms and a tag-free threaded representation
• The Expected Performance of Traversal Algorithms in Binary Trees
• scientific article; zbMATH DE number 3954287

Cites work

• Analysis of algorithms on threaded trees
• On deletion in threaded binary trees
• The Expected Performance of Traversal Algorithms in Binary Trees

Cited in

(3)

• scientific article; zbMATH DE number 3954287 (Why is no real title available?)
• On deletion in threaded binary trees
• The new design of the threaded binary trees

This page was built for publication: Computing parent nodes in threaded binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090107)