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 - Phần 2: Cây cân bằng - Trần Minh Thái

Chương 5. Cây nhị phân tìm kiếm – Cây cân bằngTrần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn1Nội dungKhái niệm cây AVLĐặc điểmĐịnh nghĩa cấu trúc dữ liệuCác kỹ thuật cân bằng câyChèn phần tử vào câyXóa phần tử khỏi cây2Cây nhị phân tìm kiếm cân bằngPhá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ếmCây nhị phân tìm kiếm cân bằng: cây AVLChi phí tìm kiếm, thêm mới, xoá trong cây n nút là O(log n)3Định nghĩaCây AVL là một cây nhị phân tìm kiếmChiều cao cây con trái và phải của nút gốc hơn kém nhau không quá 1Cả hai cây con trái và phải cũng phải là cây AVL4Chỉ số cân bằng (Balance factor)Chỉ số cân bằng (bF – balance Factor) của một nút: bF = hL – hRhL: chiều cao cây con tráihR: chiều cao cây con phảiCó 3 trường hợp:bF = 0: hL = hRbF > 0: hL > hRbF { 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 node7public CMyAVLIntNode(T x){ data = x; height = 1; pLeft = null; pRight = null;}Trường hợp 1: Lệch trái81.1 Lệch trái – trái1.2 Lệch trái – phảiTrường hợp 2: Lệch phải92.1 Lệch phải – trái2.2 Lệch phải – phảiLệch trái - trái10Quay phảiLệch trái – phải: Thực hiện quay kép11B1. Quay tráiLệch trái – phải: Thực hiện quay kép12B2. Quay phảiThêm 1 node vào cây AVLTương tự như trên cây NPTKSau 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àyPhương thức InsertNode trả về node root mới sau khi cân bằng13Bài tập 1Cho dãy số: 45, 46, 70, 11, 13, 42, 21, 9, 25, 4Hãy trình bày từng bước quá trình xây dựng cây AVLTrình bày từng bước duyệt cây theo thứ tự sau14Xác định chỉ số cân bằng15int GetBalance(CMyAVLNode N){ if (N == null) return 0; return Height(N.PLeft) - Height(N.PRight);}int Height(CMyAVLNode N){ if (N == null) return 0; return N.Height;}Phương thức xoay phải16public 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;}Phương thức xoay trái17public 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;}18public CMyAVLNode Insert(CMyAVLNode node, T x){ if (node == null) return (new CMyAVLNode(x)); if (node.Data == x) return node; if (x 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;}Hủy 1 node trên câyTương tự như trên cây NPTKSau khi hủy, nếu mất cân bằng  cân bằng lạiHàm DeleteNode trả về node root sau khi cân bằng20Bài tập 21. Hãy trình bày từng bước quá trình:Xóa node có giá trị 13Xóa node có giá trị 452. Trình bày thuật toán và cài đặt phương thức xóa node trên cây AVL21