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