Premium
Efficient algorithms to create and maintain balanced and threaded binary search trees
Author(s) -
Iyengar S. Sitharama,
Chang Hsi
Publication year - 1985
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.4380151002
Subject(s) - binary search tree , thread (computing) , computer science , traverse , binary tree , algorithm , workspace , data structure , binary number , self balancing binary search tree , depth first search , weight balanced tree , ternary search tree , optimal binary search tree , linked list , binary search algorithm , search algorithm , tree structure , mathematics , interval tree , artificial intelligence , programming language , arithmetic , geodesy , robot , geography
The algorithm proposed by Chang and lyengar to perfectly balance binary search trees has been modified to not only balance but also thread binary search trees. Threads are constructed in the same sequence as normal pointers during the balancing process. No extra workspace is necessary, and the running time is also linear for the modified algorithm. Such produced tree structure has minimal average path length for fast information retrieval, and threads to facilitate more flexible and efficient traversing schemes. Maintenance and manipulation of the data structure are discussed and relevant algorithms given.