TAILIEUCHUNG - Thuật toán Algorithms (Phần 23)

Tham khảo tài liệu 'thuật toán algorithms (phần 23)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 17. Radix Searching Several searching methods proceed by examining the search keys one bit at a time rather than using full comparisons between keys at each step . These methods called radix searching methods work with the bits of the keys themselves as opposed to the transformed version of the keys used in hashing. As with radix sorting methods these methods can be useful when the bits of the search keys are easily accessible and the values of the search keys are well distributed. The principal advantages of radix searching methods are that they provide reasonable worst-case performance without the complication of balanced trees they provide an easy way to handle variable-length keys some allow some savings in space by storing part of the key within the search structure and they can provide very fast access to data competitive with both binary search trees and hashing. The disadvantages are that biased data can lead to degenerate trees with bad performance and data comprised of characters is biased and that some of the methods can make very inefficient use of space. Also as with radix sorting these methods are designed to take advantage of particular characteristics of the computer s architecture since they use digital properties of the keys it s difficult or impossible to do efficient implementations in languages such as Pascal. We ll examine a series of methods each one correcting a problem inherent in the previous one culminating in an important method which is quite useful for searching applications where very long keys are involved. In addition we ll see the analogue to the linear-time sort of Chapter 10 a constant-time search which is based on the same principle. Digital Search Trees The simplest radix search method is digital tree searching the algorithm is precisely the same as that for binary tree searching except that rather than 213 214 CHAPTER 17 branching in the tree based on the result of the comparison between the keys we branch according to the key

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.