LÝ THUYẾT VÀ MÔ PHỎNG CÂY AVL.doc

Lý thuyết và mô phỏng cây AVL Nguyễn Thị Thu Hương – Ak54 -CNTT

MỤC LỤC

MỤC LỤC ....................................................................................................................... 1

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 ........................................................................................... 5

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 .................................................................................. 6

2.1. Cây nhị phân cân bằng hoàn toàn (CCBHT) .................................................... 6

a. Định nghĩa: ...................................................................................................... 6

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 .......................................... 7

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 ................................................................... 10

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 ................................................................... 11

1.3. Yêu cầu về mô phỏng thuật toán ...................................................................... 12

- 1 -

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. .................................................................................. 12

e. Tạo mức độ sử dụng khác nhau cho người học ........................................... 12

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 ................................. 16

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: .............................................................................. 17

2.3. Sản phẩm mẫu ................................................................................................... 19

2.4. Đánh gía và ý tưởng phát triển ......................................................................... 19

TÀI LIỆU THAM KHẢO ............................................................................................. 20

- 2 -