Tài liệu Cây đỏ đen – lý thuết và mô phỏng

CÂY ĐỎ ĐEN – LÝ THUẾT VÀ MÔ PHỎNG

MỤC LỤC
PHẦN MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI 2
II. MỤC ĐÍCH CỦA ĐỀ TÀI 3
III. NHIỆM VỤ NGHIÊN CỨU 3
IV. PHƯƠNG PHÁP NGHIÊN CỨU 3
V. BỐ CỤC BÀI BÁO CÁO 4
PHẦN NỘI DUNG
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY 5
1.1 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM . 5
1.2 CÂY NHỊ PHÂN 9
CHƯƠNG 2: CÂY NHỊ PHÂN TÌM KIẾM 13
2.1 ĐỊNH NGHĨA CÂY NHỊ PHÂN TÌM KIẾM . 13
2.2 GIẢI THUẬT TÌM KIẾM . 13
2.3 PHÂN TÍCH ĐÁNH GIÁ 16
2.4 THAO TÁC XOÁ TRÊN CÂY NHỊ PHÂN TÌM KIẾM . 18
CHƯƠNG 3: CÂY ĐỎ ĐEN 21
3.1 ĐỊNH NGHĨA 21
3.2 CÁC TÍNH CHẤT. 23
3.3 THUẬN LỢI KHI SỬ DỤNG 24
3.4 CÁC PHÉP TOÁN TRÊN CÂY ĐỎ ĐEN 26
3.4.1 PHÉP CHÈN 26
3.4.2 PHÉP XOÁ 29
3.4.3 TÌM KIẾM . 33
PHẦN KẾT LUẬN
TÀI LIỆU THAM KHẢO









PHẦN MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀITrong 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. 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ách tổ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 đó, trong mộ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ào khá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 R[SUB]1[/SUB], R[SUB]2[/SUB], . , R[SUB]n[/SUB] . Mỗi bản ghi R[SUB]i[/SUB] (1 ≤ i ≤ n) tương ứng với một khoá k[SUB]i[/SUB] . Hãy tìm bản ghi có giá trị khoá tương ứng bằng X cho trướ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ột trong 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ìm kiế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ếm không thoả (unsuccessfull). Sau một phép tìm kiếm không thoả có khi xuất hiện yê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 dãy khoá luôn biến động thì lúc đó chi phí cho sắp xếp lại nổi lên rất rõ và chính điều ấy bộ lộ nhược điểm của phương pháp này.
Để khắc phục nhược điểm vừa nêu trên đối với tìm kiếm nhị phân và đáp ứng yêu cầu tìm kiếm đối với bảng biến động, một phương pháp mới được hình thành dựa trên cơ sở bảng được tổ chức dưới dạng cây nhị phân mà ta gọi là cây nhị phân tìm kiếm.
Trong đó cây đỏ đen là một trong những cấu trúc dữ liệu hay, cùng với cây nhị phân tìm kiếm là những cấu trúc dữ liệu có điểm mạnh trong việc lưu trữ và tìm kiếm dữ liệu. Song cây đỏ đen có những đặc tính riêng mà nhờ đó nó đã làm nổi bật những điểm mạnh của mình.
Trên cơ sở đó và với sự định hướng của thầy giáo hướng dẫn Th.S Nguyễn Hữu Dung em đã chọn đề tài “Cây đỏ đen – lý thuyết và mô phỏng ”
II. MỤC ĐÍCH CỦA ĐỀ TÀIĐề tài nhằm nghiên cứu lý thuyết về cây đỏ đen, một dạng cây tìm kiếm nhị phân tự cân bằng để thấy được những điểm mạng của kiểu cấu trúc dữ liệu này. Trên cơ sở thực hiện mô phỏng các phép toán chèn, xoá, tìm kiếm trên cây đỏ đen, đề tài nhằm khẳng định những tính chất, và việc sử dụng cấu trúc dữ liệu cây đỏ đen vào việc lưu trữ dữ liệu và thực hịên tìm kiếm trong bài toán tìm kiếm là một việc nên làm
III. NHIỆM VỤ NGHIÊN CỨUv Nghiên cứu và làm rõ những khái niệm, tính chất về cấu trúc dữ liệu cây, cây nhị phân, cây nhị phân tìm kiếm. Trên cơ sở đó xây dựng cấu trúc cây đỏ đen.
v Nghiên cứu các phép toán chèn, xoá , tìm kiếm trên cấu trúc dữ liệu cây đỏ đen; đánh giá chúng so với cây nhị phân tìm kiếm
v Thực hiện mô phỏng các phép toán trên cây đỏ đen
IV. PHƯƠNG PHÁP NGHIÊN CỨUPhương pháp nghiên cứu chủ yếu là tham khảo các tài liệu, bài viết, sách giáo trình liên quan tới cấu trúc cây, cây nhị phân tìm kiếm, cây đỏ đen.