Nghiên cứu khoa học: Cây 2-3-4 - Lý thuyết và mô phỏng

Cây 2-3-4 – Lý thuyết và mô phỏng<br /> <br /> Nghiên Cứu Khoa Học<br /> <br /> MỤC LỤC----------------------------------------------------------------------------------1<br /> LỜI MỞ ĐẦU<br /> I.<br /> LÝ DO CHỌN ĐỀ TÀI---------------------------------------------------2<br /> II.<br /> MỤC ĐÍCH NGHIÊN CỨU ĐỀ TÀI-----------------------------------2<br /> III.<br /> NHIỆM VỤ NGHIÊN CỨU ĐỀ TÀI-----------------------------------3<br /> IV. ĐỐI TƢỢNG NGHIÊN CỨU--------------------------------------------3<br /> V.<br /> PHƢƠNG PHÁP NGHIÊN CỨU----------------------------------------3<br /> PHẦN NỘI DUNG-------------------------------------------------------------------------4<br /> CHƢƠNG 1. LÝ THUYẾT CÂY 2-3-4---------------------------------------------4<br /> I.<br /> Giới thiệu về cây 2-3-4.-----------------------------------------------------4<br /> II.<br /> Tổ chức cây 2-3-4.----------------------------------------------------------6<br /> III.<br /> Tìm kiếm.---------------------------------------------------------------------8<br /> IV.<br /> Tách node.-------------------------------------------------------------------8<br /> 1. Tách node con.------------------------------------------------------------8<br /> 2. Tách node gốc.----------------------------------------------------------11<br /> 3. Tách theo hướng đi xuống.--------------------------------------------12<br /> V.<br /> Chèn node.------------------------------------------------------------------14<br /> VI.<br /> Tính hiệu quả của Cây 2-3-4---------------------------------------------15<br /> VII. Chuyển từ cây 2-3-4 sang cây đỏ đen.----------------------------------16<br /> CHƢƠNG 2. MÔ PHỎNG THUẬT TOÁN TRÊN CÂY 2-3-4--------------21<br /> I.<br /> Tổng quan về mô phỏng thuật toán.-------------------------------------21<br /> 1. Khái niệm thuật toán và các đặc trưng của thuật toán.----------21<br /> 2. Khái niệm mô phỏng thuật toán.-------------------------------------21<br /> II.<br /> Các yêu cầu mô phỏng thuật toán.--------------------------------------22<br /> III.<br /> Quá trình thiết kế nhiệm vụ mô phỏng thuật toán.--------------------23<br /> IV.<br /> Mô phỏng thuật toán trên Cây 2-3-4------------------------------------23<br /> 1. Giới thiệu ngôn ngữ mô phỏng.--------------------------------------23<br /> 2. Phân tích và thiết kế thuật toán mô phỏng.------------------------24<br /> a. Phân tích.-----------------------------------------------------------24<br /> b. Thiết kế.-------------------------------------------------------------24<br /> TÀI LIỆU THAM KHẢO---------------------------------------------------------------36<br /> <br /> Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT<br /> <br /> 1<br /> <br /> Cây 2-3-4 – Lý thuyết và mô phỏng<br /> <br /> Nghiên Cứu Khoa Học<br /> <br /> LỜI MỞ ĐẦU<br /> I. Lý do chọn đề tài<br /> Trong hai thập kỉ qua, mô phỏng thuật toán đã đƣợc các nhà sƣ phạm của<br /> 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<br /> 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<br /> 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ô<br /> 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<br /> của nó trong suốt quá trình thực thi.<br /> 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<br /> 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<br /> 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<br /> 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<br /> nhanh hơn và ngày càng yêu thích giải thuật.<br /> 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ụ<br /> 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<br /> 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<br /> 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<br /> tính.<br /> 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<br /> 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á<br /> 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 –<br /> Lý thuyết và mô phỏng” đƣợc chọn làm đề tài nghiên cứu.<br /> II. Mục đích nghiên cứu đề tài<br /> 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<br /> 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<br /> 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<br /> Cây 2-3-4.<br /> Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT<br /> <br /> 2<br /> <br /> Cây 2-3-4 – Lý thuyết và mô phỏng<br /> <br /> Nghiên Cứu Khoa Học<br /> <br /> III .Nhiệm vu nghiên cứu đề tài.<br /> 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<br /> tiếp cận, phƣơng pháp thiết kế một mô đun mô phỏng thuật toán.<br /> 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.<br /> IV. Đối tượng nghiên cứu.<br /> Đề 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:<br /> - Thuật toán tìm kiếm trên Cây 2-3-4<br /> - Thuật toán chèn một node và chèn một giá trị vào Cây 2-3-4<br /> - Thuật toán tách node trên Cây 2-3-4<br /> - Thuật toán xóa node và xóa một giá trị trên Cây 2-3-4<br /> V. Phưong pháp nghiên cứu.<br /> 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<br /> 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<br /> và đặc biệt là nguồn tài liệu phong phú trên mạng Internet.<br /> <br /> Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT<br /> <br /> 3<br /> <br /> Cây 2-3-4 – Lý thuyết và mô phỏng<br /> <br /> Nghiên Cứu Khoa Học<br /> <br /> PHẦN NỘI DUNG<br /> Chương I.<br /> <br /> Lý thuyết về Cây 2-3-4<br /> <br /> I. Giới thiệu về cây 2-3-4.<br /> 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<br /> ứ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.<br /> 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<br /> hợp dễ xuất hiện trong thực tế nếu ngƣời dùng không chú ý đến nó.<br /> 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<br /> 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<br /> giản có thể làm thuật toán tìm trên cây hoạt động rất tồi.<br /> 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<br /> 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<br /> 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<br /> 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ể<br /> 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<br /> 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<br /> 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ỹ<br /> 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ó<br /> đối với các phƣơng pháp khác.<br /> Để 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<br /> 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ử<br /> 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,<br /> 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<br /> 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ó<br /> 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<br /> 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<br /> tự với một 4-node có 4 liên kết đi ra khỏi nó.<br /> 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<br /> giữa cây 2-3-4 và cây đỏ-đen.<br /> <br /> Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT<br /> <br /> 4<br /> <br /> Cây 2-3-4 – Lý thuyết và mô phỏng<br /> <br /> Nghiên Cứu Khoa Học<br /> <br /> 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<br /> hoặc 3 mục dữ liệu.<br /> <br /> Hình 4.1 cây 2-3-4<br /> 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<br /> 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<br /> node không phải là lá, có thể có 3 cách sắp xếp sau:<br /> Một node với một mục dữ liệu thì luôn luôn có 2 con.<br /> <br /> k<br /> <br /> Một node với hai mục dữ liệu thì luôn luôn có 3 con.<br /> <br /> k1 k2<br /> <br /> Một node với ba mục dữ liệu thì luôn luôn có 4 con.<br /> k1<br /> <br /> k2<br /> <br /> k3<br /> <br /> 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<br /> 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à<br /> số mục dữ liệu là d, thì : c = d + 1. Sau đây là các ví dụ cụ thể:<br /> <br /> Sinh viên: Đỗ Thị Thùy Dương – Lớp A_K54_CNTT<br /> <br /> 5<br /> <br />