tailieunhanh - CHƯƠNG 11: CÁC CÂY TÌM KIẾM CÂN BẰNG

Trong mục chúng ta đã nghiên cứu CTDL cây tìm kiếm nhị phân và sử dụng CTDL này để cài đặt KDLTT tập động. Chúng ta đã chỉ ra rằng, các phép toán tập động trên cây tìm kiếm nhị phân, trong trường hợp xấu nhất, sẽ đòi hỏi thời gian O(n), trong đó n là số đỉnh của cây. Đó là trường hợp cây suy biến thành danh sách liên kết, tức là tất cả các nhánh trái (phải) của mọi đỉnh đều rỗng | Khi một KDLTT được cài đặt và được sử dụng trong một chương trình áp dụng thì thông thường là một dãy các phép toán của kiểu dữ liệu đó sẽ được thực hiện, chứ ít khi chỉ thực hiện một vài phép toán . Nhưng từ trước đến nay, ta mới chỉ quan tâm đánh giá thời gian chạy của mỗi phép toán riêng biệt, và cụ thể là đánh giá thời gian chạy trong trường hợp xấu nhất và thời gian chạy trung bình của mỗi phép toán. Chúng ta có thể đánh giá thời gian chạy trong trường hợp xấu nhất của một dãy phép toán bằng phương pháp đơn giản sau. Đánh giá thời gian chạy trong trường hợp xấu nhất của mỗi phép toán trong dãy, sau đó lấy tổng để nhận được cận trên của thời gian chạy trong trường hợp xấu nhất của cả dãy phép toán. Tuy nhiên cách đánh giá này là quá thô, bởi vì khi một phép toán được thực hiện, nó có thể làm thay đổi vị trí của các dữ liệu trong cấu trúc và do đó có thể làm cho trường hợp xấu nhất của các phép toán được thực hiện sau không xảy ra. Như vậy thời gian chạy thực tế trong trường hợp xấu nhất của một dãy phép toán có thể thấp hơn nhiều so với tổng thời gian chạy trong trường hợp xấu nhất của mỗi phép toán trong dãy.