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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
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)Chương 5. Cây nhị phântìm kiếm – Cây cân bằngTrầnMinhTháiEmail:minhthai@huflit.edu.vnWebsite:www.minhthai.edu.vn 1Nội dung1. Khái niệm cây AVL2. Đặc điểm3. Định nghĩa cấu trúc dữ liệu4. Các kỹ thuật cân bằng cây5. Chèn phần tử vào cây6. Xóa phần tử khỏi cây 2Câ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 4Chỉ 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ảiCó 3 trường hợp: ØbF = 0: hL = hR ØbF > 0: hL > hR ØbF < 0: hL < hR 5Khai báo cấu trúc cây AVLclass CMyAVLNode{ 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} 6Constructor cho nodepublic CMyAVLIntNode(T x){ data = x; height = 1; pLeft = null; pRight = null;} 7Trường hợp 1: Lệch trái 1.1 Lệch trái – trái 1.2 Lệch trái – phải 8Trường hợp 2: Lệch phải 2.1 Lệch phải – trái 2.2 Lệch phải – phải 9Lệch trái - trái Quay phải 10Lệch trái – phải: Thực hiện quay kép B1. Quay trái 11Lệch trái – phải: Thực hiện quay kép B2. Quay phải 12Thê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 13Bài tập 1Cho 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 14Xác định chỉ số cân bằngint Height(CMyAVLNode N){ if (N == null) return 0; return N.Height;}int GetBalance(CMyAVLNode N){ if (N == null) return 0; return Height(N.PLeft) - Height(N.PRight);} 15Phương thức xoay phảipublic CMyAVLNode RightRotate(CMyAVLNode T){ CMyAVLNode T1 = T.PLeft; CMyAVLNode RT1 = T1.PRight; T1.PRight = T; T.PLeft = RT1; T.Height = Max(Height(T.PLeft), Height(T.PRight)) + 1; T1.Height = Max(Height(T1.PLeft), Height(T1.PRight)) + 1; return T1;} 16Phương thức xoay tráipublic CMyAVLNode LeftRotate(CMyAVLNode T){ CMyAVLNode T1 = T.PRight; CMyAVLNode LT1 = T1.PLeft; T1.PLeft = T; T.PRight = LT1; T.Height = Max(Height(T.PLeft), Height(T.PRight)) + 1; T1.Height = Max(Height(T1.PLeft), Height(T1.PRight)) + 1; return T1;} 17public CMyAVLNode Insert(CMyAVLNode node, T x){ if (node == null) return (new CMyAVLNode(x)); if (node.Data == x) return node; if (x < node.Data) node.PLeft = Insert(node.PLeft, x); else node.PRight = Insert(node.PRight, x); node.Height = 1 + Max(Height(node.PLeft),Height(node.PRight)); //Xác định chỉ số cân bằng int balance = GetBalance(node); 18 if (balance > 1 && x < node.PLeft.Data)//LL return RightRotate(node); if (balance < -1 && x > node.PRight.Data)//RR return LeftRotate(node); if (balance > 1 && x > node.PLeft.Data)//LR { node.PLeft = LeftRotate(node.PLeft); return RightRotate(node); } if (balance < -1 && x < node.PRight.Data)//RL { node.PRight = RightRotate(node.PRight); return LeftRotate(node); } return node;} 19Hủ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 ...