n South African Computer Journal - Comparing leaf and root insertion : reviewed article
|Article Title||Comparing leaf and root insertion : reviewed article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||Jaco Geldenhuys and Brink Van der Merwe|
|Publication Date||Dec 2009|
|Pages||30 - 38|
|Keyword(s)||Binary search trees, Leaf insertion and Root insertion|
We consider two ways inserting a key into a binary 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 , 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...