Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 6: Cấu trúc cây - Lê Nguyên Khôi

Chèn liên tục vào MinHeap, nhưng không khôi phục tính chất thứ tự bộ phận.Khôi phục tính chất thứ tự bộ phận (sử dụng downheap) bắt đầu từ đỉnh chính giữa Sắp Xếp Cây Thứ Tự Bộ Phận – So Sánh Giống sắp xếp gộp (merge sort) Độ phức tạp 0 (n logn) Giống sắp xếp chèn (insertion sort) In-place algortihm

pdf35 trang | Chia sẻ: thucuc2301 | Ngày: 21/11/2020 | Lượt xem: 445 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 6: Cấu trúc cây - Lê Nguyên Khôi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Thiết Kế & Đánh Giá Thuật Toán Cấu Trúc Cây TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung  Khái niệm cơ bản  Duyệt cây  Cây nhị phân  Cây tìm kiếm nhị phân Cây tìm kiếm nhị phân cân bằng  Cây thứ tự bộ phận 1 Phân Loại Cây  Cây tự do (Đồ thị)  Đồ thị – mạng  Vô hướng, có hướng  Trọng số  Liên thông  Chu trình, phi chu trình  Cây có gốc  Có 1 đỉnh được coi là gốc  Quan hệ cha - con 2 Cây Tự Do (Đồ Thị) vô hướng định hướng 3 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở Cây Tự Do (Đồ Thị) trọng số không trọng số 4 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở 5 7 11 15 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở Cây Tự Do (Đồ Thị) liên thông không liên thông 5 Cây Tự Do (Đồ Thị) chu trình phi chu trình 6 Cây Tự Do (Đồ Thị)  Mạng vận tải  Mạng liên lạc  Mạng thông tin  Mạng xã hội  Mạng phụ thuộc 7 Cây Có Gốc – Định Nghĩa  Sử dụng khái niệm đồ thị có hướng  Có một đỉnh đặc biệt được gọi là gốc cây  Mỗi đỉnh C bất kỳ không phải là gốc, tồn tại duy nhất một đỉnh P có đường đi từ P đến C. Đỉnh Parent được gọi là cha của đỉnh Child, và Child là con của Parent.  Có đường đi duy nhất từ gốc tới mỗi đỉnh của cây. 8 Cây Có Gốc – Ví Dụ 9 gốc đỉnh trong lá A B C D E F G mức 0 mức 1 mức 2 Cây Có Gốc – Thuật Ngữ  Độ cao (height)  của một đỉnh là độ dài đường đi dài nhất từ đỉnh đó tới một lá.  độ cao của lá bằng 0.  độ cao của cây là độ cao của gốc  Độ sâu (depth)  của một đỉnh là độ dài đường đi từ gốc tới đỉnh đó  độ sâu của gốc bằng 0. 10 Cây Có Gốc – Độ Cao  Độ cao của một đỉnh là độ dài đường đi dài nhất từ đỉnh đó tới một lá.  Xác đinh độ cao của mỗi đỉnh ℎ  = max ∀ ℎ( ) + 1 11 A B C D E F G Cây Biểu Thức 12 * + - / 3 7 4 6 2 Duyệt Cây  Thứ tự trước (preorder)  Thứ tự trong (inorder)  Thứ tự sau (postorder) 13 r T1 T2 Tk r1 r2 rk Duyệt Cây – Thứ Tự Trước  Thăm gốc r  Duyệt lần lượt các cây con T1, , Tk theo thứ tự trước  Còn được biết đến là kỹ thuật tìm kiếm theo độ sâu A-B-E-F-C-D-G 14 r T1 T2 Tk r1 r 2 rk A B C D E F G Duyệt Cây – Thứ Tự Trước – Mã Giả Algorithm preOrder(p) visit(p) for each child ci of p preOrder(ci) 15 Duyệt Cây – Thứ Tự Trong  Duyệt cây con trái T1 theo thứ tự trong  Thăm gốc r  Duyệt lần lượt các cây con T2, , Tk theo thứ tự trong E-B-F-A-C-G-D 16 r T1 T2 Tk r1 r 2 rk A B C D E F G Duyệt Cây – Thứ Tự Trong – Mã Giả Algorithm inOrder(p) inOrder(c1) visit(p) for each child ci of p inOrder(ci) 17 Duyệt Cây – Thứ Tự Sau  Duyệt lần lượt các cây con T1, , Tk theo thứ tự sau  Thăm gốc r E-F-B-C-G-D-A 18 r T1 T2 Tk r1 r 2 rk A B C D E F G Duyệt Cây – Thứ Tự Sau – Mã Giả Algorithm postOrder(p) for each child ci of p postOrder(ci) visit(p) 19 Cây Nhị Phân  Mỗi đỉnh có nhiều nhất 2 đỉnh con  Nhị phân chuẩn (full/proper binary tree) Mỗi đỉnh có 0 hoặc 2 đỉnh con  Nhị phân đầy đủ (complete binary tree)  Các lá ở cùng mức  Nhị phân gần đầy đủ (almost complete binary tree)  Có con phải thì có con trái 20 Cây Nhị Phân Đầy Đủ  Độ cao ℎ có 2 − 1 lá   lá có độ cao log  + 1 21 Cây Tìm Kiếm Nhị Phân  Cây tìm kiếm nhị phân là cây nhị phân lưu khóa ở các đỉnh trong của nó và thỏa mãn tính chất sau:  Gọi , ,  là 3 đỉnh sao cho  nằm trong cây con trái của  và  nằm trong cây con phải của , thỏa mãn  !(") ≤  !($) ≤  !(%)  Duyệt cây tìm kiếm nhị phân theo thứ tự trong sẽ thăm các khóa theo thứ tự tăng dần 22 Cây Tìm Kiếm Nhị Phân  Một số thao tác chính:  Tìm kiếm: đỉnh có khóa & đỉnh trước/sau đỉnh có khóa & đỉnh có khóa min/max  Sửa đổi:  thêm đỉnh có khóa & xóa đỉnh có khóa &  Mã giả  Độ phức tạp 23 6 92 41 8 Cây Tìm Kiếm Nhị Phân Cân Bằng  Cây tìm kiếm nhị phân cân bằng có cấu trúc của cây tìm kiếm nhị phân nhưng đảm bảo độ cao của cây là '(log )  Ví dụ:  Cây AVL Tìm kiếm nhanh  Cây Đỏ-Đen Sửa đổi nhanh 24 Cây Thứ Tự Bộ Phận – Heap  Cây nhị phân gần đầy đủ:  Có tất cả các mức của cây đều không thiếu đỉnh nào, trừ mức thấp nhất được lấp đầy kể từ bên trái  Độ cao là log  25 2 35 79 8 0 1 2 3 4 5 Cây Thứ Tự Bộ Phận – Heap  Min heap là cây nhị phân gần đầy đủ với tính chất:  Khóa của một đỉnh bất kỳ NHỎ hơn hoặc bằng khóa của các đỉnh con của nó.  Max heap là cây nhị phân gần đầy đủ với tính chất:  Khóa của một đỉnh bất kỳ LỚN hơn hoặc bằng khóa của các đỉnh con của nó. 26 Cây Thứ Tự Bộ Phận – Min Heap  Một số thao tác chính:  Tìm nhỏ nhất  Xóa nhỏ nhất  Chèn 27 2 35 79 8 0 1 2 3 4 5 Min Heap – Xóa Nhỏ Nhất  Thay thế gốc bằng đỉnh cuối cùng  Giải phóng đỉnh cuối cùng  Khôi phục tính chất thứ tự bộ phận của heap  Downheap khôi phục lại tính chất bằng cách đảo chỗ đỉnh có khóa & dọc theo đường đi từ gốc xuống  Downheap dừng khi & tiến tới một lá hay một đỉnh có khóa con lớn hơn &  Độ phức tạp: ((log ) 28 2 35 79 8 0 1 2 3 4 5 Min Heap – Xóa Nhỏ Nhất  Thay thế gốc bằng đỉnh cuối  Downheap 29 2 35 79 8 0 1 2 3 4 5 8 35 79 0 1 2 3 4 3 85 79 0 1 2 3 4 8 35 79 0 1 2 3 4 5 Min Heap – Chèn  Tìm tới vị trí để đưa phần tử mới vào  Lưu phần tử có khóa & vào đỉnh đó  Khôi phục tính chất thứ tự bộ phận của heap  Upheap khôi phục lại tính chất bằng cách đảo chỗ đỉnh có khóa & dọc theo đường đi từ đỉnh tới gốc  Upheap dừng khi & tiến tới gốc hay một đỉnh có khóa cha nhỏ hơn &  Độ phức tạp: ((log ) 30 2 35 79 1 0 1 2 3 4 5 Min Heap – Chèn  Thêm đỉnh cuối mới  Upheap 31 2 35 79 0 1 2 3 4 5 2 35 79 0 1 2 3 4 15 2 35 79 0 1 2 3 4 15 2 15 79 0 1 2 3 4 35 Sắp Xếp Cây Thứ Tự Bộ Phận  Liên tục xóa nhỏ nhất của Min heap sẽ được một dãy tăng dần  Độ phức tạp: (( log )  Xây dựng Min heap  Lần lượt chèn các khóa vào cây Min heap, bắt đầu từ cây Min heap rỗng  Độ phức tạp: (( log ) 32 2 35 79 8 0 1 2 3 4 5 Xây Dựng Min Heap – Cách Khác  Chèn liên tục vào Min Heap, nhưng không khôi phục tính chất thứ tự bộ phận.  Khôi phục tính chất thứ tự bộ phận (sử dụng downheap) bắt đầu từ đỉnh chính giữa  Xem tr.158 33 Sắp Xếp Cây Thứ Tự Bộ Phận – So Sánh  Giống sắp xếp gộp (merge sort)  Độ phức tạp (  log   Giống sắp xếp chèn (insertion sort)  In-place algortihm 34

Các file đính kèm theo tài liệu này:

  • pdfthiet_ke_danh_gia_thuat_toanbaigiang06_cautruccay_4596_2032093.pdf