Cây đỏ đen – Lý thuyết và mô phỏng

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ việc chọn một cấu trúc dữ liệu trừu tượng.
Nội dung trích xuất từ tài liệu:
Cây đỏ đen – Lý thuyết và mô phỏng TRƯỜNG …………………. KHOA………………………. ----- ----- Cây đỏ đenLý thuyết và mô phỏngCây đỏ den – lý thuyết và mô phỏng MỤC LỤCPHẦN MỞ ĐẦUI. LÝ DO CHỌN ĐỀ TÀI ............................................................................... 2II. MỤC ĐÍCH CỦA ĐỀ TÀI .......................................................................... 3III. NHIỆM VỤ NGHIÊN CỨU ....................................................................... 3IV. PHƯƠNG PHÁP NGHIÊN CỨU .............................................................. 3V. BỐ CỤC BÀI BÁO CÁO............................................................................. 4PHẦN NỘI DUNGCHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY............................................... 5 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM........................................................................ 51.1 CÂY NHỊ PHÂN ........................................................................................................ 91.2CHƯƠNG 2: CÂY NHỊ PHÂN TÌM KIẾM ........................................................13 ĐỊNH NGHĨA CÂY NHỊ PHÂN TÌM KIẾM ........................................................... 132.1 GIẢI THUẬT TÌM KIẾM ........................................................................................ 132.2 PHÂN TÍCH ĐÁNH GIÁ ......................................................................................... 162.3 THAO TÁC XOÁ TRÊN CÂY NHỊ PHÂN TÌM KIẾM........................................... 182.4CHƯƠNG 3: CÂY ĐỎ ĐEN ................................................................................21 ĐỊNH NGHĨA .......................................................................................................... 213.1 CÁC TÍNH CHẤT .................................................................................................... 233.2 THUẬN LỢI KHI SỬ DỤNG................................................................................... 243.3 CÁC PHÉP TOÁN TRÊN CÂY ĐỎ ĐEN ................................................................ 263.4 3.4.1 PHÉP CHÈN ..................................................................................................... 26 3.4.2 PHÉP XOÁ ....................................................................................................... 29 3.4.3 TÌM KIẾM ........................................................................................................ 33PHẦN KẾT LUẬNTÀI LIỆU THAM KHẢO 1Trần Thị Thu Bình _A/K54_SPTin_ĐHSPHNCây đỏ den – lý thuyết và mô phỏngPHẦN MỞ ĐẦU I. LÝ DO CHỌN ĐỀ TÀI Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máytính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấutrúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn.Việc chọn cấu trúc dữ liệu thường bắt đầu từ việc chọn một cấu trúc dữ liệu trừutượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hịên nhiều phép toán,sử dụng càng ít tài nguyên, thời gian sử lý và không gian bộ nhớ tốt. Chúng ta đều biết tìm kiếm (Searching) là một đòi hỏi rất thường xuyên trongđời sống hàng ngày cũng như trong xử lý Tin học. Vấn đề tìm kiếm xét một cáchtổng quát, có thể hiểu là tìm một đối tượng thoả mãn một số đòi hỏi nào đó, trongmột tập rộng lớn các đối tượng. Khi không liên quan đến mục đích xử lý cụ thể nàokhác, bài toán tìm kiếm có thể được phát biểu độc lập và tổng quát như sau: “Cho một bảng gồm n bản ghi R1, R2, ... , Rn . Mỗi bản ghi Ri (1 ≤ i ≤ n) tươngứng với một khoá ki . Hãy tìm bản ghi có giá trị khoá tương ứng bằng X chotrước”. X được gọi là khoá tìm kiếm. Công việc tìm kiếm sẽ hoàn thành khi có mộttrong hai tình huống sau đây sảy ra 1) Tìm được bản ghi có giá trị khoá tương ứng bằng X, lúc đó ta nói phép tìmkiếm được thoả (successfull) 2) Không tìm thấy được bản ghi nào có giá trị khoá bằng X. Phép tìm kiếmkhông thoả (unsuccessfull). Sau một phép tìm kiếm không thoả có khi xuất hiệnyêu cầu bổ xung thê m bản ghi mới có khoá bằng X vào bảng. Giải thuật thể hiện cảyêu cầu này được gọi là giải thuật “tìm kiếm có bổ xung”. Có nhiều phương pháp tìm kiếm cơ bản và phổ dụng, đối với dữ liệu ở bộ nhớtrong nghĩa là tìm kiếm trong, đối với dữ liệu ở bộ nhớ ngoài là tìm kiếm ngoài.Đối với tìm kiếm trong, tìm kiếm nhị phân là một phương pháp khá thông dụng,chi phí ít, đạt kết quả tốt. Tuy nhiên khi sử dụng tìmkiếm nhị phân dãy khoá đãphải được sắp xếp rồi, nghĩa là thời gian chi phí cho sắp xếp cũng phải kể đến. Nếu ...