Cây AVL (AVL tree) là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao của cây con trái và cây con phải không chênh lệch quá 1. Trong chương này sẽ trình bày một số nội dung liên quan đến cây AVL như: Xây dựng cây cân bằng, các trường hợp mất cân bằng, xử lý mất cân bằng, thao tác tìm kiếm, thao tác thêm phần tử,. . | 47 AVL tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011 48 Do . Adelsen Velskii và . Lendis đưa ra vào năm 1962, đặt tên là cây AVL. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 1 49 Cây cân bằng AVL là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao của cây con trái và cây con phải không chênh lệch quá 1. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 50 Ví dụ : 12 12 8 11 5 4 8 18 17 5 7 4 Cây AVL? 2 18 11 17 7 Cây AVL? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 2 51 Việc xây dựng cây cân bằng dựa trên cây nhị phân tìm kiếm, chỉ bổ sung thêm 1 giá trị cho biết sự cân bằng của các cây con như thế nào. Cách làm gợi ý: struct NODE { Data key; NODE *pLeft, *pRight; int bal; }; Trong đó giá trị bal (balance, cân bằng) có thể là: 0: cân bằng; 1: lệch trái; 2: lệch phải Cấu trúc dữ liệu và giải thuật - HCMUS 2011 52 Mất cân bằng trái-trái (L-L) Mất cân bằn trái-phải (L-R) Mất cân bằng phải-phải (R-R) Mất cân bằng phải-trái (R-L) Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 3 53 Mất cân bằng trái-trái (L-L) 12 18 17 5 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 54 Mất cân bằng trái-phải (L-R) 12 18 17 5 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 4 55 Mất cân bằng phải-phải (R-R) 12 8 11 5 22 25 7 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 56 Mất cân bằng phải-trái (R-L) 12 8 11 5 4 7 22 20 Cấu trúc dữ liệu và giải thuật - HCMUS .
