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

Chia sẻ: Vân Vân | Ngày: | Loại File: PPTX | Số trang:111

Thêm vào BST

Báo xấu

39
lượt xem 2
download

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

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!

Chủ đề:

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

Lưu

Nội dung Text: Cây cân bằng - cây đỏ đen và cây 2-3-4

MÔN CHUYÊN ĐỀ TỐT NGHIỆP KHOA HỌC MÁY TÍNH CHỦ ĐỀ 1: CÂY CÂN BẰNG & CÂY ĐỎ ĐEN & CÂY 23 Phạm Thị Khánh Huyền 4 Thành viên nhóm: Ø Ø Nguyễn Thị Kim Dung Ø Trần Thị Lan Ø Nguyễn Thị Hồng Nhung LOGO 12/26/18 1 K65A_FIT_HNUE
NỘI DUNG CHÍNH CÂY CÂN BẰNG CÂY ĐỎ ĐEN CÂY 234 BTREE 12/26/18 2 K65A_FIT_HNUE
CÂY CÂN BẰNG 1 Khái niệm 2 Các thao tác 3 Biểu diễn CTDL 4 Đánh giá 5 Bài tập minh họa 12/26/18 3 K65A_FIT_HNUE
GIỚI THIỆU AVL TREE 12/26/18 4 K65A_FIT_HNUE
1. KHÁI NIỆM q 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 12/26/18 5 K65A_FIT_HNUE
1. KHÁI NIỆM q 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) • 12/26/18 CSCB(p) = 1 ⇔ Độ cao cây ph6ải (p)
1. KHÁI NIỆM 1. Cây trên có phải là cây cân bằng hay không? 2. Xác định CSCB của mỗi nút trên cây? 12/26/18 7 K65A_FIT_HNUE
CÁC TRƯỜNG HỢP MẤT CÂN BẰNG q 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: q Mất cân bằng trái – trái (LL) q Mất cân bằng trái – phải (LR) q Mất cân bằng phải – phải (RR) q Mất cân bằng phải – trái (RL) 12/26/18 8 K65A_FIT_HNUE
CÁC TRƯỜNG HỢP MẤT CÂN BẰNG q a) Mất cân bằng tráitrái (LL) 12/26/18 9 K65A_FIT_HNUE
CÁC TRƯỜNG HỢP MẤT CÂN BẰNG q b) Mất cân bằng tráiphải (LR) 12/26/18 10 K65A_FIT_HNUE
CÁC TRƯỜNG HỢP MẤT CÂN BẰNG q c) Mất cân bằng phảiphải (RR) 12/26/18 11 K65A_FIT_HNUE
CÁC TRƯỜNG HỢP MẤT CÂN BẰNG q d) Mất cân bằng phảitrái (RL) 12/26/18 12 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q Xử lý cụ thể cho các trường hợp mất cân bằng như sau: MẤT CÂN BẰNG PHẢI Mất cân bằng phảiphải (RR) Mất cân bằng phảitrái (RL) Quay trái tại node bị mất cân Quay phải tại node con phải của bằng node bị mất cân bằng Quay trái tại node bị mất cân bằng MẤT CÂN BẰNG TRÁI Mất cân bằng tráitrái (LL) Mất cân bằng tráiphải (LR) Quay phải tại node bị mất cân Quay trái tại node con trái của bằng node bị mất cân bằng Quay phải tại node bị mất cân bằng 12/26/18 13 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – phải (RR): 12/26/18 14 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – phải (RR): 12/26/18 15 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – trái (RL) q Quá trình xử lý gồm 2 bước sau: • Bước 1: Quay phải Q • Bước 2: Quay trái cây P 12/26/18 16 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – trái (RL): • Bước 1: Quay phải cây Q 12/26/18 17 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – trái (RL): • Bước 2: Quay trái cây P 12/26/18 18 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – trái (RL): • Bước 1: Quay phải cây Q 12/26/18 19 K65A_FIT_HNUE
XỬ LÝ MẤT CÂN BẰNG q P mất cân bằng phải – trái (RL): • Bước 2: Quay trái cây P 12/26/18 20 K65A_FIT_HNUE