tailieunhanh - Cây cân bằng - cây đỏ đen và cây 2-3-4

Nội dung chính của bài thuyết trình trình bày khái niệm, các thao tác, biểu diễn CTDL và đánh giá của cây cân bằng - cây đỏ đen và cây 2-3-4. Mời các bạn tham khảo! | 11/29/2018 K65A_FIT_HNUE 1 LOGO CHỦ ĐỀ 1: CÂY CÂN BẰNG & CÂY ĐỎ ĐEN & CÂY 2-3-4 MÔN CHUYÊN ĐỀ TỐT NGHIỆP KHOA HỌC MÁY TÍNH Thành viên nhóm: Phạm Thị Khánh Huyền Nguyễn Thị Kim Dung Trần Thị Lan Nguyễn Thị Hồng Nhung NỘI DUNG CHÍNH 11/29/2018 K65A_FIT_HNUE 2 CÂY CÂN BẰNG CÂY ĐỎ ĐEN CÂY 2-3-4 B-TREE 11/29/2018 K65A_FIT_HNUE 3 CÂY CÂN BẰNG Khái niệm 1 Các thao tác 2 Bài tập minh họa 5 Đánh giá 4 Biểu diễn CTDL 3 11/29/2018 K65A_FIT_HNUE 4 GIỚI THIỆU AVL TREE Phương pháp chèn trên CNPTK có thể có những biến dạng mất cân đối nghiêm trọng Chi phí cho việc tìm kiếm trong trường hợp xấu nhất đạt tới n VD: 1 triệu nút ⇒ chi phí tìm kiếm = nút Nếu có một cây tìm kiếm nhị phân cân bằng hoàn toàn, chi phí cho việc tìm kiếm chỉ xấp xỉ VD: 1 triệu nút ⇒ chi phí tìm kiếm =≈ 20 nút . Adelson-Velsky và . Landis đã đề xuất một tiêu chuẩn cân bằng (gọi là cây cân bằng AVL) Cây AVL có chiều cao O() 1. KHÁI NIỆM Cây cân bằng AVL Là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao của cây con trái và cây con phải không chênh lệch quá 1 11/29/2018 K65A_FIT_HNUE 5 Cả 2 cây trên đều là cây nhị phân tìm kiếm Nhưng chỉ có cây đầu tiên là cây cân = 5 có con trái 1, con phải 1 ------ 8 có con trái 2, con phải 1 18 có con trái 1, con phải 0 ------ 12 có con trái 3, con phải 2) 5 1. KHÁI NIỆM Chỉ số cân bằng của một nút: Định nghĩa: Chỉ số cân bằng của một nút là hiệu của chiều cao cây con phải và cây con trái của nó. Đối với một cây cân bằng, chỉ số cân bằng (CSCB) của mỗi nút chỉ có thể mang một trong ba giá trị sau: CSCB(p) = 0 ⇔ Độ cao cây phải (p) = Độ cao cây trái (p) CSCB(p) = 1 ⇔ Độ cao cây phải (p) > Độ cao cây trái (p) CSCB(p) = -1 ⇔ Độ cao cây phải (p) < Độ cao cây trái (p) 11/29/2018 K65A_FIT_HNUE 6 1. KHÁI NIỆM 11/29/2018 K65A_FIT_HNUE 7 Cây trên có phải là cây cân bằng hay không? Xác định CSCB của mỗi nút trên cây? - Nút lá luôn có CSCB = 0 7 CÁC TRƯỜNG HỢP MẤT 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: Mất cân . | 11/29/2018 K65A_FIT_HNUE 1 LOGO CHỦ ĐỀ 1: CÂY CÂN BẰNG & CÂY ĐỎ ĐEN & CÂY 2-3-4 MÔN CHUYÊN ĐỀ TỐT NGHIỆP KHOA HỌC MÁY TÍNH Thành viên nhóm: Phạm Thị Khánh Huyền Nguyễn Thị Kim Dung Trần Thị Lan Nguyễn Thị Hồng Nhung NỘI DUNG CHÍNH 11/29/2018 K65A_FIT_HNUE 2 CÂY CÂN BẰNG CÂY ĐỎ ĐEN CÂY 2-3-4 B-TREE 11/29/2018 K65A_FIT_HNUE 3 CÂY CÂN BẰNG Khái niệm 1 Các thao tác 2 Bài tập minh họa 5 Đánh giá 4 Biểu diễn CTDL 3 11/29/2018 K65A_FIT_HNUE 4 GIỚI THIỆU AVL TREE Phương pháp chèn trên CNPTK có thể có những biến dạng mất cân đối nghiêm trọng Chi phí cho việc tìm kiếm trong trường hợp xấu nhất đạt tới n VD: 1 triệu nút ⇒ chi phí tìm kiếm = nút Nếu có một cây tìm kiếm nhị phân cân bằng hoàn toàn, chi phí cho việc tìm kiếm chỉ xấp xỉ VD: 1 triệu nút ⇒ chi phí tìm kiếm =≈ 20 nút . Adelson-Velsky và . Landis đã đề xuất một tiêu chuẩn cân bằng (gọi là cây cân bằng AVL) Cây AVL có chiều cao O() 1. KHÁI NIỆM Cây cân bằng AVL Là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao .