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

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ó
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.
- 3 -
Lý thuyết và mô phỏng cây AVL Nguyễn Thị Thu Hương – Ak54 -CNTT
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.

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
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.
- 5 -
Lý thuyết và mô phỏng cây AVL Nguyễn Thị Thu Hương – Ak54 -CNTT
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).

n)
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:
- 7 -
Lý thuyết và mô phỏng cây AVL Nguyễn Thị Thu Hương – Ak54 -CNTT
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.
TH1
- 8 -