Tối ưu hoá cây nhị phân một chiều với thông tin chứa ở các đỉnh trong

Đỗ Đức Giáo

Abstract


The notion of a search tree plays an important role in computer science, especially in the theory of data structures. For that reason we can find many papers concerned with the theory of search trees in literature. After having read these papers we noticed that, above all, questions of the optimal construction and inductive generation of search trees are studied, where equivalent transformation of search trees are often used.

In this paper we intend to further develop the conception of search trees in [4]. A prove of a theorem which shows that each binary search tree can be uniquely transformed into optimal binary search tree by using axiom schemes and the rules are introduced in this paper.




DOI: https://doi.org/10.15625/1813-9663/15/4/7784

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology