Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Cây tìm kiếm chuỗi: Phân tích của chúng bằng quan hệ hồi quy
Tóm tắt
Trong bài báo này, chúng tôi đã tính toán số phép so sánh trung bình cần thiết khi tìm kiếm trong một cây tìm kiếm chuỗi tổng quát, là một sự mở rộng của khái niệm cây tìm kiếm nhị phân và tam phân. Phân tích này sử dụng các quan hệ hồi quy và minh họa cách mà các kỹ thuật như vậy hữu ích trong loại vấn đề này.
Từ khóa
#cây tìm kiếm chuỗi #phân tích #quan hệ hồi quy #tìm kiếm nhị phân #tìm kiếm tam phânTài liệu tham khảo
T. N. Hibbard,Some Combinatorial Properties of Certain Trees with Applications to Searching and Sorting, J.A.C.M. Vol. 9 (1962), pp. 13–29.
D. E. Knuth,The Art of Computer Programming. Vol. 3. Sorting and Searching, Addison-Wesley, 1973, pp. 406–457.
W. C. Lynch,More combinatorial properties of certain trees, Computer Journal Vol. 7 (1965), pp. 299–302.
J. L. Szwarcfiter and L. B. Wilson,Some properties of ternary trees, University of New-castle upon Tyne Technical Report No. 79, October 1975.
L. B. Wilson,The Analysis of Sequence Search Trees using Recurrence Relations, University of Newcastle upon Tyne Technical Report No. 76, October 1975.
P. F. Windley,Trees, Forests and Rearranging, Computer Journal, Vol. 3 (1966), pp. 84–88.