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 Nguyễn Thị Thu Hương – Ak54 -CNTT - 1 - 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 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 - 2 - 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 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 - 3 - 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ó 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 - 4 - 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 <= 2i. Số nút ở mức lá <= 2h-1, với h là chiều cao của cây. Chiều cao của cây h >= log2(số nút trong cây). Số nút trong cây <= 2h-1. Hình ảnh cây nhị phân: 1.2 Cây nhị phân tìm kiếm a. Định nghĩa và tính chất 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 - 5 - Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm: Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N. Trong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét CNPTK. b.Giải thuật tìm kiếm Giả sử, ta muốn biết liệu trên cây tìm kiếm nhị phân có nút nào chứa khoá K hay không. Ta sẽ bắt đầu duyệt từ nút gốc của cây (Nút gốc có khoá N). Nếu K > N, thì chuyển sang nhánh phải và tiếp tục quá trình so sánh. Nếu K < N, thì chuyển sang nhánh trái và tiếp tục quá trình so sánh. Quá trình tìm kiếm sẽ dừng lại, khi xảy ra một trong hai trường hợp sau: K = N. Tức là tìm thấy nút có giá trị khoá bằng K. Con trỏ trỏ đến Null. Tức là, trên cây tìm kiếm nhị phân không có nút nào có giá trị khoá bằng K 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 - 6 - c. Giải thuật bổ sung Dựa vào giá trị khoá của nút cần chèn để xác định vị trí chính xác của nút đó. Giả sử nút cần chèn có giá trị khoá là V, nút gốc của cây có giá trị khoá là N. Nếu V>N thì ta đi theo nhánh phải và tiếp tục quá trình so sánh. Nếu V < N thì ta đi theo nhánh trái và tiếp tục quá trình so sánh. Quá trình này sẽ dừng lại khi xảy ra một trong hai trường hợp sau: V = N. Trong trường hợp này, dữ liệu cần chèn đã có trong cây. Vì vậy, ta không cần chèn thêm nút mới. Con trỏ trỏ đến Null. Tức là ta đã tìm đến vị trí chính xác cho nút mới. d. Giải thuật loại bỏ Giả sử ta muốn xóa một nút có nhãn là x, ta tiến hành tìm kiếm trên cây bắt đầu từ nút gốc: nếu nhãn x lớn hơn nhãn của nút gốc thì ta tìm sang cây con bên phải, ngược lại thì ta sẽ tìm sang cây con bên trái. Nếu không tìm thấy thì giải thuật kết thúc. Nếu tìm gặp thì có 3 trường hợp sau : Nếu x là lá thì ta thay x bằng Nil. Nếu x chỉ có một nút con thì ta thay x bằng nút con của nó. Nếu x có 2 con thì ta thay x bằng nút lớn nhất trên cây con bên trái (nút cực phải của cây trái) hoặc nút bé nhất trên cây con bên phải của x (nút cực trái của cây phải). f. Phân tích đánh giá Tất cả các thao tác tìm kiếm, bổ sung, loại bỏ trên CNPTK đều có độ phức tạp trung bình O(h), với h là chiều cao của cây Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự. Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK (khi mà mỗi nút đều chỉ có 1 con trừ nút lá). Lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n). 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 - 7 - II. CÂY NHỊ PHÂN CÂN BẰNG 2.1. Cây nhị phân cân bằng hoàn toàn (CCBHT) a. Định nghĩa: Cây cân bằng hoàn toàn là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải. b. Đánh giá: Một cây rất khó đạt được trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi thêm hay hủy các nút trên cây có thể làm cây mất cân bằng (xác suất rất lớn), chi phí cân bằng lại cây lớn vì phải thao tác trên toàn bộ cây. Tuy nhiên nếu cây cân đối thì việc tìm kiếm sẽ nhanh. Đối với cây cân bằng hoàn toàn, trong trường hợp xấu nhất ta chỉ phải tìm qua log2n phần tử (n là số nút trên cây). Do CCBHT là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. Nhưng ưu điểm của nó lại rất quan trọng. Vì vậy, cần đưa ra một CTDL khác có đặc tính giống CCBHT nhưng ổn định hơn. Như vậy, cần tìm cách tổ chức một cây đạt trạng thái cân bằng yếu hơn và việc cân bằng lại chỉ xảy ra ở phạm vi cục bộ nhưng vẫn phải bảo đảm chi phí cho thao tác tìm kiếm đạt ở mức O(log2 n). 2.2. Cây nhị phân tự cân bằng (AVL) a. Định nghĩa Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Cây cân bẳng hoàn toàn là cây AVL, nhưng cây AVL chưa chắc đã là cây cân bằng hoàn toàn. Tính cân đối của cây AVL nhẹ hơn so với tính cân đối của cây nhị phân cân bằng hoàn toàn. Cây nhị phân tìm kiếm mà luôn có dạng cân đối AVL, thì chi phí tìm kiếm đối với nó ngay trong trường hợp xấu nhất vẫn là O(log2n) 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 - 8 - Từ khi được giới thiệu, cây AVL đã nhanh chóng tìm thấy ứng dụng trong nhiều bài toán khác nhau. Vì vậy, nó mau chóng trở nên thịnh hành và thu hút nhiều nghiên cứu. Từ cây AVL, người ta đã phát triển thêm nhiều loại CTDL hữu dụng khác như cây đỏ-đen (Red-Black Tree), B-Tree, b. Các trường hợp gây mất cân bằng trên cây AVL Trường hợp 1: Cây lệch trái: Trường hợp 2: Cây lệch phải: Ta có thể thấy rằng các trường hợp lệch về bên phải hoàn toàn đối xứng với các trường hợp lệch về bên trái. Vì vậy ta chỉ cần khảo sát trường hợp lệch về bên trái. 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 - 9 - TH1 TH2 TH3 b. Giải thuật bổ sung trên cây AVL Việc đi theo đường tìm kiếm trên cây để thấy được khoá mới chưa có sẵn trên cây và biết được “chỗ” để bổ sung nó vào, tất nhiên được thực hiện tương tự như việc bổ sung 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 - 10 - một node vào trong cây nhị phân. Sau khi node mới được bổ sung, có ba tình huống có thể xảy ra với các node tiền bối của nó. Để tiện trình bày, ta giả sử phép bổ sung được thực hiện vào phía trái. Như vậy ba tình huống đó có thể nêu cụ thể như sau: Tình huống 1: Cây con phải đã cao hơn 1 (lệch phải) sau phép bổ sung chiều cao hai cây con bằng nhau. Trường hợp này ta chỉ cần chỉnh lại hệ số cân bằng tại nút đang xét. Tình huống 2: Chiều cao của hai cây con vốn đã bằng nhau, sau phép bổ sung cây con trái cao hơn 1 (lệch trái). Trường hợp này chiều cao của cây gốc là node đang xét bị thay đổi, nên không chỉ phải chỉnh lý hệ số cân đối nút đang xét mà còn phải chỉnh lý hệ số cân đối ở các node tiền bối của nó. Tình huống 3: Cây con trái đã cao hơn 1 (lệch trái), sau phép bổ sung nó cao hơn 2: tính “cân bằng AVL” bị phá vỡ. vậy ta phải cân bằng lại bằng phép xoay.Có hai trường hợp phải xử lý khác nhau: TH1: Node mới bổ sung làm tăng chiều cao cây con trái của node con trái node bất thường. Tái cân bằng giống như trong trương hợp 1 TH2: Node mới bổ sung làm tăng chiều cao cây con phải của node con trái node bất thường. Tái cân bằng giống như tring tường hợp 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 - 11 - c. Giải thuật loại bỏ trên cây AVL Loại bỏ giống như giải thuật loại bỏ của cây nhị phân, chỉ khác là sau khi loại bỏ cây bị mất cân đối và phải tái cân đối bằng phép quay như đã làm khi bổ sung. Việc huỷ 1 nút có thể phải cân bằng dây chuyền các nút từ gốc cho đên phần tử bị huỷ trong khi thêm vào chỉ cần 1 lần cân bằng cục bộ. d .Đánh giá Cây cân bằng có CTDL ổn định hơn hẳn CCBHT vì chỉ khi thêm hủy làm cây thay đổi chiều cao các trường hợp mất cân bằng mới có khả năng xảy ra. Cây AVL với chiều cao được khống chế sẽ cho phép thực thi các thao tác tìm thêm hủy với chi phí O (log2(n)) và bảo đảm không suy biến thành O(n). PHẦN 2: MÔ PHỎNG I. LÝ THUYẾT MÔ PHỎNG 1.1 Định nghĩa mô phỏng thuật toán Mô phỏng thuật toán là quá trình tách dữ liệu, thao tác và tạo giao diện đồ hoạ mô phỏng cho quá trình đó. 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 - 12 - 1.2 Mục đích của mô phỏng thuật toán Mô phỏng thuật toán sử dụng đồ hoạ để mô tả các cấu trúc dữ liệu bên trong của thuật toán được thực hiện trong chương trình và biểu diễn sự thay đổi của các cấu trúc dữ liệu trong mỗi trạng thái thực thi và các hoạt động của chương trình. Trong suốt quá trình mô tả, người sử dụng có thể thấy từng bước thực hiện của chương trình và có thể thấy được những chi tiết nhỏ của thuật toán và hiểu sâu hơn về nó. Vì thế, mô phỏng thuật toán giúp cho người sử dụng hiểu thuật toán. Trong quá trình mô phỏng, người sử dụng có thể thấy chương trình của họ được thi hành như thế nào, đánh giá sự thay đổi của dữ liệu qua mỗi bước và nó sẽ ảnh hưởng đến bước tiếp theo như thế nào. Nó giúp người sử dụng phát hiện ra lỗi của chương trình (nếu có), Từ đó có thể tìm ra lỗi và sửa lại chương trình để nó chạy chính xác và ổn định hơn. 1.3. Yêu cầu về mô phỏng thuật toán a. Phản ánh đúng nội dung của thuật toán Thuật toán được mô phỏng phải chính xác, các bước của thuật toán phải trực quan và phản ánh đứng nội dung của thuật toán để thể hiện tính đúng đắn của thuật toán. 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 Quá trình mô phỏng có thể diễn ra liên tục, biểu diễn thuật toán từ đầu đến cuối. Tuy nhiên, trong quá trình mô phỏng thuật toán chúng ta đều có nhu cầu theo dõi các bước của giải thuật xem nó chạy đúng hay chưa, các biến và các đối tượng thay đổi như thế nào. Do đó trong khi thiết kế giải thuật chương trình cần phải có nút tạm dừng để dừng chương trình và nút tiếp tục để tiếp tục quá trình mô phỏng. 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. Quá trình mô tả trực quan quá trình thì hành của thuật toán là để biết bản chất bên trong của vấn đề là gì, điều này đồng nghĩa với việc phải có hình ảnh động để mô tả thuật 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 - 13 - toán hoạt động như thế nào, các biến thay đổi ra sao. từ đó mới kích thích tư duy sáng tạo của học sinh và thu hút sự chú ý của người học. Bên cạnh đó để cho quá trình mô phỏng thêm sinh động chúng ta có thể chèn thêm âm thanh vào phần mềm, có các nút chỉnh âm thanh để lúc nào cần chúng ta có thể bật hay tắt một cách chủ động. 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. Để kiểm định thuật toán thì ta phải thử với các bộ dữ liệu vào ngẫu nhiên hoặc các bộ dữ liệu mẫu hoặc các bộ dữ liệu do người dùng nhập vào. Nếu kết quả chạy chương trình vẫn ổn định và thuật toán vẫn đúng đắn thì khi đó chương trình mới được đánh giá cao. e. Tạo mức độ sử dụng khác nhau cho người học Do đối tượng người học có trình độ nhận thức khác nhau (tốt, khá, trung bình, yếu). Để tạo mức độ sử dụng khác nhau cho người học, trong chương trình thiết kế mô phỏng cần đặt thời gian để chạy chương trình (nhanh, trung bình, chậm) để phủ hợp với sự theo dõi và tiếp thu giải thuật của từng đối tượng người học. II. PHÂN TÍCH THIẾT KẾ 2.1. Cấu trúc dữ liệu lưu trữ a. Ngôn ngữ lập trình được sử dụng Visual FoxPro là một trong các ngôn ngữ lập trình quản trị dữ liệu lâu đời, ngoài ra Visual FoxPro còn là một ngôn ngữ lập trình hướng đối tượng. Nó có khả năng tạo ra các lớp đối tượng, điều khiển chương trình thông qua các tác vụ của đối tượng. Đối tượng mà Visual FoxPro tạo ra đa dạng, phong phú, có thể chứa các hình ảnh sống động, rất thích hợp cho việc mô phỏng thuật toán. Là một ngôn ngữ lập trình phù hợp cho việc tạo ra các phần mềm dạy học. b.Phân tích giải thuật đưa ra cấu trúc dữ liệu Cây AVL được cài đặt bằng con trỏ. Mỗi nút của cây là một đối tượng có tên là NODE gồm Các thuộc tính sau: 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 - 14 - Thuộc tính Ý nghĩa Thuộc tính Ý nghĩa Value_n Giá trị của Node Child_l Con trái của node Child_r Con phải của node Parent_n Cha của node Canh Cạnh nối với cha của nó Hs_canbang Hệ số cân bằng x hoành độ nút trên form y tung độ nút trên form Trong trường hợp node không có con trái, hoặc không có con phải. thì thuộc tính Child_l, Child_r sẽ trỏ đến NULL. Vấn đề đặt ra: là làm thế nào để hiển thị được một cây nhị phân cân đối, phù hợp với kích thước của Form. Vì vậy ta sẽ sử dụng cách duyệt sau. Tức là sẽ tính toạ độ của các con trước, toạ độ của node sẽ được tính như sau: node.x = (node.child_l.x + node.child_r.y)/2; node.y = node.child_l.y – dy(dy: chính là khoảng cách giữa node và hai con của nó). Các node là là thì cách nhau một khoảng là dx. Nhưng cách tính toạ độ này chỉ phù hợp với cây nhị phân mà các node của nó phải có đầy đủ 2 con. Nhưng cây AVL thì chưa chắc đã thoả mãn điều này. Giải quyết vấn đề: Bằng cách nào đó chúng ta sẽ làm cho tất cả các nút đều có đầy đủ lá. Vì thế ta xây dựng một đối tượng có tên là NULL, đối tượng này được sử dụng làm lá của tất cả các nút có con trái hoặc con phải là NULL. Đối tượng NULL gồm có các thuộc tính sau: Thuộc tính Ý nghĩa Thuộc tính Ý nghĩa Paretn_n Trỏ tới cha của nó x, y Toạ độ trên Form Trong trường hợp nút là gốc, tức là node đó không có cha thì thuộc tính Parent_n sẽ trỏ đến giá trị là .F. Sở dĩ chúng ta thêm thuộc tính Parent_n vào để thuận tiện hơn cho việc tái cân bằng cho cây AVL 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 - 15 - Thuộc tính cạnh là một đối tượng line: Có tác dụng nối giữa node đó và cha của nó. Thuộc tính Hs_canbang: sẽ nhận giá trị từ -2 -> 2. -2: Cây con phải cao hơn 2 so với cây con trái -1: Cây con phải cao hơn 1 so với cây con trái 0: Cây con trái và cây con phải có chiều cao bằng nhau 1: Cây con trái cao hơn 1 so vơi cây con phải 2: Cây con trái cao hơn 2 so vơi cây con phải Vấn đề đặt đặt ra: Trường hợp hệ số cân bằng của nút bằng -2 và 2 là các trường hợp cây bị mất cân đối. Cần phải tái cân đối lại cây bằng các phép xoay Giải quyết vấn đề: ta xây dựng phương thức Quay_trai, Quay_phai đối với từng nút. Trong phép Quay_trai: Con trái sẽ được đưa lên vị trí của nút Quay trái Các bước thực hiện Node1. Parent_n = node2.Parent_n IF Node2 != gốc THEN {Node1.parent_n.child_l = Node1 (Node1.parent_n.child_r = Node1)} Node2.child_l = Node1.child_r Node2.child_l.parent_n=Node2 Node1.child_r = node2 Node2.parent_n = Node1 Trong phép Quay_phai: Con phải sẽ đưa lên vị trí của nút 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 - 16 - Quay phải Các bước thực hiện Node2. Parent_n = node1.Parent_n IF Node1 != gốc THEN {Node2.parent_n.child_l = Node2 (Node2.parent_n.child_r = Node2)} Node1.child_r = Node2.child_l Node1.child_r.parent_n=Node1 Node2.child_l = node1 Node1.parent_n = Node2 Ta có hàm: add_ node(Nkey): tạo ra một node mới có giá trị là nkey, đồng thời với việc tạo ra node mới thì ta cũng tạo ra một node Null, nốt Null sẽ được gán làm con trái của node mới sinh ra. Node mới sinh ra bao giờ cũng có vị trí tai gốc. Gốc chính là một điểm mốc mà ta chọn để đánh dấu toạ độ của ROO. Ta có hàm: add_ nkey(Nkey, onode): hàm này có tác dụng thêm vào cây onode một nút có giá trị là nkey. Bước 1: Tìm vị trí Nkey được thêm vào qua hàm tim_vi_tri(nkey): Hàm này sẽ thể hiện quá trình tìm vị trí cần chèn vào. Lúc này sẽ có một Node có nhãn là Nkey di chuyển. Node có nhãn là Nkey này chính là một biến của form có tên là Newnode1, sau khi tìm được vị trí thì Newnode1 sẽ biến mất. Bước 2: Nếu onode là Null thì gọi đến hàm newnode= add_ node(Nkey). Sau đó thay Newnode vào vị trí của Onode. Onode được gán làm child_r của newnode. Nếu onode không Null thì gọi đến add_nkey(nkey, onode.child_l) hoặc add_nkey(nkey, onode.child_r) tuỳ vào giá trị của nkey. 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 - 17 - Bước 3: Hiển thị cây mới. Bước 4: Kiểm tra tính cân bằng của cây, nếu mất cân bằng thì tái cân bằng lại, quá trình này được thực hiện qua hàm Test(Onode): Hàm này kiểm tra tính cân bằng, nếu không cân bằng thì tái cân bằng, sau đó hiển thị cây mới sau khi đã cân bằng. Hàm Test(Onode): Hàm này sẽ tự phân ra các trường hợp mất cân bằng để tái cân bằng lại. Giá trị của Onode ban đầu chính là Node mới thêm vào. Hàm sẽ đi lên đến các node tiền bối của Onode, lần lượt kiểm tra tính cân bằng và tái cân băng khi gặp mất cân bằng. 2.2. Xây dựng mô hình mô phỏng dữ liệu vào và dữ liệu ra Trong các yêu cầu của mô phỏng thuật toán có yêu cầu: 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, tốt nhất. Ta có mô hình mô phỏng dữ liệu vào và dữ liệu ra như sau: a.Vậy chúng ta phải xây dựng 3 mẫu dữ liệu vào: Dữ liệu mẫu: là dữ liệu đã được ghi lại từ trước, khi muốn sử dụng chỉ việc lấy ra. Có tác dụng là cho người sử dụng đỡ mất công nhập lại dữ liệu (trong trường hợp dữ liệu quá lớn thì mất thời gian), hoặc để kiểm định thuật toán trong các trường hợp xấu, trung bình hoặc tốt. 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 - 18 - Dữ liệu sinh ngẫu nhiên: do sử dụng hàm Random để sinh giá trị của dữ liệu hạn chế trong một khoảng nào đó, hoặc mặc định sinh bao nhiêu tuỳ theo mong muốn của người lập trình. Dữ liệu nhập trực tiếp: là dữ liệu do người dùng nhập vào từ bàn phím, đa số thì dạng dữ liệu này thường được sử dụng vì người dùng muốn kiểm định dữ liệu do chính mình nhập vào. Người dùng có thể sinh dữ liệu từng Node 1, hoặc có thể sinh dữ liệu cùng một lúc nhiều node. b.Xây dựng mẫu dữ liệu ra: Phần mềm mô phỏng phải có hình ảnh động để mô tả trực quan quá trình thi hành của thuật toán. Vì thế kết quả chạy chương trình phải diễn ra từ từ. Khi thêm một nút thì ta phải mô tả trực quan quá trình tìm vị trí của nút, tức là nút di chuyển chậm, tìm vị trí, sau đó thêm vào vị trí đã tìm được. Vậy trong đối tượng NODE ta phải xây dựng một hàm di chuyển Di_chuyen(x,y): Có tác dụng di chuyển node từ vị trí cũ đến toạ độ (x,y): Thủ tục WAIT '' TIMEOUT Time: có tác dụng cho đoạn chương trình rừng lại trong khoảng thời gian time giây. Vậy quá trình di chuyển của một node là dịch chuyển từng đoạn dx, dy nhỏ,cho chương trình rừng lại bao nhiêu thời gian tuỳ người lập trình, hoặc người dùng có thể chọn chương trình chạy nhanh, bình thường hay chậm là tuỳ ý. Cách tính dx, dy: Chương trình Giải thích If Abs(x0-x)>Abs(y0-y) If x>x0 dx=h Else dx=-h Endif so_buoc=Abs(Int((x- Kiểm tra xem, vị trí di chuyển đến thì tung độ có khoảng cách lớn hơn, hay hoành độ lớn hơn. Lấy khoảng cách lớn hơn để từ đấy tính số bước. làm như thế thì đối tượng mới di chuyển mịn và đẹp hơn. Khi biết dx thì tính được dy: 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 - 19 - x0)/dx)) dy=dx*(y-y0)/(x-x0) Else If y>y0 dy=h Else dy=-h Endif so_buoc=Abs(Int((y- y0)/dy)) dx=dy*(x-x0)/(y-y0) Endif Dy = dx*(y-y0)/(x- x0) Khi biết dy thì tính đựoc dx: Dx= dy*(x-x0)/(y-y0) dx>0 nếu x>x0 và ngược lại dy>0 nếu y>y0 và ngược lại Phải mô phỏng quá trính quay trái, quay phải một cách trực quan để học sinh hiểu được. Vậy sẽ có một Form để mô phỏng quá trình này. Do đây là phần mềm mô phỏng thuật toán cho học sinh, mà thuật toán thì khá trừu tượng thường gây khó khăn cho quá trình nhận thức của học sinh (nhất là với những học sinh yếu kém). Do đó phần mềm cần thiết kế sao cho giải thuật chia thành nhiều bước riêng rẽ để tại mỗi bước của giải thuật ta có thể giải thích cho người học thấy được bản chất bên trong của thuật toán (các biến đổi như thế nào, chạy ra sao) để từ đó người học sẽ dễ dàng tiếp thu giải thuật một cách dễ dàng và nhanh chóng. Thao tác xoá: viết cho sự kiện Click của chuột vào đối tượng NODE. 2.3. Sản phẩm mẫu Hình ảnh của form chính 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 - 20 - 2.4. Đánh gía và ý tưởng phát triển Ưu điểm: Phần mềm mô phỏng đã cho người dùng thấy được tổng quan về giải thuật của cây nhị phân tự cân bằng AVL. Phần mềm đã tạo được giao diện đồ hoạ thân thiện, dễ sử dụng, Người học có thể tiếp thu một cách nhanh chóng các tư tưởng của giải thuật Nhược điêm: Phần mềm mô phỏng chưa tiện dụng với người học. Chưa có thao tác kéo thả với từng đối tượng. Giao diện đồ học chưa sống động, mầu sắc chưa hài hoà. Phong cách lập trình chưa có tính chuyên nghiệp Phát triển: Phần mềm mô phỏng này sẽ được phát triển lên tiếp trong đề tài khoá luận: Phần mềm sẽ có khả năng kéo thả đối với từng đối tượng, sẽ có hệ thống menu chuyên nghiệp hơn, giao diện bao gổm cả hình ảnh động và âm thanh. Phát triển thành Phần mềm ứng dụng trong giảng dạy môn cấu trúc dữ liệu 2 cho sinh viên và học sinh. 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 - 21 - TÀI LIỆU THAM KHẢO [1].Thầy: Đỗ Xuân Lôi: “Cấu trúc dữ liệu và giải thuật”.Nhà xuất bản đại học quốc gia Hà Nội 1993 [2]. Thầy: Nguyễn Xuân Huy: “Thuật toán”. Nhà xuất bản thống kê – 1998 [3]. Cô: Trần Hạnh Nhi: “Cấu trúc dữ liệu”. Trung tâm phát triển công nghệ thông tin, chương trình đào tạo từ xa [4].Bách khoa toàn thư mở Wikipedia [5]. Thầy: Nguyễn Hữu Dung: “Lập trình hướng đối tượng trong Visual Foxpro”. Trường đại học Sư phạm Hà Nội [6] Thầy: Nguyễn Ngọc Minh: “Visual FoxPro 6.0” Nhà xuất bản Lao động – xã hội