n South African Computer Journal - Comparing leaf and root insertion : reviewed article

Volume 2009, Issue 44
  • ISSN : 1015-7999
  • E-ISSN: 2313-7835



We consider two ways inserting a key into a binary tree: which is the standard method, and which involves additional rotations. Although the respective cost of constructing leaf and root insertion binary search trees , in terms of comparisons, are the same 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.

Loading full text...

Full text loading...


Article metrics loading...


This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error