Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 10 - Trường ĐH Văn Lang

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

20
lượt xem 5
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 10 cung cấp cho người học những kiến thức như: tổng quan về cấu trúc cây; thao tác trên cấu trúc cây; cây các loại cây; cây nhị phân; duyệt 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 10 - Trường ĐH Văn Lang

KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU & GIẢI (Data Structure and Algorithm) THUẬT CHƯƠNG 10: CẤU TRÚC CÂY (TREE) GVGD: Th.S Trần Công Thanh HỌC KỲ I – NĂM HỌC 2020-2021 KHÓA 25T-IT
01. TỔNG QUAN 02. THAO TÁC TRÊN CT CÂY NỘI 03. CÁC LOẠI CÂY DUNG 04. CÂY NHỊ PHÂN 05. DUYỆT CÂY
KHÁI NIỆM CƠ BẢN ▪ Cây là một cấu trúc phân tầng của các phần tử gọi là nút (node) • Mỗi node chứa một phần tử đơn. • Mỗi phần tử có thể có 1 hoặc nhiều nhánh kết nối với các nút khác, được gọi là nút con. ▪ Mọi cây có 1 nút gốc – root duy nhất. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Mọi nút trừ nút gốc đều là con của một nút khác – nút cha. 3 3 KHOA CÔNG NGHỆ THÔNG TIN
CẤU TRÚC CÂY TRONG THỰC TẾ ▪ Thông thường các mô hình tổ chức sẽ có cấu trúc cây: • Một cây tổ chức là một cây không có thứ tự có cấu trúc phân tầng, như tổ chức của phòng ban trong thương mại. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com University Engineering Medicine Science Education Law Arts Chemistry Physics Maths Languages History 4 4 KHOA CÔNG NGHỆ THÔNG TIN
▪ Sơ đồ phân loại sinh học cũng là một loại cây phổ biến. ▪ Cây này cũng không có thứ tự nhưng có tổ chức phân lớp. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com animals worms insects arachnids vertebrates stars sponges ants beetles flies fish reptites birds mammals snakes lizards crocodiles 5 KHOA CÔNG NGHỆ THÔNG TIN
▪ Một bản đồ di chuyển thường được dùng trong ứng dụng định vị robot dùng lưu trữ các hướng theo một giải thuật để khám phá toàn bộ không gian xung quanh. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 6 KHOA CÔNG NGHỆ THÔNG TIN
▪ Tổ chức file và các thư mục ▪ Chúng tả có thể mô hình hóa tổ chức các file bằng cách dùng cây không sắp xếp theo mô hình nút lá, và các thư mục như các nút cha. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com root doc bin lib etc tmp users cp grep sort mail motd passwd 7 KHOA CÔNG NGHỆ THÔNG TIN
Thao tác trên cấu trúc cây Nó phải có thể ▪ truy cập vào nút gốc của cây ▪ truy cập tất cả các tổ tiên của một nút trong cây ▪ truy cập tất cả con cháu của một nút trong cây 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com ▪ thêm một nút mới vào cây, ▪ xóa một nút nhất định khỏi cây ▪ Duyệt cây. 8 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa This node is the parent This is an edge 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 9 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 10 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa ▪ Cây có thể được sắp xếp hoặc không được sắp xếp. ▪ Cây không có thứ tự, cây là cây ở hình dạng. Theo nghĩa cấu trúc, nó trông giống như một cái cây. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com ▪ Đối với bất kỳ nút nhất định nào, không có thứ tự nào được áp đặt cho các nút con của nút đó 11 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa ▪ Một cây có thứ tự áp đặt thứ tự trên các nút ▪ Có nhiều chiến lược sắp xếp thứ tự, nhưng theo nghĩa đơn giản nhất, thứ tự có thể được áp đặt bằng cách gán các số khác nhau cho các nút con của nút ▪ Lưu ý rằng thứ tự và duyệt cây không giống nhau 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 12 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa ▪ Cây có thể cân bằng hoặc không cân bằng ▪ Cây cân bằng tốt là cây không có nút nào xa gốc hơn bất kỳ nút nào khác ▪ Các giải thuật cân bằng khác nhau cho phép các định 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com nghĩa khác nhau về "xa hơn nhiều" và đi kèm với các chi phí khác nhau để giữ cho cây cân bằng 13 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 14 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa ▪ Brute force tìm kiếm thông qua một cấu trúc tuyến tính yêu cầu thời gian O (N) ▪ Nếu cây được cân bằng tốt, việc tìm kiếm, chèn và xóa có thể được thực hiện trong thời gian O (ln (N)) ▪ Một cây không cân bằng cao cung cấp ít hoặc không có giá trị 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com vì trong trường hợp xấu nhất, hầu hết cây sẽ phải được duyệt qua để thực hiện việc chèn, xóa hoặc tra cứu dẫn đến thời gian là O (N) cho các thao tác này. 15 KHOA CÔNG NGHỆ THÔNG TIN
Một số định nghĩa ▪ Cây NULL – là cây có chỉ có nút gốc hay không có nút nào. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 16 KHOA CÔNG NGHỆ THÔNG TIN
Mô tả cây nhị phân ▪ Mô tả dữ liệu ▪ Mô tả tác vụ ▪ Ba phép duyệt cây nhị phân 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 17 17 KHOA CÔNG NGHỆ THÔNG TIN
BT – Mô tả dữ liệu ▪ Cấu trúc cây đơn giản nhất, mỗi nút có tối đa 2 nút con ▪ Tại mỗi nút gồm các 3 thành phần • Phần data: chứa giá trị, thông tin… • Liên kết đến nút con trái (nếu có) • Liên kết đến nút con phải (nếu có) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com ▪ Cây nhị phân có thể rỗng (ko có nút nào) ▪ Cây NP khác rỗng có 1 nút gốc • Có duy nhất 1 đường đi từ gốc đến 1 nút • Nút không có nút con bên trái và con bên phải là nút lá 18 18 18 KHOA CÔNG NGHỆ THÔNG TIN
BT – Mô tả dữ liệu Kích thước = 9 (số nút) Mức 0 A Cây con trái Cây con phải Mức 1 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com B C Mức 2 D E F G Mức 3 Độ sâu/chiều cao = 3 H I 19 19 KHOA CÔNG NGHỆ THÔNG TIN
20 BT – Mô tả tác vụ 1. Khởi tạo cây 6. Xóa trái 2. Kiểm tra rỗng 7. Xóa phải 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 3. Tạo nút 8. Duyệt cây 4. Thêm trái 9. Tìm kiếm 5. Thêm phải 10. Xóa cây 20 KHOA CÔNG NGHỆ THÔNG TIN