For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Searching in Preorder Trees and Its Evaluation
Mamoru HOSHI Toshitsugu YUBA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1978/01/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Full Text: PDF>>
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.