{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T05:22:14Z","timestamp":1736659334966,"version":"3.32.0"},"reference-count":8,"publisher":"Wiley","issue":"11","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4746,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1993,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [<jats:italic>k<\/jats:italic>] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[<jats:italic>k<\/jats:italic>] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[<jats:italic>k<\/jats:italic>] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.<\/jats:p>","DOI":"10.1002\/spe.4380231106","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T20:18:09Z","timestamp":1163794689000},"page":"1267-1283","source":"Crossref","is-referenced-by-count":0,"title":["ISA [<i>k<\/i>] trees: A class of binary search trees with minimal or near minimal internal path length"],"prefix":"10.1002","volume":"23","author":[{"given":"Faris N.","family":"Abuali","sequence":"first","affiliation":[]},{"given":"Roger L.","family":"Wainwright","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"volume-title":"The Art of Computer Programming, vol. 3, Sorting and Searching","year":"1973","author":"Knuth D. E.","key":"e_1_2_1_2_2"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/358476.358509"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/358105.358191"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/6592.6599"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/42411.42421"},{"issue":"2","key":"e_1_2_1_8_2","first-page":"79","article-title":"Technical correspondence on Gerasch's insertion algorithm","volume":"34","author":"Richard I.","year":"1991","journal-title":"Commun. ACM"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"F. N.AbualiandR. L.Wainwright \u2018Fringe analysis of binary search trees with minimal internal path length\u2019 Proceedings of the 1991 Computer Science Conference San Antonio Texas 5\u20137 March 1991 pp.61\u201370.","DOI":"10.1145\/327164.327208"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380231106","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380231106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:56:18Z","timestamp":1736639778000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380231106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,11]]},"references-count":8,"journal-issue":{"issue":"11","published-print":{"date-parts":[[1993,11]]}},"alternative-id":["10.1002\/spe.4380231106"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380231106","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"type":"print","value":"0038-0644"},{"type":"electronic","value":"1097-024X"}],"subject":[],"published":{"date-parts":[[1993,11]]}}}