Use of Doubly Chained Tree Structures in File Organisation for Optimal Searching
Francis Suraweera · The Computer Journal · 1986
The problem of minimising the search length (time) associated with a variable length, doubly chained tree structure with weighted terminal nodes and its implications on the organisation of a file are investigated. The main result is an algorithm which constructs an optimal doubly chained tree as a static data structure. Also considered are a few ramifications, particularly when the search steps have unequal costs. The supporting activity of file maintenance is also discussed. Two methods of updating a data file organised as a doubly chained tree structures are presented, which allow the realisation of a dynamic data structure.