Báo cáo khoa học: Lý thuyết và mô phỏng cây AVL

Báo cáo khoa học: Lý thuyết và mô phỏng cây AVL<br /> <br /> Nguyễn Thị Thu Hương – Ak54 -CNTT<br /> <br /> MỤC LỤC<br /> <br /> PHẦN MỞ ĐẦU ...................................................................................................... 3<br /> Lý do chọn đề tài.................................................................................................. 3<br /> PHẦN 1: LÝ THUYẾT ............................................................................................ 4<br /> I. CÂY NHỊ PHÂN TÌM KIẾM ............................................................................... 4<br /> 1.1. Định nghĩa và các khái niệm về cây nhị phân .............................................. 4<br /> 1.2 Cây nhị phân tìm kiếm ................................................................................... 4<br /> a. Định nghĩa và tính chất .............................................................................. 4<br /> b.Giải thuật tìm kiếm ..................................................................................... 5<br /> c. Giải thuật bổ sung...................................................................................... 6<br /> d. Giải thuật loại bỏ ....................................................................................... 6<br /> f. Phân tích đánh giá...................................................................................... 6<br /> II. CÂY NHỊ PHÂN CÂN BẰNG ............................................................................ 7<br /> 2.1. Cây nhị phân cân bằng hoàn toàn (CCBHT) ................................................. 7<br /> a. Định nghĩa: ............................................................................................... 7<br /> b. Đánh giá:................................................................................................... 7<br /> 2.2. Cây nhị phân tự cân bằng (AVL) ................................................................... 7<br /> a. Định nghĩa ................................................................................................. 7<br /> b. Các trường hợp gây mất cân bằng trên cây AVL ....................................... 8<br /> b. Giải thuật bổ sung trên cây AVL ................................................................ 9<br /> c. Giải thuật loại bỏ trên cây AVL ............................................................... 11<br /> d .Đánh giá .................................................................................................. 11<br /> PHẦN 2: MÔ PHỎNG .......................................................................................... 11<br /> I. LÝ THUYẾT MÔ PHỎNG ................................................................................. 11<br /> 1.1 Định nghĩa mô phỏng thuật toán .................................................................. 11<br /> 1.2 Mục đích của mô phỏng thuật toán .............................................................. 12<br /> 1.3. Yêu cầu về mô phỏng thuật toán .................................................................. 12<br /> <br /> -1-<br /> <br /> Báo cáo khoa học: Lý thuyết và mô phỏng cây AVL<br /> <br /> Nguyễn Thị Thu Hương – Ak54 -CNTT<br /> <br /> a. Phản ánh đúng nội dung của thuật toán .................................................. 12<br /> b. Có thể thực hiện giải thuật theo từng bước 1 để theo dõi giá trị của các<br /> biến và các đối tương trong bài toán ........................................................... 12<br /> c. Có hình ảnh động (có thể có âm thanh khi cần) để mô tả trực tiếp quá trình<br /> thi hành của thuật toán. ............................................................................... 12<br /> d. Có thể kiểm định thuật toán trong trường hợp ngẫu nhiên, trường hợp xấu<br /> nhất, trường hợp tốt nhất. ............................................................................ 13<br /> e. Tạo mức độ sử dụng khác nhau cho người học ........................................ 13<br /> II. PHÂN TÍCH THIẾT KẾ .................................................................................. 13<br /> 2.1. Cấu trúc dữ liệu lưu trữ .............................................................................. 13<br /> a. Ngôn ngữ lập trình được sử dụng ............................................................ 13<br /> b.Phân tích giải thuật đưa ra cấu trúc dữ liệu ............................................. 13<br /> 2.2. Xây dựng mô hình mô phỏng dữ liệu vào và dữ liệu ra ............................... 17<br /> a.Vậy chúng ta phải xây dựng 3 mẫu dữ liệu vào: ....................................... 17<br /> b.Xây dựng mẫu dữ liệu ra: ......................................................................... 18<br /> 2.3. Sản phẩm mẫu............................................................................................. 19<br /> 2.4. Đánh gía và ý tưởng phát triển ................................................................... 20<br /> TÀI LIỆU THAM KHẢO ...................................................................................... 21<br /> <br /> -2-<br /> <br /> Báo cáo khoa học: Lý thuyết và mô phỏng cây AVL<br /> <br /> Nguyễn Thị Thu Hương – Ak54 -CNTT<br /> <br /> LÝ THUYẾT VÀ MÔ PHỎNG CÂY AVL<br /> PHẦN MỞ ĐẦU<br /> Lý do chọn đề tài<br /> <br /> Hiện nay, công nghệ thông tin với tốc độ phát triển rất nhanh. Các nhà khoa<br /> học khẳng định rằng chưa có một ngành khoa học - công nghệ nào lại có nhiều ứng<br /> dụng như công nghệ thông tin. Việc ứng dụng công nghệ thông tin vào trong giáo<br /> dục đã trở thành mối ưu tiên hàng đầu của nhiều quốc gia trong đó có Việt Nam.<br /> Trong quá trình học các giải thuật nói chung và môn cấu trúc dữ liệu nói<br /> riêng, chúng ta rút ra một nhận định chung là: nhiều giải thuật phức tạp trừu tượng,<br /> khó hiểu, khó hình dung vấn đề. Do đó chúng ta luôn mong muốn trong quá trình<br /> học giải thuật nên có những mô phỏng trực quan để chúng ta có thể tiếp thu giải<br /> thuật một cách dễ dàng hơn. Tuy nhiên, việc học tốt giải thuật có rất nhiều thận lợi<br /> dó là giúp cho quá trình tư duy giải thật tốt hơn, phát hiện vấn đề nhanh hơn, đặc<br /> biệt giúp cho việc học các môn học khác có tính logic cao được thuận lợi hơn.<br /> Nhưng để học tốt giải thuật thì không dễ dàng với nhiều người. Vậy để giúp người<br /> học tiếp thu một cách dễ dàng các giải thuật thì phải xây dựng các phần mền mô<br /> phỏng thuật toán.<br /> Cây AVL là loại cây nhị phân tự cân bằng, là một loại cấu trúc dữ liệu được<br /> ứng dụng rất nhiều trong công việc tìm kiếm. Cây nhị phân tìm kiếm với ưu điểm<br /> thực hiện dễ dàng phép bổ sung và loại bỏ đã tỏ ra là khá thuận tiện trong việc xử lý<br /> các bảng biến động. Tuy nhiên nếu cây phát triển tự nhiên thì khuynh hướng suy<br /> biến có thể xuất hiện và điều đó làm cho người dùng lo ngại. Còn nếu muốn luôn đạt<br /> được chi phí tối thiểu thì đòi hỏi cây phải luôn được “cân đối” (Như cây nhị phân<br /> hoàn chỉnh và cây nhị phân gần đầy) Nhưng như ta đã biết, việc sửa lại cây cho cân<br /> đối nếu tiến hành thường xuyên sẽ gây tổn phí khá nhiều thời gian và công sức. Vì<br /> vậy cần phải đi tới một giải pháp dung hoà: Giảm bớit sự chặt chẽ của tính “cân đối”<br /> để tránh được khả năng suy biến của cây. Năm 1962 P.M . Adelson – Velski – EM.<br /> Landis đã mở đầu phương hướng giải quyết này bằng cách đưa ra một dạng cây cân<br /> đối mới mà sau này được mang tên họ, đó là cây nhị phân tìm kiếm cân đối AVL.<br /> Tính ứng dụng của cây AVL là rất lớn, nhưng trong chương trình chúng ta chưa<br /> được học, nên em mong muốn làm mô phỏng giải thuật về cây AVL để người học có<br /> <br /> -3-<br /> <br /> Báo cáo khoa học: Lý thuyết và mô phỏng cây AVL<br /> <br /> Nguyễn Thị Thu Hương – Ak54 -CNTT<br /> <br /> thể nắm được loại cấu trúc dữ liệu này và áp dụng nó trong việc giải quyết các bài<br /> toán của mình.<br /> PHẦN 1: LÝ THUYẾT<br /> I. CÂY NHỊ PHÂN TÌM KIẾM<br /> 1.1. Định nghĩa và các khái niệm về cây nhị phân<br /> Cây nhị phân là cây mà các nút chỉ có tối đa 2 con<br /> Đối với cây con có một nút thì người ta phân biệt cây con trái và cây con<br /> phải. Vì vây cây nhị phân là cây có thứ tự<br /> Số nút ở mức i