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




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.


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