ITEM VIEW

Comparing leaf and root insertion

dc.contributor.authorGeldenhuys, Jacoen_ZA
dc.contributor.authorVan der Merwe, Brinken_ZA
dc.date.accessioned2019-10-22T10:24:20Z
dc.date.available2019-10-22T10:24:20Z
dc.date.issued2009
dc.identifier.citationGeldenhuys, J. & Van der Merwe, B. 2009. Comparing leaf and root insertion. South African Computer Journal, 44:30-38, doi:10.18489/sacj.v44i0.21.
dc.identifier.issn2313-7835 (online)
dc.identifier.otherdoi:10.18489/sacj.v44i0.21
dc.identifier.urihttp://hdl.handle.net/10019.1/106691
dc.descriptionCITATION: 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.
dc.descriptionThe original publication is available at http://sacj.cs.uct.ac.za
dc.description.abstractWe 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.en_ZA
dc.description.urihttp://sacj.cs.uct.ac.za/index.php/sacj/article/view/21
dc.format.extent9 pages
dc.language.isoen_ZAen_ZA
dc.publisherSouth African Institute of Computer Scientists and Information Technologists
dc.subjectComputer programmingen_ZA
dc.subjectBinary search treeen_ZA
dc.titleComparing leaf and root insertionen_ZA
dc.typeArticleen_ZA
dc.description.versionPublisher's version
dc.rights.holderAuthors retain copyright


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

ITEM VIEW