LỜI MỞ ĐẦU Môn học Cấu trúc dữ liệu nâng cao là một môn cơ bản, nền tảng cho mỗi người học và làm về công nghệ thông tin. Trong môn học này, chúng ta được tìm hiểu, nghiên cứu rất nhiều cấu trúc dữ liệu cùng với những ứng dụng của chúng trong thực tế. Với các cây tìm kiếm nhị phân: cây AVL, cây đỏ - đen, cây 2-3 ., đều có các điểm chung là: Các phép toán tìm kiếm (search) không làm thay đổi cấu trúc dữ liệu, khi ta thực hiện các phép toán như: phép chèn (insert), phép xóa (delete), có thể chúng ta phải điều chỉnh cấu trúc dữ liệu cho nó thỏa mãn các điều kiện đã đặt ra của cấu trúc dữ liệu đó. Thường khi tổ chức dữ liệu cũng như khi thực hiện các phép toán trên tập dữ liệu đã được cấu trúc, chúng ta không hề quan tâm tới các dữ liệu nào được truy cập thường xuyên hơn các dữ liệu khác. Mặt khác, chúng ta mong muốn rằng, khi chúng ta truy cập tới một dữ liệu nào đó thì các lần truy cập sau này tới dữ liệu đó sẽ nhanh hơn. Một thực tế nữa là, trong các chương trình áp dụng, rất ít khi chúng ta sử dụng một cấu trúc dữ liệu để biểu diễn một tập dữ liệu mà chỉ thực hiện một vài phép toán trên cấu trúc dữ liệu đó, thông thường cần phải thực hiện một dãy rất lớn các phép toán. Bởi vậy người ta đưa ra ý tưởng: khi thực hiện các phép toán trên một cấu trúc dữ liệu đã lựa chọn, người ta tiến hành điều chỉnh cấu trúc dữ liệu ngay cả đối với các phép toán không đòi hỏi phải điều chỉnh (chẳng hạn: các phép toán tìm kiếm), nhằm làm cho các phép toán thực hiện sau đó sẽ nhanh hơn và do đó có thể giảm thời gian thực hiện một dãy dài các phép toán. Các cấu trúc dữ liệu như thế được gọi là cấu trúc dữ liệu tự điều chỉnh (self-adjusting data structure). Trong phần 1, chúng tôi sẽ giới thiệu cấu trúc dữ liệu tự điều chỉnh của cây nhị phân đặc biệt gọi là splay tree, trong phần này chúng tôi sẽ đưa ra một phương pháp đánh giá thời gian chạy của một dãy phép toán, được gọi là phương pháp phân tích khấu hao (amortized analysis). Phương pháp phân tích khấu hao cho phép ta có thể đánh giá cận trên chặt của thời gian chạy của một dãy phép toán. Phương pháp này thường được sử dụng để đánh giá thời gian chạy của một dãy phép toán trên các cấu trúc dữ liệu tự điều chỉnh. Ở phần 2 của báo cáo chúng tôi sẽ trình bày ứng dụng của cấu trúc splay tree trong nén dữ liệu. Chúng tôi xin trân trọng tỏ lòng biết ơn tới Tiến sĩ Nguyễn Mạnh Hùng - người đã trực tiếp giảng dạy môn học Cấu trúc dữ liệu nâng cao đồng cảm ơn các bạn bè và đồng nghiệp đã nhiệt tình giúp đỡ để tôi hoàn thành bài tập này. Mặc dù đã cố gắng nhưng chắc hẳn tài liệu không tránh khỏi những thiếu sót. Vì vậy chúng tôi rất mong được Thầy cùng các bạn nhận xét và góp ý để tôi được để tài liệu này được hoàn thiện hơn. Chúng tôi xin trân thành cảm ơn! MỤC LỤC LỜI MỞ ĐẦU - 1 - 1. SPLAY TREE - 5 - 1.1 Giới thiệu về Splay tree - 5 - 1.2 Nguyên tắc hoạt động của splay tree - 6 - 1.2.1 Phương pháp Bottom Up - 7 - 1.2.2 Phương pháp phân tích Top – Down - 9 - 1.3 Các phép cập nhật trên Splay Tree - 11 - 1.3 Các phép cập nhật trên Splay Tree - 12 - 1.3.1 Find (i, T) - 12 - 1.3.2 Catenate (T1,T2) - 13 - 1.3.3 Split (i,T) – Tách cây T tại node i - 14 - 1.3.4 Insert (i,T) - 16 - 1.3.5 Delete (i,T) – Xoá nút i khỏi cây T - 17 - 1.4. Phân tích khấu hao - 19 - 1.5. Các thao tác trên Splay Trees - 25 - 2. ỨNG DỤNG CÂY SPLAY TRONG NÉN DỮ LIỆU - 30 - 2.1 Sử dụng phép quay Splaying trong nén dữ liệu - 30 - 2.2 Sử dụng phép quay Semi - Splaying trong nén dữ liệu - 33 - KẾT LUẬN - 36 -