TAILIEUCHUNG - 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.

• Kỹ thuật lập trình
• cấu trúc dữ liệu cao cấp
• ngôn ngữ lập trình C++
• lập trình hướng đối tượng
• cấu trúc dữ liệu tuyến tính
• cây tìm kiếm cân bằng
• Cấu trúc dữ liệu
• Thuật toán cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Lập trình C++
• Công nghệ thông tin
• Cấu trúc dữ liệu và giải thuật
• Giáo trình Cấu trúc dữ liệu và giải thuật
• Quản trị mạng
• Ngôn ngữ diễn đạt giải thuật
• Bài toán đệ quy
• Cấu trúc danh sách liên kết
• Ngôn ngữ máy
• Assembly languages
• Ngôn ngữ lập trình cấp cao
• Algorithms in pseudo code
• lập trình máy tính
• mẹo lập trình
• ngôn ngữ lập trình
• thủ thuật lập trình
• Lập trình căn bản
• Giáo trình Lập trình căn bản
• Giáo trình nghề Quản trị mạng
• Ngôn ngữ lập trình C
• Ngôn ngữ biểu diễn giải thuật
• Cấu trúc if lồng nhau
• Giáo trình thuật toán
• Lý thuyết và thực hành thuật toán
• Căn bản về toán học
• Sắp xếp và thống kê số liệu
• Kỹ thuật phân tích và thiết kế cao cấp
• Các cấu trúc dữ liệu cao cấp
• toán cao cấp
• toán liệt kê
• giải thuật
• lý thuyết động
• bài toán đồ thị
• định nghĩa hàng đợi
• số nhị phân
• khử đệ qui
• Vận dụng hàng đợi vào các bài toán
• bài toán mỹ
• bài toán cao cấp
• kế toán doanh nghiệp
• bài toán kinh tế
• đề thi quản trị
• Lý thuyết và bài tập
• Cẩm nang thuật toán
• Tư duy toán học
• Sắp xếp và thống kê thứ tự
• Các cấu trúc dữ liệu
• Các kỹ thuật phân tích
• Thiết kế cao cấp
• Thuật toán đồ thị
• Các chủ đề chọn lọc