Premium
ISA [ k ] trees: A class of binary search trees with minimal or near minimal internal path length
Author(s) -
Abuali Faris N.,
Wainwright Roger L.
Publication year - 1993
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380231106
Subject(s) - successor cardinal , weight balanced tree , binary search tree , ternary search tree , path (computing) , binary tree , node (physics) , binary number , combinatorics , mathematics , path length , class (philosophy) , random binary tree , computer science , algorithm , arithmetic , tree structure , interval tree , artificial intelligence , physics , computer network , quantum mechanics , mathematical analysis
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 [ k ] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[ k ] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[ k ] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.