twinkle_love_93
New Member
Link tải luận văn miễn phí cho ae Kết Nối
Cây đỏ đen – Lý thuyết và mô phỏng
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À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á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 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 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ỨU
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.
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
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ỨU
Phươ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.
Tìm tài liệu trên mạng Internet
Nghiên cứu lý thuyết về lập trình hướng đối tượng của ngôn ngữ lập trình Vissual foxpro, để xây dựng các bước mô phỏng các thuật toán trên cây đỏ đen.
V. BỐ CỤC BÀI BÁO CÁO
Báo cáo được chia thành 3 chương:
Chương 1: Tổng quan về cấu trúc cây
Chương này giới thiệu tổng quan về cấu trúc cây, khái niệm và các tính chất của cây, cây nhị phân;
Chương 2: Cây nhị phân tìm kiếm
Chương này trình bày về cây nhị phân tìm kiếm bao gồm: định nghĩa, các giải thuật tìm kiếm, các thao tác chèn và xoá trên cây nhị phân tìm kiếm, đánh giá về thời gian, độ phức tạp của các thao tác này
Chương 3: Cây đỏ đen
Chương này trình bày khái niệm, tính chất cây đỏ đen, các phép toán chèn, xoá, tìm kiếm trên cây đỏ đen, đánh giá về thời gian , độ phức tạp của các phép toán này; những thuận lợi khi sử dụng cấu trúc cây đỏ đen.
PHẦN NỘI DUNG
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY
1.1 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM
Cây là một cấu trúc phi tuyến tính. Một cây (tree) là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là nút gốc (root), giữa các nút có một mối quan hệ phân cấp gọi là quan hệ “cha - con”.
Có thể định nghĩa cây một cách đệ quy như sau:
1. Một nút là một cây. Nút đó cũng là gốc của cây ấy.
2. Nếu T1, T2, ..., Tn là các cây, với n1, n2, ... nk lần lượt là các gốc, n là một nút và n có quan hệ cha - con với n1, n2, ... nk thì lúc đó một cây mới T sẽ được tạo lập, với n là gốc của nó. n được gọi là cha của n1, n2, ... nk ; ngược lại n1, n2, ... nk được gọi là con của n. Các cây T1, T2, ..., Tn được gọi là các cây con (substrees) của n.
Ta quy ước : Một cây không có nút nào được gọi là cây rỗng (null tree).
Có nhiều đối tượng có cấu trúc cây.
Ví dụ :
• Mục lục của một cuốn sách, hay một chương trong sách, có cấu trúc cây.
• Cấu trúc thư mục trên đĩa cũng có cấu trúc cây, thư mục gốc có thể coi là gốc của cây đó với các cây con là các thư mục con và tệp nằm trên thư mục gốc.
• Gia phả của một họ tộc cũng có cấu trúc cây.
• Một biểu thức số học gồm các phép toán cộng, trừ, nhân, chia cũng có thể lưu trữ trong một cây mà các toán hạng được lưu trữ ở các nút lá, các toán tử được lưu trữ ở các nút nhánh, mỗi nhánh là một biểu thức con.
Chẳng hạn chương 1 trong PHẦN NỘI DUNG của bài báo cáo này :
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY
1.1 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM
1.2 CÂY NHỊ PHÂN
1.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT
1.2.2 BIỂU DIỄN CÂY NHỊ PHÂN
1.2.3 PHÉP DUYỆT CÂY NHỊ PHÂN
1.3 ÁP DỤNG
1.3.1 CÂY BIỂU DIỄN BIỂU THỨC
1.3.2 CÂY BIỂU DIỄN CÁC TẬP
1.3.3 CÂY QUYẾT ĐỊNH
Ta có thể biểu diễn bằng một cây có dạng như sau:
Hình 1.1
Biểu thức số học x + y * (z – t) + u/v, ta có thể biểu diễn dưới dạng cây như hình 1.2
Hình 1.2
Các tập bao nhau như hình 1.3 có thể biểu diễn bởi cây như hình 1.4
Hình 1.3
Hình 1.4
Đối với cây, chẳng hạn xét cây ở hình 1.4
o Nút A được gọi là gốc của cây
o B, C, D là gốc của các cây con gốc của A
o A là cha của B, C, D còn B, C, D là con của A.
Số các con của một nút gọi là cấp (degree) của nút đó. Ví dụ nút A có 3 con là B, C, D nên cấp của A là 3, cấp của H là 2.
• Nút có cấp bằng 0 gọi là lá (leaf) hay nút tận cùng (termimal node). Ví dụ các nút E, C, K, I , v.v. Nút không là lá được gọi là nút nhánh (branch node).
• Cấp cao nhất của nút trên cây gọi là cấp của cây đó. Cây ở hình 1.4 là cây cấp 3.
Gốc của cây có số mức (level) là 1. Nếu nút cha có số mức là i thì nút con có só mức là i + 1 . Ví dụ nút A có số mức là 1.
o Các nút B, C, D cùng có số mức là 2
o Các nút E, F, I, H, G có số mức là 3
o Các nút K, J có số mức là 4
Chiều cao (heigh) hay chiều xâu (depth) của một cây là số mức lớn nhất của nút có trên cây đó.
o Cây ở hình 1.2 có chiều cao là 5
o Cây ở hình 1.4 có chiều cao là 4
Nếu n1, n2 , … , nk là dãy các nút mà ni là cha của ni+1 với 1 ≤ i < k, thì dãy đó gọi là đường đi (path) từ n1 đến nk. Độ dài của đường đi (path length) từ nút nk đến nq là số nút phải đi qua để đi từ nk đến nq (bằng chiều cao của nq - chiều cao của nk). Ví dụ trên cây hình 1.4 độ dài đường đi từ A đến G là 2, từ A tới K là 3.
Nếu thứ tự các cây con của một nút được coi trọng thì cây đang xét là cây thứ tự (ordered tree), ngược lại là cây không có thứ tự (unordered tree). Thường thứ tự các cây con của một nút được đặt từ trái sang phải.
Hình 1.5 cho ta hai “cây có thứ tự” khác nhau :
Trường hợp 5: S là đen, con trái của S là đỏ, con phải của S là đen, còn N là con trái của cha nó. Trong trường hợp này chúng ta quay phải tại S, khi đó con trái của S trở thành cha của S và N là anh em mới của nó. Sau đó ta tráo đổi màu của S và cha mới của nó. Tất cả các đường đi sẽ có số nút đen như nhau, nhưng bây giờ N có một người anh em đen mà con phải của nó lại là đỏ, chúng ta chuyển sang Trường hợp 6. hay N hay cha của nó bị tác động bởi việc dịch chuyển này.
Hình 3.11
(trong trường hợp 6, ta đặt lại nút anh em mới của N là S.)
Trường hợp 6: S là đen, con phải của S là đỏ và N là con trái của nút cha P. Trong trường hợp này chúng ta quay trái tại P, khi đó S trở thành cha của P và con phải của S. Chúng ta hoán đổi màu của P và S, và gán cho con phải của S màu đen. Cây con giữ nguyên màu của gốc do đó Tính chất 4 (Cả hai con của nút đỏ là đen) và Tính chất 5 không bị vi phạm trong cây con này. Tuy nhiên, N bây giờ có thêm một nút đen tiền nhiệm: hay P mới bị tô đen, nó đã là đen và S là nút ông của nó trở thành đen. Như cậy các đương đi qua N có thêm một nút đen.
Trong lúc đó, với một đường đi không đi qua N, có hai khả năng:
• Đi qua nút anh em của N. Khi đó cả trước và sau khi quay nó phải đi qua S và P, khi thay đổi màu sắc hai nút này đã tráo đổi màu cho nhau. Như vậy đường đi này không bị thay đổi số nút đen.
• Đi qua nút bác của N, là con phải của S. Khi đó trước khi quay nó đi qua S, cha của S, và con phải của S, nhưng sau khi quay nó chỉ đi qua nút S và con phải của S, khi này S đã nhận màu cũ của cha P còn con phải của S's đã đổi màu từ đỏ thành đen. Kết quả là số các nút đen trên đường đi này không thay đổi.
Như vậy, số các nút đen trên các đường đi là không thay đổi. Do đó các tính chất 4 và 5 đã được khôi phục. Nút trắng trong hình vẽ có thể là đỏ hay đen, nhưng phải ghi lại trước và sau khi thay đổi.
Hình 3.12
3.4.3 TÌM KIẾM
Khi đã xây dựng được cấu trúc cây đỏ đen thì thao tác tìm kiếm trên cấu trúc dữ liệu này cũng sẽ được thực hiện như trong cây nhị phân tìm kiếm.
Khi tìm kiếm một khoá X nào đó có trên cây đó hay không ta có thể thực hiện như sau:
So sánh X với khoá ở gốc và 1 trong 4 tình huống sau đây sẽ xuất hiện:
1) Không có gốc (cây rỗng) : X không có trên cây ; phép tìm kiếm không thoả
2) X trùng với khoá gốc: phép tìm kiếm được thoả
3) X nhỏ hơn khoá ở gốc: tìm kiếm thực hiện tiếp tục bằng cách xét cây con trái của gốc với cách làm tương tự.
4) X lớn hơn khoá ở gốc: tìm kiếm được thực hiện tiếp tục bằng cách xét cây con phải của gốc với cách làm tương tự.
Ví dụ: Với cấu trúc cây đỏ đen đã xây dựng được từ hình 3.1, ta cần tìm xem giá trị khoá 5 có trong cây hay không.
Quá trình tìm kiếm sẽ như sau:
• So sánh 5 với giá trị nút gốc, 5 < 11, chuyển sang cây con trái
• Thực hiện so sánh 5 > 2, chuyển sang cây con phải
• Thực hiện so sánh 5 < 7 , chuyển sang cây con trái
• Cuối cùng, 5 = 5, vậy tìm kiếm đã được thoả.
Vg,VV
Như vậy, thời gian tìm kiếm khi sử dụng cấu trúc cây đỏ đen là O(log n)
PHẦN KẾT LUẬN
Giống như cây tìm kiếm nhị phân thông thường, cây đỏ đen có thể cho phép việc tìm kiếm, chèn và xóa trong thời gian O(log2N). Thời gian tìm kiếm là gần như bằng nhau đối với hai loại cây, vì những đặc điểm của cây đỏ đen không sử dụng trong quá trình tìm kiếm. Điều bất lợi là việc lưu trữ cần cho mỗi node tăng chút ít để điều tiết màu đỏ-đen (một biến boolean).
Đặc thù hơn, theo Sedgewick, trong thực tế tìm kiếm trên cây đỏ đen mất khoảng log2N phép so sánh, và có thể chứng minh rằng nó không cần hơn 2*log2N phép so sánh.
Thời gian chèn và xóa tăng dần bởi một hằng số vì việc phải thực thi phép lật màu và quay trên đường đi xuống và tại những điểm chèn. Trung bình một phép chèn cần khoảng chừng một phép quay. Do đó, chèn hày còn chiếm O(log2N) thời gian, nhưng lại chậm hơn phép chèn trong cây nhị phân thường.
Bởi vì trong hầu hết các ứng dụng, có nhiều thao tác tìm kiếm hơn là chèn và xóa, có lẽ không có nhiều bất lợi về thời gian khi dùng cây đỏ đen thay vì cây nhị phân thuờng. Dĩ nhiên, điều thuận lợi là trong cây đỏ đen, dữ liệu đã sắp xếp không làm giảm hiệu suất O(N).
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Cây đỏ đen – Lý thuyết và mô phỏng
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À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á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 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 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ỨU
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.
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
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ỨU
Phươ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.
Tìm tài liệu trên mạng Internet
Nghiên cứu lý thuyết về lập trình hướng đối tượng của ngôn ngữ lập trình Vissual foxpro, để xây dựng các bước mô phỏng các thuật toán trên cây đỏ đen.
V. BỐ CỤC BÀI BÁO CÁO
Báo cáo được chia thành 3 chương:
Chương 1: Tổng quan về cấu trúc cây
Chương này giới thiệu tổng quan về cấu trúc cây, khái niệm và các tính chất của cây, cây nhị phân;
Chương 2: Cây nhị phân tìm kiếm
Chương này trình bày về cây nhị phân tìm kiếm bao gồm: định nghĩa, các giải thuật tìm kiếm, các thao tác chèn và xoá trên cây nhị phân tìm kiếm, đánh giá về thời gian, độ phức tạp của các thao tác này
Chương 3: Cây đỏ đen
Chương này trình bày khái niệm, tính chất cây đỏ đen, các phép toán chèn, xoá, tìm kiếm trên cây đỏ đen, đánh giá về thời gian , độ phức tạp của các phép toán này; những thuận lợi khi sử dụng cấu trúc cây đỏ đen.
PHẦN NỘI DUNG
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY
1.1 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM
Cây là một cấu trúc phi tuyến tính. Một cây (tree) là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là nút gốc (root), giữa các nút có một mối quan hệ phân cấp gọi là quan hệ “cha - con”.
Có thể định nghĩa cây một cách đệ quy như sau:
1. Một nút là một cây. Nút đó cũng là gốc của cây ấy.
2. Nếu T1, T2, ..., Tn là các cây, với n1, n2, ... nk lần lượt là các gốc, n là một nút và n có quan hệ cha - con với n1, n2, ... nk thì lúc đó một cây mới T sẽ được tạo lập, với n là gốc của nó. n được gọi là cha của n1, n2, ... nk ; ngược lại n1, n2, ... nk được gọi là con của n. Các cây T1, T2, ..., Tn được gọi là các cây con (substrees) của n.
Ta quy ước : Một cây không có nút nào được gọi là cây rỗng (null tree).
Có nhiều đối tượng có cấu trúc cây.
Ví dụ :
• Mục lục của một cuốn sách, hay một chương trong sách, có cấu trúc cây.
• Cấu trúc thư mục trên đĩa cũng có cấu trúc cây, thư mục gốc có thể coi là gốc của cây đó với các cây con là các thư mục con và tệp nằm trên thư mục gốc.
• Gia phả của một họ tộc cũng có cấu trúc cây.
• Một biểu thức số học gồm các phép toán cộng, trừ, nhân, chia cũng có thể lưu trữ trong một cây mà các toán hạng được lưu trữ ở các nút lá, các toán tử được lưu trữ ở các nút nhánh, mỗi nhánh là một biểu thức con.
Chẳng hạn chương 1 trong PHẦN NỘI DUNG của bài báo cáo này :
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC CÂY
1.1 ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM
1.2 CÂY NHỊ PHÂN
1.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT
1.2.2 BIỂU DIỄN CÂY NHỊ PHÂN
1.2.3 PHÉP DUYỆT CÂY NHỊ PHÂN
1.3 ÁP DỤNG
1.3.1 CÂY BIỂU DIỄN BIỂU THỨC
1.3.2 CÂY BIỂU DIỄN CÁC TẬP
1.3.3 CÂY QUYẾT ĐỊNH
Ta có thể biểu diễn bằng một cây có dạng như sau:
Hình 1.1
Biểu thức số học x + y * (z – t) + u/v, ta có thể biểu diễn dưới dạng cây như hình 1.2
Hình 1.2
Các tập bao nhau như hình 1.3 có thể biểu diễn bởi cây như hình 1.4
Hình 1.3
Hình 1.4
Đối với cây, chẳng hạn xét cây ở hình 1.4
o Nút A được gọi là gốc của cây
o B, C, D là gốc của các cây con gốc của A
o A là cha của B, C, D còn B, C, D là con của A.
Số các con của một nút gọi là cấp (degree) của nút đó. Ví dụ nút A có 3 con là B, C, D nên cấp của A là 3, cấp của H là 2.
• Nút có cấp bằng 0 gọi là lá (leaf) hay nút tận cùng (termimal node). Ví dụ các nút E, C, K, I , v.v. Nút không là lá được gọi là nút nhánh (branch node).
• Cấp cao nhất của nút trên cây gọi là cấp của cây đó. Cây ở hình 1.4 là cây cấp 3.
Gốc của cây có số mức (level) là 1. Nếu nút cha có số mức là i thì nút con có só mức là i + 1 . Ví dụ nút A có số mức là 1.
o Các nút B, C, D cùng có số mức là 2
o Các nút E, F, I, H, G có số mức là 3
o Các nút K, J có số mức là 4
Chiều cao (heigh) hay chiều xâu (depth) của một cây là số mức lớn nhất của nút có trên cây đó.
o Cây ở hình 1.2 có chiều cao là 5
o Cây ở hình 1.4 có chiều cao là 4
Nếu n1, n2 , … , nk là dãy các nút mà ni là cha của ni+1 với 1 ≤ i < k, thì dãy đó gọi là đường đi (path) từ n1 đến nk. Độ dài của đường đi (path length) từ nút nk đến nq là số nút phải đi qua để đi từ nk đến nq (bằng chiều cao của nq - chiều cao của nk). Ví dụ trên cây hình 1.4 độ dài đường đi từ A đến G là 2, từ A tới K là 3.
Nếu thứ tự các cây con của một nút được coi trọng thì cây đang xét là cây thứ tự (ordered tree), ngược lại là cây không có thứ tự (unordered tree). Thường thứ tự các cây con của một nút được đặt từ trái sang phải.
Hình 1.5 cho ta hai “cây có thứ tự” khác nhau :
Trường hợp 5: S là đen, con trái của S là đỏ, con phải của S là đen, còn N là con trái của cha nó. Trong trường hợp này chúng ta quay phải tại S, khi đó con trái của S trở thành cha của S và N là anh em mới của nó. Sau đó ta tráo đổi màu của S và cha mới của nó. Tất cả các đường đi sẽ có số nút đen như nhau, nhưng bây giờ N có một người anh em đen mà con phải của nó lại là đỏ, chúng ta chuyển sang Trường hợp 6. hay N hay cha của nó bị tác động bởi việc dịch chuyển này.
Hình 3.11
(trong trường hợp 6, ta đặt lại nút anh em mới của N là S.)
Trường hợp 6: S là đen, con phải của S là đỏ và N là con trái của nút cha P. Trong trường hợp này chúng ta quay trái tại P, khi đó S trở thành cha của P và con phải của S. Chúng ta hoán đổi màu của P và S, và gán cho con phải của S màu đen. Cây con giữ nguyên màu của gốc do đó Tính chất 4 (Cả hai con của nút đỏ là đen) và Tính chất 5 không bị vi phạm trong cây con này. Tuy nhiên, N bây giờ có thêm một nút đen tiền nhiệm: hay P mới bị tô đen, nó đã là đen và S là nút ông của nó trở thành đen. Như cậy các đương đi qua N có thêm một nút đen.
Trong lúc đó, với một đường đi không đi qua N, có hai khả năng:
• Đi qua nút anh em của N. Khi đó cả trước và sau khi quay nó phải đi qua S và P, khi thay đổi màu sắc hai nút này đã tráo đổi màu cho nhau. Như vậy đường đi này không bị thay đổi số nút đen.
• Đi qua nút bác của N, là con phải của S. Khi đó trước khi quay nó đi qua S, cha của S, và con phải của S, nhưng sau khi quay nó chỉ đi qua nút S và con phải của S, khi này S đã nhận màu cũ của cha P còn con phải của S's đã đổi màu từ đỏ thành đen. Kết quả là số các nút đen trên đường đi này không thay đổi.
Như vậy, số các nút đen trên các đường đi là không thay đổi. Do đó các tính chất 4 và 5 đã được khôi phục. Nút trắng trong hình vẽ có thể là đỏ hay đen, nhưng phải ghi lại trước và sau khi thay đổi.
Hình 3.12
3.4.3 TÌM KIẾM
Khi đã xây dựng được cấu trúc cây đỏ đen thì thao tác tìm kiếm trên cấu trúc dữ liệu này cũng sẽ được thực hiện như trong cây nhị phân tìm kiếm.
Khi tìm kiếm một khoá X nào đó có trên cây đó hay không ta có thể thực hiện như sau:
So sánh X với khoá ở gốc và 1 trong 4 tình huống sau đây sẽ xuất hiện:
1) Không có gốc (cây rỗng) : X không có trên cây ; phép tìm kiếm không thoả
2) X trùng với khoá gốc: phép tìm kiếm được thoả
3) X nhỏ hơn khoá ở gốc: tìm kiếm thực hiện tiếp tục bằng cách xét cây con trái của gốc với cách làm tương tự.
4) X lớn hơn khoá ở gốc: tìm kiếm được thực hiện tiếp tục bằng cách xét cây con phải của gốc với cách làm tương tự.
Ví dụ: Với cấu trúc cây đỏ đen đã xây dựng được từ hình 3.1, ta cần tìm xem giá trị khoá 5 có trong cây hay không.
Quá trình tìm kiếm sẽ như sau:
• So sánh 5 với giá trị nút gốc, 5 < 11, chuyển sang cây con trái
• Thực hiện so sánh 5 > 2, chuyển sang cây con phải
• Thực hiện so sánh 5 < 7 , chuyển sang cây con trái
• Cuối cùng, 5 = 5, vậy tìm kiếm đã được thoả.
Vg,VV
Như vậy, thời gian tìm kiếm khi sử dụng cấu trúc cây đỏ đen là O(log n)
PHẦN KẾT LUẬN
Giống như cây tìm kiếm nhị phân thông thường, cây đỏ đen có thể cho phép việc tìm kiếm, chèn và xóa trong thời gian O(log2N). Thời gian tìm kiếm là gần như bằng nhau đối với hai loại cây, vì những đặc điểm của cây đỏ đen không sử dụng trong quá trình tìm kiếm. Điều bất lợi là việc lưu trữ cần cho mỗi node tăng chút ít để điều tiết màu đỏ-đen (một biến boolean).
Đặc thù hơn, theo Sedgewick, trong thực tế tìm kiếm trên cây đỏ đen mất khoảng log2N phép so sánh, và có thể chứng minh rằng nó không cần hơn 2*log2N phép so sánh.
Thời gian chèn và xóa tăng dần bởi một hằng số vì việc phải thực thi phép lật màu và quay trên đường đi xuống và tại những điểm chèn. Trung bình một phép chèn cần khoảng chừng một phép quay. Do đó, chèn hày còn chiếm O(log2N) thời gian, nhưng lại chậm hơn phép chèn trong cây nhị phân thường.
Bởi vì trong hầu hết các ứng dụng, có nhiều thao tác tìm kiếm hơn là chèn và xóa, có lẽ không có nhiều bất lợi về thời gian khi dùng cây đỏ đen thay vì cây nhị phân thuờng. Dĩ nhiên, điều thuận lợi là trong cây đỏ đen, dữ liệu đã sắp xếp không làm giảm hiệu suất O(N).
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Tags: đen đỏ đến gọi là j
Last edited by a moderator: