TAILIEUCHUNG - 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 .

• Kỹ thuật lập trình
• Cây cân bằng
• Cây đỏ đen và cây 2 3 4
• Khoa học máy tính
• Biểu diễn CTDL
• Chương trình dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cây cân bằng AVL
• Cây nhị phân tìm kiếm
• Xử lý mất cân bằng bằng
• Các node trên cây cân bằng
• Bài giảng Cây cân bằng
• Tài liệu Cây cân bằng
• lập trình cơ bản
• tổng quan lập trình
• lập trình đối tượng
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cách xây dựng cây cân bằng
• Các trường hợp mất cân bằng cây AVL
• Xử lý mất cân bằng cây AVL
• Thao tác trên cây AVL
• Cấu trúc dữ liệu và giải thuật
• Data structures
• Cây cân bằng Red Black
• Cấu trúc lưu trữ
• Cây tìm kiếm nhị phân cân bằng
• Cây tìm kiếm nhị phân
• AVL tree
• Cây splay
• Cây 2‐3
• Bài giảng Cấu trúc dữ liệu 1
• Cây nhị phân
• Cây nhị phân cân bằng
• Đánh giá tìm kiếm
• Bài giảng Đánh giá tìm kiếm
• Mất cân bằng AVL Tree
• Cân bằng lại cây AVL
• Phần tử trên cây AVL
• Hủy một phần tử trên cây AVL
• Cây nhị phân tìm kiếm cân bằng
• Mất cân bằng cây nhị phân
• Cây đỏ đen
• Cây AA
• tình trạng thừa cân
• giảm cân không đúng cách
• tác hại của giảm cân
• bữa ăn của người Việt
• ẩm thực Việt Nam
• khuynh hướng ẩm thực
• tổ chức dữ liệu
• chỉ số cân bằng
• giá trị hợp lệ
• lệch nhánh trái
• lệch nhánh phải
• cấu trúc dữ liệu cao cấp
• ngôn ngữ lập trình C++
• lập trình hướng đối tượng
• cấu trúc dữ liệu tuyến tính
• cây tìm kiếm cân bằng
• Tạp chí Khoa học Công nghệ và Thực phẩm
• Phương pháp phân đoạn
• dữ liệu ảnh
• Cây phân cụm đa nhánh cân bằng
• Phép biến đổi Wavelet
• Giao thức cây thu thập dữ liệu
• Cân bằng năng lượng
• Thiết kế giao thức EACTP
• Energy Aware Collection Tree Protocol
• Giao thức CTP
• Giải thuật 1
• Thao tác trên cây cân bằng
• cao su
• phòng bệnh cây cao su
• kỹ thuật trồng cây nông nghiệp
• các loại cây nông nghiệp
• phương pháp trồng cây
• phát triển cây công nghiệp
• Cấu trúc dữ liệu cây
• Cây có thứ tự
• tìm kiếm cây trong một nút
• sự tương ứng hình thức
• cây từ điển tìm kiếm
• loại phần tử trong trie
• Cấu trúc cây nhị phân
• Cấu trúc cây nhị phân tìm kiếm
• Cấu trúc giải thuật
• Thành phần dữ liệu
• Cây AVL
• Xây dựng cây cân bằng
• Thao tác tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng