TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Trần Minh Thái (2016)
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Cây nhị phân tìm kiếm – Cây cân bằng" cung cấp cho người học các khái niệm cây AVL, đặc điểm, định nghĩa cấu trúc dữ liệu, các kỹ thuật cân bằng cây, chèn phần tử vào cây, xóa phần tử khỏi cây. . | Chương 5. Cây nhị phân tìm kiếm – Cây cân bằng Trần Minh Thái Email: minhthai@ Website: 1 Nội dung Khái niệm cây AVL Đặc điểm Định nghĩa cấu trúc dữ liệu Các kỹ thuật cân bằng cây Chèn phần tử vào cây Xóa phần tử khỏi cây 2 2 Cây nhị phân tìm kiếm cân bằng Phát minh: Nhà toán học Nga G. M. Adel’Son-Vel’Skil và E. M. Landis (1962) Cấu trúc cây giúp tối ưu thời gian tìm kiếm Cây nhị phân tìm kiếm cân bằng: cây AVL Chi phí tìm kiếm, thêm mới, xoá trong cây n nút là O(log n) 3 Định nghĩa Cây AVL là một cây nhị phân tìm kiếm Chiều cao cây con trái và phải của nút gốc hơn kém nhau không quá 1 Cả hai cây con trái và phải cũng phải là cây AVL 4 Chỉ số cân bằng (Balance factor) Chỉ số cân bằng (bF – balance Factor) của một nút: bF = hL – hR hL: chiều cao cây con trái hR: chiều cao cây con phải Có 3 trường hợp: bF = 0: hL = hR bF > 0: hL > hR bF { private T data; private int height; private CMyAVLNode pLeft = null; private CMyAVLNode pRight = null; //Các property get/ set //Các phương thức } Constructor cho node 7 public CMyAVLIntNode(T x) { data = x; height = 1; pLeft = null; pRight = null; } Trường hợp 1: Lệch trái 8 Lệch trái – trái Lệch trái – phải Trường hợp 2: Lệch phải 9 Lệch phải – trái Lệch phải – phải Lệch trái - trái 10 Quay phải Lệch trái – phải: Thực hiện quay kép 11 B1. Quay trái Lệch trái – phải: Thực hiện quay kép 12 B2. Quay phải Thêm 1 node vào cây AVL Tương tự như trên cây NPTK Sau khi thêm xong, nếu chiều cao của cây thay đổi. Nếu có mất cân bằng cân bằng lại ở nút này Phương thức InsertNode trả về node root mới sau khi cân bằng 13 Bài tập 1 Cho dãy số: 45, 46, 70, 11, 13, 42, 21, 9, 25, 4 Hãy trình bày từng bước quá trình xây dựng cây AVL Trình bày từng bước duyệt cây theo thứ tự sau 14 Xác định chỉ số cân bằng 15 int GetBalance(CMyAVLNode N) { if (N == null) return 0; return Height() - Height(); } int Height(CMyAVLNode N) { if (N == null) return 0; return ; } Phương thức xoay phải 16 public CMyAVLNode RightRotate(CMyAVLNode T) { CMyAVLNode T1 = ; CMyAVLNode RT1 = ; = T; = RT1; = Max(Height(), Height()) + 1; = Max(Height(), Height()) + 1; return T1; } Phương thức xoay trái 17 public CMyAVLNode LeftRotate(CMyAVLNode T) { CMyAVLNode T1 = ; CMyAVLNode LT1 = ; = T; = LT1; = Max(Height(), Height()) + 1; = Max(Height(), Height()) + 1; return T1; } 18 public CMyAVLNode Insert(CMyAVLNode node, T x) { if (node == null) return (new CMyAVLNode(x)); if ( == x) return node; if (x 1 && x )//RR return LeftRotate(node); if (balance > 1 && x > )//LR { = LeftRotate(); return RightRotate(node); } if (balance < -1 && x < )//RL { = RightRotate(); return LeftRotate(node); } return node; } Hủy 1 node trên cây Tương tự như trên cây NPTK Sau khi hủy, nếu mất cân bằng cân bằng lại Hàm DeleteNode trả về node root sau khi cân bằng 20 Bài tập 2 1. Hãy trình bày từng bước quá trình: Xóa node có giá trị 13 Xóa node có giá trị 45 2. Trình bày thuật toán và cài đặt phương thức xóa node trên cây AVL 21
đang nạp các trang xem trước
