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)

Chia sẻ: Bình Yên | Ngày: | Loại File: PPTX | Số trang:21

Thêm vào BST

Báo xấu

66
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ân tìm kiếm – Cây cân bằng Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1
Nội dung 1. Khái niệm cây AVL 2. Đặc điểm 3. Định nghĩa cấu trúc dữ liệu 4. Các kỹ thuật cân bằng cây 5. Chèn phần tử vào cây 6. Xóa phần tử khỏi cây 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 < 0: hL < hR 5
Khai báo cấu trúc cây AVL class 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 } 6
Constructor cho node public CMyAVLIntNode(T x) { data = x; height = 1; pLeft = null; pRight = null; } 7
Trường hợp 1: Lệch trái 1.1 Lệch trái – trái 1.2 Lệch trái – phải 8
Trường hợp 2: Lệch phải 2.1 Lệch phải – trái 2.2 Lệch phải – phải 9
Lệch trái - trái Quay phải 10
Lệch trái – phải: Thực hiện quay kép B1. Quay trái 11
Lệch trái – phải: Thực hiện quay kép B2. Quay phải 12
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 int 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); } 15
Phương thức xoay phải public 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; } 16
Phương thức xoay trái public 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; } 17
public 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; } 19
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