Hoàn tất bài thực hành này, sinh viên có thể: Hiểu được các thao tác quay cây (quay trái, quay phải) để hiệu chỉnh cây thành cây cân bằng, cài đặt hoàn chỉnh cây cân bằng AVL. . | CÂY CÂN BẰNG AVL B M C TIÊU Hoàn tất bài thực hành này, sinh viên có thể: c th - Hiểu được các thao tác quay cây (quay trái, quay phải) để hiệu chỉnh cây thành cây cân c ph nh bằng. b Cài đặt hoàn chỉnh cây cân bằng AVL. Thời gian thực hành: 120 phút – 360 phút Lưu ý: Sinh viên phải thực hành bài tập về Cây nhị phân và Cây nhị phân tìm kiếm trước khi c t ki làm bài này. TÓM T T Cây cân bằng AVL là cây nhị phân tìm kiếm (NPTK) mà tại mỗi đỉnh của cây, độ cao của cây con ki trái và cây con phải khác nhau không quá 1 1. Ví dụ 1: cây cân bằng AVL Ví dụ 2: cây không cân bằng Khi thêm node mới vào cây AVL có thể xảy ra các trường hợp mất cân bằng như sau i th ng sau: Mất cân bằng phải-trái (R-L) Mất cân bằng trái-trái (L-L) Mất cân bằng trái-phải (L-R) Trang 1 Mất cân bằng phải-phải (R-R) Tài li u hư ng d n th c hành môn C u trúc d li u và gi i thu t ụng Xử lý mất cân bằng bằng cách sử dụ các phép quay cây a. Quay trái b. Quay phải Xử lý cụ thể cho các trường hợp mất cân b t bằng như sau: MẤT CÂN BẰNG PHẢI Mất cân bằng phải-trái (R-L) Mất cân bằng phải-phải (R-R) bị - Quay phải tại node con phải của i ph - Quay trái tại node b mất cân bằng node bị mất cân bằng ất - Quay trái tại node bị mấ cân bằng MẤT CÂN BẰNG TRÁI Mất cân bằng trái-phải (L-R) Mất cân bằng trái-trái (L-L) - Quay trái tại node con trái của i - Quay phải tại node bị mất cân i b bằng - node bị mất cân bằng Quay phải tại node bị m cân bằng mất Giống với cây NPTK, các thao tác trên cây cân bằng bao gồm: , b - Thêm phần tử vào cây Tìm kiếm 1 phần tử trên cây Duyệt cây Xóa 1 phần tử trên cây N I DUNG TH C HÀNH Tổ chức một cây cân bằng AVL trong đó mỗi node trên cây chứa thông tin dữ liệu nguyên. m u Tài li u hư ng d n th c hành môn C u trúc d li u và gi i thu t Trang Sinh viên đọc kỹ phát biểu bài tập và thực hiện theo hướng dẫn: p th 2 Cơ bản Người dùng sẽ nhập các giá trị nguyên từ bàn phím. Với mỗi giá trị nguyên được nhập vào, phải tạo cây AVL theo đúng tính chất của nó. Nếu .
