Searching in Preorder Trees and Its Evaluation
Summary :
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.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E61-E No.1 pp.8-14
- Publication Date
- 1978/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Computers
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mamoru HOSHI, Toshitsugu YUBA, "Searching in Preorder Trees and Its Evaluation" in IEICE TRANSACTIONS on transactions,
vol. E61-E, no. 1, pp. 8-14, January 1978, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e61-e_1_8/_p
Copy
@ARTICLE{e61-e_1_8,
author={Mamoru HOSHI, Toshitsugu YUBA, },
journal={IEICE TRANSACTIONS on transactions},
title={Searching in Preorder Trees and Its Evaluation},
year={1978},
volume={E61-E},
number={1},
pages={8-14},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Searching in Preorder Trees and Its Evaluation
T2 - IEICE TRANSACTIONS on transactions
SP - 8
EP - 14
AU - Mamoru HOSHI
AU - Toshitsugu YUBA
PY - 1978
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E61-E
IS - 1
JA - IEICE TRANSACTIONS on transactions
Y1 - January 1978
AB - 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.
ER -
English
