TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Cây AVL (AVL tree) - ĐH KHTN TPHCM

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 .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cây AVL
• Cây nhị phân tìm kiếm
• Xây dựng cây cân bằng
• Thao tác tìm kiếm
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp