Xem mẫu
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
MỤC LỤC----------------------------------------------------------------------------------1
LỜI MỞ ĐẦU
I.
LÝ DO CHỌN ĐỀ TÀI---------------------------------------------------2
II.
MỤC ĐÍCH NGHIÊN CỨU ĐỀ TÀI-----------------------------------2
III.
NHIỆM VỤ NGHIÊN CỨU ĐỀ TÀI-----------------------------------3
IV. ĐỐI TƢỢNG NGHIÊN CỨU--------------------------------------------3
V.
PHƢƠNG PHÁP NGHIÊN CỨU----------------------------------------3
PHẦN NỘI DUNG-------------------------------------------------------------------------4
CHƢƠNG 1. LÝ THUYẾT CÂY 2-3-4---------------------------------------------4
I.
Giới thiệu về cây 2-3-4.-----------------------------------------------------4
II.
Tổ chức cây 2-3-4.----------------------------------------------------------6
III.
Tìm kiếm.---------------------------------------------------------------------8
IV.
Tách node.-------------------------------------------------------------------8
1. Tách node con.------------------------------------------------------------8
2. Tách node gốc.----------------------------------------------------------11
3. Tách theo hướng đi xuống.--------------------------------------------12
V.
Chèn node.------------------------------------------------------------------14
VI.
Tính hiệu quả của Cây 2-3-4---------------------------------------------15
VII. Chuyển từ cây 2-3-4 sang cây đỏ đen.----------------------------------16
CHƢƠNG 2. MÔ PHỎNG THUẬT TOÁN TRÊN CÂY 2-3-4--------------21
I.
Tổng quan về mô phỏng thuật toán.-------------------------------------21
1. Khái niệm thuật toán và các đặc trưng của thuật toán.----------21
2. Khái niệm mô phỏng thuật toán.-------------------------------------21
II.
Các yêu cầu mô phỏng thuật toán.--------------------------------------22
III.
Quá trình thiết kế nhiệm vụ mô phỏng thuật toán.--------------------23
IV.
Mô phỏng thuật toán trên Cây 2-3-4------------------------------------23
1. Giới thiệu ngôn ngữ mô phỏng.--------------------------------------23
2. Phân tích và thiết kế thuật toán mô phỏng.------------------------24
a. Phân tích.-----------------------------------------------------------24
b. Thiết kế.-------------------------------------------------------------24
TÀI LIỆU THAM KHẢO---------------------------------------------------------------36
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
1
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
LỜI MỞ ĐẦU
I. Lý do chọn đề tài
Trong hai thập kỉ qua, mô phỏng thuật toán đã đƣợc các nhà sƣ phạm của
ngành công nghệ thông tin sử dụng nhƣ một công cụ hỗ trợ cho việc giảng dạy các
thuật toán trên máy tính. Nguyên nhân của việc mô phỏng thuật toán đƣợc sử dụng
nhƣ một công cụ trợ giúp cho việc giảng dạy là do nó có thể cung cấp các mô
phỏng động bằng đồ họa của một thuật toán và các thay đổi trong cấu trúc dữ liệu
của nó trong suốt quá trình thực thi.
Nhƣ một phần của quá trình học thuật toán, việc mô phỏng các thuật toán
còn góp phần giúp các em học sinh, sinh viên khi mới bắt đầu làm quen với giải
thuật có thể vừa dễ dàng theo dõi các bƣớc duyệt ở lý thuyết vừa nhìn thấy các
bƣớc chạy ở thực tế nhƣ thế nào. Tƣ đó có thể giúp các em tƣ duy thuật toán
nhanh hơn và ngày càng yêu thích giải thuật.
Mô phỏng thuật toán ngày càng trở nên hữu ích và trở thành một giáo cụ
trực quan rất quan trọng trong hầu hết các lĩnh vực, nhất là trong môi trƣờng giáo
dục. Với các nhà sƣ phạm của ngành công nghệ thông tin thì mô phỏng thuật toán
có tác dụng nhƣ một tài liệu hƣớng dẫn trong việc dạy các thuật toán bằng máy
tính.
Cây 2-3-4 là một cây nhị phân tìm kiếm giải quyết tốt hơn các trƣờng hợp
xấu nhất cho cây nhị phân tìm kiếm bình thƣờng. Và đây còn là một nội dung khá
mới mẻ và phức tạp đối với nhiều học sinh, sinh viên. Vì vậy vấn đề “Cây 2-3-4 –
Lý thuyết và mô phỏng” đƣợc chọn làm đề tài nghiên cứu.
II. Mục đích nghiên cứu đề tài
Mục đích nghiên cứu của khóa luận này nhằm tìm hiểu và đánh giá các
thuật toán trên Cây 2-3-4, đồng thời xây dựng một phần mềm mô phỏng các thuật
toán này nhằm hỗ trợ cho việc học, nghiên cứu và tiến tới dạy các thuật toán trên
Cây 2-3-4.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
2
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
III .Nhiệm vu nghiên cứu đề tài.
Nghiên cứu tổng quan về mô phỏng thuật toán, các yêu cầu, phƣơng pháp
tiếp cận, phƣơng pháp thiết kế một mô đun mô phỏng thuật toán.
Thiết kế minh họa các mô đun minh họa các thuật toán trên Cây2-3-4.
IV. Đối tượng nghiên cứu.
Đề tài nghiên cứu đi sâu vào nghiên cứu và cài đặt một số thuật toán:
- Thuật toán tìm kiếm trên Cây 2-3-4
- Thuật toán chèn một node và chèn một giá trị vào Cây 2-3-4
- Thuật toán tách node trên Cây 2-3-4
- Thuật toán xóa node và xóa một giá trị trên Cây 2-3-4
V. Phưong pháp nghiên cứu.
Phƣơng pháp nghiên cứu chủ yếu tham khảo các tài liệu tham khảo liên
quan đến Cây nhị phân tìm kiếm, Cây 2-3-4 thông qua các sách, tài liệu tham khảo
và đặc biệt là nguồn tài liệu phong phú trên mạng Internet.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
3
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
PHẦN NỘI DUNG
Chương I.
Lý thuyết về Cây 2-3-4
I. Giới thiệu về cây 2-3-4.
Nhƣ chúng ta đã biết, các thuật toán về cây nhị phân luôn rất tốt cho nhiều
ứng dụng, tuy nhiên chúng lại có những khuyết điểm trong trƣờng hợp xấu nhất.
Chẳng hạn nhƣ trƣờng hợp Quicksort, trƣờng hợp xấu nhất của nó lại là trƣờng
hợp dễ xuất hiện trong thực tế nếu ngƣời dùng không chú ý đến nó.
Các tập tin đã đƣợc xắp xếp thứ tự, các tập tin với thứ tự ngƣợc, các tập các
khoá lớn, nhỏ xen lẫn nhau hay các tập tin với sự phân đoạn lớn có cấu trúc đơn
giản có thể làm thuật toán tìm trên cây hoạt động rất tồi.
Với thuật toán QuickSort, cái mà chúng ta cần để cái tiến tình huống là sắp
xếp lại để có trƣờng hợp ngẫu nhiên: bằng cách chọn một phần tử phân hoạch
ngẫu nhiên, chúng ta có thể dựa vào quy luật xác xuất để tránh khỏi trƣờng hợp
xấu nhất. Với tìm kiếm trên cây nhị phân thì may mắn hơn, bởi vì chúng ta có thể
làm tốt hơn nhiều; có một kỹ thuật tổng quát cho phép chúng ta bảo đảm trƣờng
hợp xấu nhất sẽ không xuất hiện. Kỹ thuật này gọi là Cân bằng đã đƣợc dùng làm
cơ sở cho nhiều thuật toán khác nhau về “cây cân bằng”. Chúng ta sẽ xem xét kỹ
một thuật toán thuộc loại đó và cùng nhau thảo luận tóm tắt về sự liên quan của nó
đối với các phƣơng pháp khác.
Để khử trƣờng hợp xấu nhất của cây tìm kiếm nhị phân, chúng ta cần dùng
một vài linh động trong cấu trúc sẽ dùng. Để có sự linh động này, chúng ta giả sử
rằng các node trong cây của chúng ta có chứa nhiều hơn một khóa. Cụ thể hơn,
chúng ta sẽ thừa nhận các 3-node và 4-node mà có thể chứa tƣơng ứng hai và ba
khóa. Một 3-node có ba liên kết ra khỏi nó, một liên kết cho tất cả các mẩu tin có
khóa nhỏ hơn cả hai khóa của nó, một cho tất cả các mẩu tin có khóa nằm giữa hai
khóa của nó, một cho tất cả các mẩu tin có khóa lớn hơn hai khóa của nó. Tƣơng
tự với một 4-node có 4 liên kết đi ra khỏi nó.
Chúng ta sẽ xem xét các đặc tính của cây 2-3-4 và mối quan hệ khá gần gũi
giữa cây 2-3-4 và cây đỏ-đen.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
4
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
Hình 4.1 Trình bày một cây 2-3-4 đơn giản. Mỗi node có thể lƣu trữ 1, 2
hoặc 3 mục dữ liệu.
Hình 4.1 cây 2-3-4
Các số 2, 3 và 4 trong cụm từ cây 2-3-4 có ý nghĩa là khả năng có bao nhiêu
liên kết đến các node con có thể có đƣợc trong một node cho trƣớc. Đối với các
node không phải là lá, có thể có 3 cách sắp xếp sau:
Một node với một mục dữ liệu thì luôn luôn có 2 con.
k
Một node với hai mục dữ liệu thì luôn luôn có 3 con.
k1 k2
Một node với ba mục dữ liệu thì luôn luôn có 4 con.
k1
k2
k3
Nhƣ vậy, một node không phải là lá phải luôn luôn có số node con nhiều hơn
1 so với số mục dữ liệu của nó. Nói cách khác, đối với mọi node với số con là c và
số mục dữ liệu là d, thì : c = d + 1. Sau đây là các ví dụ cụ thể:
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
5
nguon tai.lieu . vn
Nghiên Cứu Khoa Học
MỤC LỤC----------------------------------------------------------------------------------1
LỜI MỞ ĐẦU
I.
LÝ DO CHỌN ĐỀ TÀI---------------------------------------------------2
II.
MỤC ĐÍCH NGHIÊN CỨU ĐỀ TÀI-----------------------------------2
III.
NHIỆM VỤ NGHIÊN CỨU ĐỀ TÀI-----------------------------------3
IV. ĐỐI TƢỢNG NGHIÊN CỨU--------------------------------------------3
V.
PHƢƠNG PHÁP NGHIÊN CỨU----------------------------------------3
PHẦN NỘI DUNG-------------------------------------------------------------------------4
CHƢƠNG 1. LÝ THUYẾT CÂY 2-3-4---------------------------------------------4
I.
Giới thiệu về cây 2-3-4.-----------------------------------------------------4
II.
Tổ chức cây 2-3-4.----------------------------------------------------------6
III.
Tìm kiếm.---------------------------------------------------------------------8
IV.
Tách node.-------------------------------------------------------------------8
1. Tách node con.------------------------------------------------------------8
2. Tách node gốc.----------------------------------------------------------11
3. Tách theo hướng đi xuống.--------------------------------------------12
V.
Chèn node.------------------------------------------------------------------14
VI.
Tính hiệu quả của Cây 2-3-4---------------------------------------------15
VII. Chuyển từ cây 2-3-4 sang cây đỏ đen.----------------------------------16
CHƢƠNG 2. MÔ PHỎNG THUẬT TOÁN TRÊN CÂY 2-3-4--------------21
I.
Tổng quan về mô phỏng thuật toán.-------------------------------------21
1. Khái niệm thuật toán và các đặc trưng của thuật toán.----------21
2. Khái niệm mô phỏng thuật toán.-------------------------------------21
II.
Các yêu cầu mô phỏng thuật toán.--------------------------------------22
III.
Quá trình thiết kế nhiệm vụ mô phỏng thuật toán.--------------------23
IV.
Mô phỏng thuật toán trên Cây 2-3-4------------------------------------23
1. Giới thiệu ngôn ngữ mô phỏng.--------------------------------------23
2. Phân tích và thiết kế thuật toán mô phỏng.------------------------24
a. Phân tích.-----------------------------------------------------------24
b. Thiết kế.-------------------------------------------------------------24
TÀI LIỆU THAM KHẢO---------------------------------------------------------------36
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
1
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
LỜI MỞ ĐẦU
I. Lý do chọn đề tài
Trong hai thập kỉ qua, mô phỏng thuật toán đã đƣợc các nhà sƣ phạm của
ngành công nghệ thông tin sử dụng nhƣ một công cụ hỗ trợ cho việc giảng dạy các
thuật toán trên máy tính. Nguyên nhân của việc mô phỏng thuật toán đƣợc sử dụng
nhƣ một công cụ trợ giúp cho việc giảng dạy là do nó có thể cung cấp các mô
phỏng động bằng đồ họa của một thuật toán và các thay đổi trong cấu trúc dữ liệu
của nó trong suốt quá trình thực thi.
Nhƣ một phần của quá trình học thuật toán, việc mô phỏng các thuật toán
còn góp phần giúp các em học sinh, sinh viên khi mới bắt đầu làm quen với giải
thuật có thể vừa dễ dàng theo dõi các bƣớc duyệt ở lý thuyết vừa nhìn thấy các
bƣớc chạy ở thực tế nhƣ thế nào. Tƣ đó có thể giúp các em tƣ duy thuật toán
nhanh hơn và ngày càng yêu thích giải thuật.
Mô phỏng thuật toán ngày càng trở nên hữu ích và trở thành một giáo cụ
trực quan rất quan trọng trong hầu hết các lĩnh vực, nhất là trong môi trƣờng giáo
dục. Với các nhà sƣ phạm của ngành công nghệ thông tin thì mô phỏng thuật toán
có tác dụng nhƣ một tài liệu hƣớng dẫn trong việc dạy các thuật toán bằng máy
tính.
Cây 2-3-4 là một cây nhị phân tìm kiếm giải quyết tốt hơn các trƣờng hợp
xấu nhất cho cây nhị phân tìm kiếm bình thƣờng. Và đây còn là một nội dung khá
mới mẻ và phức tạp đối với nhiều học sinh, sinh viên. Vì vậy vấn đề “Cây 2-3-4 –
Lý thuyết và mô phỏng” đƣợc chọn làm đề tài nghiên cứu.
II. Mục đích nghiên cứu đề tài
Mục đích nghiên cứu của khóa luận này nhằm tìm hiểu và đánh giá các
thuật toán trên Cây 2-3-4, đồng thời xây dựng một phần mềm mô phỏng các thuật
toán này nhằm hỗ trợ cho việc học, nghiên cứu và tiến tới dạy các thuật toán trên
Cây 2-3-4.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
2
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
III .Nhiệm vu nghiên cứu đề tài.
Nghiên cứu tổng quan về mô phỏng thuật toán, các yêu cầu, phƣơng pháp
tiếp cận, phƣơng pháp thiết kế một mô đun mô phỏng thuật toán.
Thiết kế minh họa các mô đun minh họa các thuật toán trên Cây2-3-4.
IV. Đối tượng nghiên cứu.
Đề tài nghiên cứu đi sâu vào nghiên cứu và cài đặt một số thuật toán:
- Thuật toán tìm kiếm trên Cây 2-3-4
- Thuật toán chèn một node và chèn một giá trị vào Cây 2-3-4
- Thuật toán tách node trên Cây 2-3-4
- Thuật toán xóa node và xóa một giá trị trên Cây 2-3-4
V. Phưong pháp nghiên cứu.
Phƣơng pháp nghiên cứu chủ yếu tham khảo các tài liệu tham khảo liên
quan đến Cây nhị phân tìm kiếm, Cây 2-3-4 thông qua các sách, tài liệu tham khảo
và đặc biệt là nguồn tài liệu phong phú trên mạng Internet.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
3
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
PHẦN NỘI DUNG
Chương I.
Lý thuyết về Cây 2-3-4
I. Giới thiệu về cây 2-3-4.
Nhƣ chúng ta đã biết, các thuật toán về cây nhị phân luôn rất tốt cho nhiều
ứng dụng, tuy nhiên chúng lại có những khuyết điểm trong trƣờng hợp xấu nhất.
Chẳng hạn nhƣ trƣờng hợp Quicksort, trƣờng hợp xấu nhất của nó lại là trƣờng
hợp dễ xuất hiện trong thực tế nếu ngƣời dùng không chú ý đến nó.
Các tập tin đã đƣợc xắp xếp thứ tự, các tập tin với thứ tự ngƣợc, các tập các
khoá lớn, nhỏ xen lẫn nhau hay các tập tin với sự phân đoạn lớn có cấu trúc đơn
giản có thể làm thuật toán tìm trên cây hoạt động rất tồi.
Với thuật toán QuickSort, cái mà chúng ta cần để cái tiến tình huống là sắp
xếp lại để có trƣờng hợp ngẫu nhiên: bằng cách chọn một phần tử phân hoạch
ngẫu nhiên, chúng ta có thể dựa vào quy luật xác xuất để tránh khỏi trƣờng hợp
xấu nhất. Với tìm kiếm trên cây nhị phân thì may mắn hơn, bởi vì chúng ta có thể
làm tốt hơn nhiều; có một kỹ thuật tổng quát cho phép chúng ta bảo đảm trƣờng
hợp xấu nhất sẽ không xuất hiện. Kỹ thuật này gọi là Cân bằng đã đƣợc dùng làm
cơ sở cho nhiều thuật toán khác nhau về “cây cân bằng”. Chúng ta sẽ xem xét kỹ
một thuật toán thuộc loại đó và cùng nhau thảo luận tóm tắt về sự liên quan của nó
đối với các phƣơng pháp khác.
Để khử trƣờng hợp xấu nhất của cây tìm kiếm nhị phân, chúng ta cần dùng
một vài linh động trong cấu trúc sẽ dùng. Để có sự linh động này, chúng ta giả sử
rằng các node trong cây của chúng ta có chứa nhiều hơn một khóa. Cụ thể hơn,
chúng ta sẽ thừa nhận các 3-node và 4-node mà có thể chứa tƣơng ứng hai và ba
khóa. Một 3-node có ba liên kết ra khỏi nó, một liên kết cho tất cả các mẩu tin có
khóa nhỏ hơn cả hai khóa của nó, một cho tất cả các mẩu tin có khóa nằm giữa hai
khóa của nó, một cho tất cả các mẩu tin có khóa lớn hơn hai khóa của nó. Tƣơng
tự với một 4-node có 4 liên kết đi ra khỏi nó.
Chúng ta sẽ xem xét các đặc tính của cây 2-3-4 và mối quan hệ khá gần gũi
giữa cây 2-3-4 và cây đỏ-đen.
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
4
Cây 2-3-4 – Lý thuyết và mô phỏng
Nghiên Cứu Khoa Học
Hình 4.1 Trình bày một cây 2-3-4 đơn giản. Mỗi node có thể lƣu trữ 1, 2
hoặc 3 mục dữ liệu.
Hình 4.1 cây 2-3-4
Các số 2, 3 và 4 trong cụm từ cây 2-3-4 có ý nghĩa là khả năng có bao nhiêu
liên kết đến các node con có thể có đƣợc trong một node cho trƣớc. Đối với các
node không phải là lá, có thể có 3 cách sắp xếp sau:
Một node với một mục dữ liệu thì luôn luôn có 2 con.
k
Một node với hai mục dữ liệu thì luôn luôn có 3 con.
k1 k2
Một node với ba mục dữ liệu thì luôn luôn có 4 con.
k1
k2
k3
Nhƣ vậy, một node không phải là lá phải luôn luôn có số node con nhiều hơn
1 so với số mục dữ liệu của nó. Nói cách khác, đối với mọi node với số con là c và
số mục dữ liệu là d, thì : c = d + 1. Sau đây là các ví dụ cụ thể:
Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT
5