Searching in Preorder Trees and Its Evaluation

Mamoru HOSHI  Toshitsugu YUBA  

IEICE TRANSACTIONS (1976-1990)   Vol.E61   No.1   pp.8-14
Publication Date: 1978/01/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Computers

Full Text: PDF>>
Buy this Article

We propose a preorder tree which satisfies an order relation: Keys placed at nodes appear in lexicographic order, when the tree is traversed in preorder. Algorithms for search, insertion and deletion are given. The number of key comparisons in the search is investigated theoretically and by simulation studies and compared with the case of binary search trees. We also give an algorithm for constructing a preorder tree which minimizes the number of key comparisons. Simulation experiments confirm the effectiveness of optimization.