Comparing leaf and root insertion
Date
2009
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
South African Institute of Computer Scientists and Information Technologists
Abstract
We consider two ways of inserting a key into a binary search tree: leaf insertion which is the standard method,
and root insertion which involves additional rotations. Although the respective cost of constructing leaf and root
insertion binary search trees trees, in terms of comparisons, are the same in the average case, we show that in
the worst case the construction of a root insertion binary search tree needs approximately 50% of the number of
comparisons required by leaf insertion.
Description
CITATION: Geldenhuys, J. & Van der Merwe, B. 2009. Comparing leaf and root insertion. South African Computer Journal, 44:30-38, doi:10.18489/sacj.v44i0.21.
The original publication is available at http://sacj.cs.uct.ac.za
The original publication is available at http://sacj.cs.uct.ac.za
Keywords
Computer programming, Binary search tree
Citation
Geldenhuys, J. & Van der Merwe, B. 2009. Comparing leaf and root insertion. South African Computer Journal, 44:30-38, doi:10.18489/sacj.v44i0.21.